How many ways are there to express a natural as a sum of 3 others—but by induction? I have figured out an (inductive?) process, but I cannot express it formally: There is always one possibility where $n$ is in the first place of our 3-tuple: $[n~~0~~0]$. Then I can subtract $k~(\leq n)$ from $n$, and distribute it between the two other spots. For that I have $k+1$ options (from $[k~~0]$ to $[0~~k]$). Since $k$ can range from $0$ to $n$, I have $\sum_{k=1}^{n+1}k$ possibilities. > Exempli gratia: > > For $1$ there are $ \begin{bmatrix} 1 & 0 & 0 \\\ 0 & 1 & 0 \\\ 0 & 0 & 1 \end{bmatrix} $ 3 possibilities. The two "parts" are $[1~|~0~~0]$ and $\left[ \begin{array}{c|cc} 0 & 1 & 0 \\\ 0 & 0 & 1 \end{array} \right]$. The problem is, that if I use the above formula for induction, I would simply be proving Gauss' formula. It just doesn't feel like correct induction.

Well, the number of ways to write $m$ as $a+b$ are clearly $m+1$, ranging from $0+(m)$ to $(m)+0$.

So the number of ways to write $n$ as $a+b+c$ are given by: $$ \sum_{c=0}^{n}(n-c+1)=\sum_{d=0}^{n}(d+1)=\sum_{k=1}^{n+1}k $$ by setting $d=n-c$ and $k=d+1$.