<s>[INST] Sum of the first $n$ triangular numbers - induction Question:
Prove by mathematical induction that $$(1)+(1+2)+(1+2+3)+\cdots+(1+2+3+\cdots+n)=\frac{1}{6}n(n+1)(n+2)$$ is true for all positive integers n.
Attempt:
I did the the induction steps and I got up to here:
$$RTP:\frac{1}{6}n(n+1)(n+2)+(1+2+3+\cdots+n+(n+1))=\frac{1}{6}(n+1)(n+2)(n+3)$$
Where do I go from here?
Thank you very much.
 [/INST] You can use two nested inductions.
In order to show the equality $\forall n, 1 + (1+2) + (1+2+3) + \ldots (1+2+\ldots+n) = \frac 1 6 n (n+1) (n+2)$,
you check that it is true for $n=1$, and then you are left to show the equality $\forall n, \frac 1 6 n (n+1) (n+2) + (1+2+ \ldots+n+(n+1)) = \frac 1 6 (n+1) (n+2) (n+3)$,
which can be simplified to $\forall n, (1+2+ \ldots +n+(n+1)) = \frac 1 6 (n+1) (n+2) [(n+3)-n] = \frac 1 2 (n+1) (n+2) $.
Now, you use induction again to prove this. You check that it is true for $n=1$, and are left to show the equality $\forall n, \frac 1 2 (n+1)(n+2) + (n+2) = \frac 1 2 (n+2)(n+3)$. Which should be straightforward to prove.

Alternately you can use a single strong induction : check that it is true for $n=0,1$, and for $n\ge 1$, assume the equality is true for $n-1$ and $n$, and show that it is true for $n+1$, by using $1 + (1+2) + (1+2+3) + \dots + (1+2+\ldots n+1) = 2*(1 + (1+2) + \ldots (1+2+\ldots + n)) - (1+(1+2) + \ldots + (1+2+\ldots +(n-1)) + (n+1)$.
Replace everyone with the corresponding $\frac 1 6 k(k+1)(k+2)$, and then it should be straightforward.
</s>