The sequence $ \{a_n\}_{n=0}^{\infty} $ is recursively defined by $ a_0 = 0 $, $a_1 = 1 $, $a_2 = 4 $ and $a_n = a_{n-1} + a_{n-3} - n^2 + 8n - 10$ for $ n \geq 3 $.
Prove using induction or strong induction that $ a_n = n^2 $ for all $n \in \mathbb{N} .$
$--------------------------------------$
I want to show that it's true with strong induction.
I would say in my IH: Assume that the formula $ a_n = n^2 $ is true for all values of n, where $ 0 \leq n \leq k $ and where $ k \geq 3 $. Want to show that it's true for $ k + 1$, that is $a_{k+1} = (k+1)^2 $
Would this be a correct way to formulate my IH?
or would this be better: Assume that the formula, $ a_n = n^2 $ , is true for $ 0, 1 ,2, ... ,k-3, k-2, k-1, k$ where $k \geq 3$ and want to show it's true for $ k + 1$, that is $a_{k+1} = (k+1)^2 $
Im thankful for all the help I can get.
Here we use a slightly different, though equivalent, induction hypothesis from the one you defined. Let the predicate $P(n)$ be $a_n = n^2$. We have that $a_0 = 0$, $a_1 = 1$ and $a_2 = 4$ and so the three base cases $n = 0,1,2$ hold. We now assume $P(k)$ holds for all $k < n$ and prove that $P(n)$, $n > 2$, holds:
$$ a_n = a_{n - 1} + a_{n - 3} - n^2 + 8n - 10 $$ $$ = (n - 1)^2 + (n - 3)^2 - n^2 + 8n - 10 $$ $$ = n^2 + 1 - 2n + n^2 + 9 - 6n - n^2 + 8n - 10 $$ $$ = n^2 + 1 - 2n + 9 - 6n + 8n - 10 $$ $$ = n^2 - 2n - 6n + 8n $$ $$ = n^2 $$
and so by strong induction $P(n)$ holds for all naturals $n \in \mathbb{N}$. This implies $a_n = n^2$ is indeed a solution to the given recurrence.