number theory - 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?

Answer

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}$$