<s>[INST] 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?
 [/INST] 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$.
</s>