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

## 1 Answer

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.

• What do you mean by " This kind of partitions can be identified with partitions of n-k by dividing the even numbers by 1. " ??? – user331899 May 29 '16 at 14:29
• In your answer q(2n+1) = q(n) + ... + q(1) + 1 = q(2n). ????? what happend ? – user331899 May 29 '16 at 15:02
• @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
• There was a typo, 1 should be 2. In how many partitions of 5, we use exactly 2 1s? 0 because other than 1 every other power of two is even but, if we use even number of 1s the sum would be even, whereas 5 is odd. In how many partitions of 5, we use exactly one 1? This question is the same thing as the following: in how many ways can we partition 4 into powers of 2 that are at least two? Every such partition in fact is a regular partition of 4/2=2 multiplied by 2. Like 122--11, 14-2 – Emre May 29 '16 at 19:48
• 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