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?
 A: 
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}$$
A: Uhm.. It's awkward.. Let me try to explain:
Induction is done on propositions. Let $P(n)$ be a particular proposition you want to prove (indexed by a natural number $n$). If you prove $P(0)$ is true and that $P(n) \implies P(n+1)$, then by induction you proved $P(n)$ for every natural number $n$.
What is your proposition in this case? It seems to me that you want to find a solution to the recurrence relation $$L_n = L_{n-1}+1$$
You want to check wether the ansatz $$L_n = \frac{n(n+1)}2 +1$$ is a solution to said recurrence relation.
You can just plug it in: if $L_n = \frac{n(n+1)}2 +1$, then $L_{n-1} = \frac{n(n-1)}2 + 1$ and the relation holds. (QED)
There is no proposition on $n$ to make induction on. If we want to find one, we can say: "Let $L_n = \frac{n(n+1)}2 +1$, and let $P(\bar n)$ = "This relation holds: $L_{\bar n} = L_{\bar n-1}+1$"
You want to prove that $P(n)$ is true for every $n$
You can say:  $P(1)$ is true. So if I show that $P(n) \implies P(n+1)$ I'm done. Which is true, but it's weird: you can prove $P(n)$ instantly for every $n$ just by plugging the ansatz into the equation, why would you follow such a complicated (and more difficult) route?
A: The induction schema is (base) $P(0)$ is true (might start elsewhere too), (induction) if $P(n)$ is true, we prove $P(n + 1)$ is true, (conclusion) $P(n)$ is true for all $n \in \mathbb{N}_0$.
You have to work from $P(n)$ to $P(n + 1)$ somehow.
In your case, the claim is that $L_n = n (n + 1) / 2 + 1$.
Base: For $n = 0$ you have that $L_0 = 1$ by definition, and the formula gives $\frac{0 (0 + 1)}{2} + 1 = 1$. This is true.
Induction: By hypothesis, for $n$ we have:
$\begin{align}
  L_n = \frac{n (n + 1)}{2} + 1
\end{align}$
We know that:
$\begin{align}
  L_{n + 1}
    &= L_n + n + 1 \\
    &= \frac{n (n + 1)}{2} + 1 + n + 1\\
    &= \frac{(n + 2) (n + 1)}{2} + 1
\end{align}$
(the first step by the definition of $L_{n + 1}$, the second one uses the induction hypothesis, then just algebra)
This is the claim for $n + 1$, as we wanted to prove.
Conclusion: By induction, the claim is true for all $n \ge 0$.
