# Strong mathematical induction: Prove Inequality for a provided recurrence relation $a_n$

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

• Please check to be sure that I interpreted all of the mathematical expressions correctly. – Brian M. Scott May 24 '13 at 17:58
• Yes you did, thank you for editing it for me =) @BrianM.Scott – Jamie May 24 '13 at 17:58
• You’re welcome. – Brian M. Scott May 24 '13 at 18:05

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

• That actually makes sense, thank you – Jamie May 24 '13 at 18:11
• @Jamie: You’re welcome. – Brian M. Scott May 24 '13 at 18:14

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)

• U are welcome. :) – Abhra Abir Kundu May 24 '13 at 18:14