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

  • $\begingroup$ have you tried something? why does your induction fail? $\endgroup$ – Exodd Oct 13 '14 at 18:28
  • 1
    $\begingroup$ Do you know something about "Generating Functions" ? $\endgroup$ – Dinesh Oct 13 '14 at 18:31
  • $\begingroup$ 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. $\endgroup$ – 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$.

  • $\begingroup$ one allowed way to write n+1 ? I'm also having trouble figuring out what the LHS and RHS would equal. $\endgroup$ – Test Oct 13 '14 at 22:17
  • $\begingroup$ 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. $\endgroup$ – Harald Hanche-Olsen Oct 14 '14 at 6:56
  • $\begingroup$ 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)$. $\endgroup$ – Harald Hanche-Olsen Oct 14 '14 at 6:57
  • $\begingroup$ I want to get it, but I don't ;( $\endgroup$ – Test Oct 14 '14 at 20:06
  • $\begingroup$ I added an example to make it clearer. $\endgroup$ – 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.

  • $\begingroup$ That's pretty great. but no idea how to do induction? $\endgroup$ – 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

  • $\begingroup$ With this approach, how to you account for the (rather severe) restrictions on the $x_k$? $\endgroup$ – Harald Hanche-Olsen Oct 13 '14 at 19:15
  • $\begingroup$ 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! $\endgroup$ – mvggz Oct 13 '14 at 20:59
  • $\begingroup$ 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$. $\endgroup$ – Harald Hanche-Olsen Oct 14 '14 at 7:00
  • $\begingroup$ 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$ $\endgroup$ – mvggz Oct 14 '14 at 7:31
  • $\begingroup$ 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. $\endgroup$ – Harald Hanche-Olsen Oct 14 '14 at 7:59

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.