Now am I doing induction correctly? Recursion: $L_n = L_{n-1} + n$ where $L_0 = 1$.
We guess that solution is $L_n = \frac{n(n+1)}{2} + 1$.
Base case: $L_0 = \frac{0(0+1)}{2} + 1 = 1$ is true.
Inductive step: Assume $L_n = \frac{n(n+1)}{2} + 1$ is true for some $n$. We will show that $L_{n+1} = \frac{(n+1)(n+2)}{2} + 1$ given that $L_n = L_{n-1} + n$ is true.
$L_{n+1} = \frac{(n+1)(n+2)}{2} + 1 = L_n + (n+1)$
$L_n = \frac{(n+1)(n+2)}{2} + 1 - (n+1)$
$L_n = \frac{(n+1)(n+2)}{2} + \frac{2}{2} - \frac{2n+2}{2} = \frac{n^2+3n+2 + 2 - 2n - 2}{2}$
$L_n = \frac{n^2+n+2}{2} = \frac{n^2+n}{2} + 1 = \frac{n(n+1)}{2} + 1$
This completes the proof.
Is everything in place for a correct induction proof? Is anything wrong? Backwards? Unclear? Awkward?


Base case: $L_0 = \frac{0(0+1)}{2} + 1 = 1$ is true.
Inductive step: Assume $L_n = \frac{n(n+1)}{2} + 1$ is true for some $n$. We will show that $L_{n+1} = \frac{(n+1)(n+2)}{2} + 1$ given that $L_n = L_{n-1} + n$ is true.

Fine.

$L_{n+1} = \frac{(n+1)(n+2)}{2} + 1 = L_n + (n+1)$

Don't start with $L_{n+1}=\frac{(n+1)(n+2)}{2}+1$ which is what you have to prove.

$$\begin{align}L_{n+1}&=L_n+n+1\\&=\frac{n(n+1)}{2}+1+n+1\\&=\frac{n(n+1)}{2}+\frac{2(n+1)}{2}+1\\&=\frac{n+1}{2}(n+2)+1\\&=\frac{(n+1)(n+2)}{2}+1\end{align}$$
