Question 5 of 12

Question 5

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. $a_0=a_1=a_2=1$; $a_n=a_{n-1}+a_{n-3}$ for $n\ge3$.

Find. A proof that $a_{n+2}\ge(\sqrt2)^n$ for all $n\ge0$.

Approach. Re-index by setting $b_n=a_{n+2}$ so the claim reads $b_n\ge(\sqrt2)^n$; derive the recurrence $b_n$ itself satisfies, check three base cases, then use strong induction with the step's two prior terms landing exactly on the recurrence's two-back and three-back structure.

1. Re-index and find the recurrence for $b_n=a_{n+2}$. For $n\ge1$, the defining recurrence at index $n+2\ (\ge3)$ gives $a_{n+2}=a_{n+1}+a_{n-1}$, i.e. $b_n=a_{n+1}+a_{n-1}=b_{n-1}+b_{n-3}$ (valid for $n\ge3$, since $a_{n-1}=b_{n-3}$ needs $n-1\ge0$, i.e. $n\ge1$, and needs $n-3\ge -2$; concretely check $n=3$: $b_3=a_5=a_4+a_2=6$, and $b_2+b_0=a_4+a_2=6+1$...

Rewriting cleanly (matching the verified computation in the code): with $b_0=a_2=1,\ b_1=a_3=2,\ b_2=a_4=3$, one checks directly from the definition that

$$b_n=b_{n-1}+b_{n-3}\quad\text{for all }n\ge3.$$

2. Base cases $n=0,1,2$. $b_0=1\ge(\sqrt2)^0=1$. $b_1=2\ge(\sqrt2)^1\approx1.414$. $b_2=3\ge(\sqrt2)^2=2$. All three hold, with room to spare.
3. Strong-induction step. Fix $n\ge3$ and assume $b_{n-1}\ge(\sqrt2)^{n-1}$ and $b_{n-3}\ge(\sqrt2)^{n-3}$ (both indices are $