The sequence $a_1,a_2,a_3,\dots$ is defined by: $a_1=1$, $a_2=1$, and $a_n=a_{n-1}+a_{n-2}-n+4$ for all integers $n\ge 3$. Prove using strong mathematical induction that $a_n\ge n$ for all integers $n\ge 3$.
I'm comfortable solving questions that require mathematical induction but I always struggle with strong mathematical induction. I've read the steps provided in my textbook and looked at examples but I still don't get it
On
Take a $m>1\in N$. In the strong form of mathematical induction you consider that $\forall n<m,n\in N$ the given proposition is true (of course after proving it for first few initial cases though it is enough to prove it for the first case) and then you go on to prove it for $m$.
Similarly in this case.
$a_3=1+1-3+4=3\ge 3$
Now you consider it to be true for $n\in N.n\le k$. Using this hypothesis we will prove it for $n=k$.
$a_k=a_{k-1}+a_{k-2}-k+4\ge (k-1)+(k-2)-k+4=k+1>k$(using the fact that $a_{k-1}\ge k-1 ,a_{k-2}\ge k-2$. Note that these are from the hypothesis)
The only difference is that strong induction gives you more to work with at the induction step: you get to assume that the result is true for all smaller values of $n$, not just for the immediately preceding value.
Here your induction hypothesis should be that $n>4$ and that $a_k\ge k$ for all integers $k$ such that $3\le k<n$, and the induction step is then to prove from this that $a_n\ge n$. As it happens, you don’t even need the full strength of the induction hypothesis: you need only that $a_{n-1}\ge n-1$ and $a_{n-2}\ge n-2$. From these you can argue that
$$a_n=a_{n-1}+a_{n-2}-n+4\ge(n-1)+(n-2)-n+4=n+1>n\;.$$
This is actually more than you were asked to show, but that’s okay: if $a_n>n$, then certainly $a_n\ge n$.
Note that the induction step does require knowing the result for the next two smaller values, $n-1$ and $n-2$, so you have to start with an $n$ that’s at least $5$, and your basis step has to verify two things, namely, that $a_3\ge 3$ and that $a_4\ge 4$.