Now am I doing induction correctly?

Question

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 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.

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

Answer 2

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?

Answer 3

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