# Proof by induction of a sum?

Let $n ∈ N$. Prove by induction that there are $n$ ways to write the number $n$ as a sum $n=x_1+x_2+...+x_k$ where the $x_i$ are natural numbers and $x_1 ≤x_2 ≤...≤x_k ≤x_1+1$.

For example, $5 = 5$, $5 = 1 + 1 + 1 + 1 + 1$, $5 = 1 + 1 + 1 + 2$, $5 = 1 + 2 + 2$, and $5 = 2 + 3$.

• have you tried something? why does your induction fail? – Exodd Oct 13 '14 at 18:28
• Do you know something about "Generating Functions" ? – Dinesh Oct 13 '14 at 18:31
• I know nothing about generating functions. I'm not sure what I'm supposed to do. I don't know if it's x(k+1), or what the LHS/RHS is supposed to look like. – Test Oct 13 '14 at 23:56

Here's a rough outline of a strategy: With $n=x_1+\cdots+x_k$, you can write $n+1=x_2+\cdots+x_k+(x_1+1)$. There is one allowed way to write $n+1$ that you can't get in this way, however.

Edit: To consider an example, here are the five ways to write $5$, with $x_1$ marked in red:

$5=\color{red}{5}$, $5=\color{red}{1}+1+1+1+1$, $\color{red}{1}+1+1+2$, $5=\color{red}{1}+2+2$, and $5=\color{red}{2}+3$

For each of these, take the red number, add $1$ to it and put it last, thus getting five ways to write $6$:

$6=\color{red}{6}$, $6=1+1+1+1+\color{red}{2}$, $6=1+1+2+\color{red}{2}$, $6=2+2+\color{red}{2}$, and $6=3+\color{red}{3}$.

Notice how this gives all the allowed ways to write $6$ as a sum, except for one, namely $6=1+1+1+1+1+1$. The same procedure works to get from $n$ to $n+1$ for all $n$, not just for $n=5$.

• one allowed way to write n+1 ? I'm also having trouble figuring out what the LHS and RHS would equal. – Test Oct 13 '14 at 22:17
• I fixed a misprint. The second sum should end in $(x_1+1)$, not $(x_k+1)$ as my fingers had typed, apparently without consulting my brain. – Harald Hanche-Olsen Oct 14 '14 at 6:56
• To be more clear, I am saying that if the sequence $x_1,\ldots,x_k$ satisfy the given requirements, then so does $x_2,\ldots,x_k,(x_1+1)$. – Harald Hanche-Olsen Oct 14 '14 at 6:57
• I want to get it, but I don't ;( – Test Oct 14 '14 at 20:06
• I added an example to make it clearer. – Harald Hanche-Olsen Oct 14 '14 at 20:27

I don't know about an inductive proof, but here's a proof using the division algorithm.

For each integer $k = 1,…,n$, by applying the division algorithm we have $$n = kq + r$$ for unique integers $r \in [0,n-1]$ and $q \in [1,n]$. Now write a sum with $q$ occurrences of $k$, although the total is only $kq$; but then add $1$ to the last $r$ summands, so the total is now $n$. That gives exactly $n$ different summations as needed.

But we still have to show that these are the only possible summations. Suppose we are given a summation as described in the question. Let $q \in [1,n]$ be the number of terms in the summation. Let $r \in [0,n-1]$ be zero if the summands are all equal, and otherwise let $r$ be the number of larger summands. Let $k$ be the value of the smaller summand. Then clearly we have $n=kq+r$, and the summation is the same one constructed above.

• That's pretty great. but no idea how to do induction? – Test Oct 13 '14 at 23:51

You could study the following power series:

$\left(\sum_{k\geq 1}x^k\right)^n$ = $\sum_{x_1,x_2,...,x_n\geq 1\,}x^\left(x_1+x_2+...+x_n\right)$ = $\left(\sum_{k\geq 0, x_1+x_2+...+x_n=k}x^k\right)$ = $\sum_{k\geq 1}a_k*x^k$

Now $a_k$ is the number of ways you can write k as a sum of n integers: k= $k = x_1 + x_2 +...+x_n$ , with only strictly positive integers

So what we are looking for is $a_n$.

Youn calculate with cauchy product of series the value of $a_n$ (or $a_k$ more generally) and you get: $a_n$ = n

• With this approach, how to you account for the (rather severe) restrictions on the $x_k$? – Harald Hanche-Olsen Oct 13 '14 at 19:15
• Which one? The calculus is done on the $\left(\sum_{k\geq 0}x^k\right)^n$ = 1/$(1-x)^n$ = f(x) $a_n$ = $f^\left(n\right)$(0)/n! – mvggz Oct 13 '14 at 20:59
• The restrictions (after a moment's reflection) imply that among the numbers $x_1,\ldots,x_k$ are at most two distinct natural numbers, say $m$ and $m+1$ for some $m$. – Harald Hanche-Olsen Oct 14 '14 at 7:00
• In fact I've made a mistake, the sum of the $x^k$ should start at 1, not 0. Because none of the $x_k$ can be 0 according to the question. I'll correct that, and it should work. It's just that with this method I transform a problem of arithmetics and counting into a power series calculation where all you have to do is evaluate the coefficient of the $x^k$ – mvggz Oct 14 '14 at 7:31
• But doesn't your method also count sums like $1+4=5$, which is not supposed to be counted? I still think you are solving the wrong problem. – Harald Hanche-Olsen Oct 14 '14 at 7:59