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