Sum of the first $n$ triangular numbers - induction

What you’ve really done up to this point is use your induction hypothesis to say that

$$(1)+(1+2)+\ldots+(1+2+\ldots+n)+\big(1+2+\ldots+n+(n+1)\big)$$

is equal to

$$\frac16n(n+1)(n+2)+\big(1+2+\ldots+n+(n+1)\big)\;.$$

To finish the induction step you must show that this quantity is equal to

$$\frac16(n+1)(n+2)(n+3)\;,$$

i.e., that

$$\frac16n(n+1)(n+2)+\big(1+2+\ldots+n+(n+1)\big)=\frac16(n+1)(n+2)(n+3)\;.\tag{1}$$

In order to do this, you need a nice closed form for the term

$$1+2+\ldots+n+(n+1)\;.$$

I’m sure that by this point you’ve learned a closed form for the sum of the first $m$ consecutive integers; substitute that (with $m=n+1$) for $1+2+\ldots+n+(n+1)$ on the lefthand side of $(1)$, and do some algebra to show that the quantity on the lefthand side then really does simplify to the quantity on the righthand side.

$$\frac{1}{6}n(n+1)(n+2)+(1+2+3+\cdots+n+1)=$$

$$=\frac{1}{6}n(n+1)(n+2)+\frac{(n+1)(n+2)}{2}=$$ $$=\frac{1}{6}n(n+1)(n+2)+\frac{3(n+1)(n+2)}{6}=$$

$$=\frac{1}{6}(n+1)(n+2)(n+3)$$

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.