number of ways to partition an integer. A partition of a positive integer n is a way of writingn as a sum of positive integers. 
Two sums
that differ only in the order of their summands are considered the same partition. 
For example,
4 can be partitioned in five distinct ways:
4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1
Let q(n) be the number of partitions of n into powers of 2 (Here q(0) = 1, q(1) = 1). 
For
instance, if n = 4, we have
4
2 + 2
2 + 1+ 1
1 + 1 + 1 + 1
Show that q(n) is even for all n ≥ 2. Give a combinatorial proof.

Use induction. Check the base cases. 
Let's look at the partitions of $2n+1$. Every partition of $2n+1$ includes odd number of $1$s. If a partition contains $2k+1$ $1$s, all the other terms in it are even. This kind of partitions can be identified with partitions of $n-k$ by dividing the even numbers by $2$. So, $q(2n+1)=q(n)+q(n-1)+\ldots+q(2)+q(1)+1$, where $1$ at the end stands for the partition consists solely of $1$s. As everything except $q(1)$ is even in this sum, $q(2n+1)$ is also  even.   
Now, look at the partitions of $2n$. A partition contains an even number of $1$s. If a partition contains $2k$ $1$s, all the other terms in it are even. This kind of partitions can be identified with partitions of $n-k$ by dividing the even numbers by $2$. So, $q(2n)=q(n)+q(n-1)+\ldots+q(2)+q(1)+1$, where $1$ at the end stands for the partition consists solely of $1$s. As everything except $q(1)$ is even in this sum, $q(2n)$ is also  even.  
