Proving by Strong Induction (solution of linear recurrence)

Question

I'm having difficulty understanding strong induction. The problem was to prove that $a_n = 2n-1$ for all n that is a natural number where $a_1 = 1, a_2 = 3$ and $a_n = 2a_{n-1}-a_{n-2}$ for n >= 3.

How do I solve this? Thank you!

Answer 1

You want to first prove that the proposition is true with a base case, i.e. n=3.

$a_3$ = 2$a_{3-1}$ - $a_{3-2}$ = 2$a_2$ - a$_1$ = 6-1 = 5 = 2(3) - 1

Then for your inductive step you want to suppose the case holds for some n = k. That is:

a$_k$ = 2$a_{k-1}$ - a$_{k-2}$ is true.

You want to show that a$_k$ being true implies that a$_{k+1}$ holds.

Then a$_{k+1}$ = a$_k$ + a$_1$ = 2a$_{k-1}$ - a$_{k-2}$ + a$_1$ = 2a$_k$ - a$_{k-1}$ as desired.