# 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.

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.
• @user331899 There is a one-to-one correspondence between the partitions of $n-k$ (into powers of two) and the partitions of $2n+1$ which use exactly $2k+1$ copies of $1$. – Erick Wong May 29 '16 at 19:44
• Yes $q(2n+1)=q(2n)$. Consider the following bijection: for every partition of $2n$ add a $1$ to get a new partition of $2n+1$. Each distinct partition of $2n$ gives a unique partition of $2n+1$ by this process. So, this map from the partitions of $2n$ to the partitions of $2n+1$ is injective and well-defined. Moreover, every partition of $2n+1$ contains at least one $1$. So, every partition of $2n+1$ can be obtained by adding $1$ to a partition of $2n$. Thus, the map from the partitions of $2n$ to the partitions of $2n+1$ is surjective. So, it is a bijection,i.e. two sets have the same cardin – Emre May 30 '16 at 1:27