4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ What do you mean by " This kind of partitions can be identified with partitions of n-k by dividing the even numbers by 1. " ??? $\endgroup$ – user331899 May 29 '16 at 14:29
  • $\begingroup$ In your answer q(2n+1) = q(n) + ... + q(1) + 1 = q(2n). ????? what happend ? $\endgroup$ – user331899 May 29 '16 at 15:02
  • $\begingroup$ @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$. $\endgroup$ – Erick Wong May 29 '16 at 19:44
  • $\begingroup$ 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 $\endgroup$ – Emre May 29 '16 at 19:48
  • 1
    $\begingroup$ 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 $\endgroup$ – Emre May 30 '16 at 1:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.