4

Let n be a positive integer. Prove that there are 2^(n−1) ways to write n as a sum of positive integers, where the order of the sum matters. For example, there are 8 ways to write 4 as the sum of positive integers: 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 2 + 1, 1 + 3, 2 + 1 + 1, 2 + 2, 3 + 1, and 4. Hint: count each of the possibilities for the first value in the sum, and add these together. You may use the fact that 1 + 2 + 4 + . . . + 2k = 2^(k+1) − 1.

I thought that you would use induction to solve for the base case, and show that there are bounds 1 < x < 2^k such that the 2^(k-1) is within those bounds and solvable, but I'm not sure if this is the right method.

MichaelGofron
  • 231
  • I think you're on the right track. Assume that it holds true for $n$, and it should be easy to show that it holds for $n+1$. Hint: for $n+1$ there are $2^{n-1}$ more ways to write the sum than for $n$ (why?). – Winston Oct 12 '14 at 20:21

2 Answers2

1

Using generating functions and classifying by the number $k$ of summands we get the total generating function $$\sum_{k\ge 1} \left(\frac{z}{1-z}\right)^k = \frac{z}{1-z} \frac{1}{1-z/(1-z)} = \frac{z}{1-2z}.$$ Now observe that $$[z^n] \frac{z}{1-2z} = [z^{n-1}] \frac{1}{1-2z} = 2^{n-1}.$$

Marko Riedel
  • 61,317
0

You’re trying to work too hard, and perhaps not thinking enough about the hint.

Your induction hypothesis is that each positive integer $k<n$ has $2^{k-1}$ decompositions. Following the hint, notice that the first value of a decomposition of $n$ must be a positive integer less than or equal to $n$. Suppose that the first integer in the decomposition is $k$; then the remaining integers must form a decomposition of $n-k$, so by the induction hypothesis there are $2^{n-k-1}$ ways to complete the decomposition of $n$. That is, we now know that $n$ has $2^{n-k-1}$ decompositions whose first term is $k$. Now just sum over the possible values of $k$.

Brian M. Scott
  • 616,228