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