From Concrete Mathematics, there is a problem called Lines in the Plane on Page 7... At one point the recurrence is described like so:
$L_n = L_{n-1} + n$
I'm not clear on how this gets accomplished during the conversion to closed form:
$L_{n-1} + n = (\frac{1}{2}(n-1)n+1) = \frac{1}{2}n(n+1)+1$
This is described as "the key induction step"...
I've looked back through my algebra notes regarding FOIL, polynomials, etc. but I'm not finding the term/method for working this out.
Any ideas?
At that point the authors have explained why $L_n$ satisfies the recurrence
$$L_n=L_{n-1}+n$$
for $n>0$, with $L_0=1$, and are proving by induction on $n$ that this implies that
$$L_n=\frac12n(n+1)+1\tag{1}$$
for each $n\ge 0$. The base case of the induction, which they don’t bother to mention, is the $n=0$ case, and indeed
$$\frac12\cdot0\cdot(0+1)+1=1=L_0\;.$$
Now they carry out the induction step: they assume that $(1)$ holds for $n-1$ and use the recurrence to show that in that case it necessarily holds for $n$ as well. For $n-1$ the closed form $(1)$ gives
$$L_{n-1}=\frac12(n-1)\big((n-1)+1\big)+1=\frac12(n-1)n+1=\frac12n(n-1)+1\;,$$
so the recurrence tells us that
$$\begin{align*} L_n&=L_{n-1}+n\\ &=\frac12n(n-1)+1+n\\ &=\frac{n^2}2\color{crimson}{-\frac{n}2}+1+\color{crimson}n\\ &=\frac{n^2}2\color{crimson}{+\frac{n}2}+1\\ &=\frac12(n^2+n)+1\\ &=\frac12n(n+1)+1\;. \end{align*}$$
We can now conclude by induction that $(1)$ holds for all $n\ge 0$.