# Strong Mathematical Induction Recursion Inequality

I have a question that is for a homework assignment and I just would like to ask if I seem to be on the right track or if I'm just doing it completely wrong.

Here is the question:

The sequence $\{a_n\}$ is defined by: $a_0 = 1$, $a_1 = 2$, $a_2 = 3$, and $a_n = a_{n-1} + 3a_{n-3} +3$ for all integers $n \geq 3$. Use strong mathematical induction to prove that $a_{n} \leq 2^{n}$ is true for all integers $n \geq 5$. Make sure you make reference to the fact that $n \geq 5$.

First off, here is what I calculated for the first few terms to get an idea. \begin{align*} a_{3} &= a_{2} + 3a_{0} + 3 = 3 + 3(1) + 3 = 9 \\ a_{4} &= a_{3} + 3a_{1} + 3 = 9 + 3(2) + 3 = 18 \\ a_{5} &= a_{4} + 3a_{2} +3 = 18 + 3(3) +3 = 30 \end{align*}

Here is my attempted solution:

For $n=5$, $a_{5} = a_{4} + 3a_{2} + 3 = 30$, for $n=6$, $a_{6} = a_{5} + 3a_{3} +3 = 60$, and finally for $n=7$, $a_{7} = a_{6} + 3a_{4} + 3 = 120$. By strong induction, assume that $a_{i} \leq 2^{i}$ for some $i$ in which $5 \leq i \leq k$, where $k \in \mathbb{Z}$. We want to prove that $a_{k+1} \leq 2^{k+1}$, meaning we want to show $a_{k} + 3a_{k-2} + 3 \leq 2 (2^{k})$. Provided that $k-2 \geq 5$, which it is, by our assumption we know that $a_{k-2} \leq 2^{k-2}$; which is that $a_{k-3} + 3a_{k-5} +3 \leq \frac{2^{k}}{4}$. Since, $a_{k+1} = a_{k} + 3a_{k-2} + 3 = a_{k} + 3(a_{k-3} + 3a_{k-5} +3) + 3$ ... and I have no idea where to go after this.

I've gone down a bunch of dead end roads and I see that there is a substitution available (I see the part of $a_{k-2}$ that I what to sub in of $a_{k+1}$ but I don't know how to make it work! Any tips would be appreciated. (Not looking for someone to just solve the problem for me).

--

I believe I have solved the proof, can you let me know if this looks better?

Proof: For $n=5$, $a_{5} = a_{4} + 3a_{2} + 3 = 30$ and $2^{5} = 32$, so $a_{5} \leq 2^{5}$ is true as $30 \leq 2^{32}$. Additionally, for $n=6$, $a_{6} = a_{5} + 3a_{3} +3 = 60$ and $2^{6} = 64$,so $a_{6} \leq 2^{6}$ is true as $60 \leq 64$. Finally for $n=7$, $a_{7} = a_{6} + 3a_{4} + 3 = 120$ and $2^{7} = 128$, so $a_{7} \leq 2^{7}$ is true as $120 \leq 128$. By strong induction, assume that $a_{i} \leq 2^{i}$ for all $i$ in which $5 \leq i \leq k$, where $k \in \mathbb{Z}$. We want to prove that $a_{k+1} \leq 2^{k+1}$, meaning we want to show $a_{k} + 3a_{k-2} + 3 \leq 2 (2^{k})$. Since in our basis step we have shown that $a_{7} \leq 2^{7}$, we can assume that $k \geq 7$, or in other words that $k-2 \geq 5$. Thus, by our assumption, we know that $a_{k-2} \leq 2^{k-2}$; and since we know that $k-2 \geq 5$ we can say $k \geq 5$, so we also know that $a_{k} \leq 2^{k}$. Then, \begin{align*} a_{k+1} &= a_{k} + 3a_{k-2} + 3\\ &\leq 2^{k} + 3(2^{k-2}) + 3 \\ &\leq 2^{k} + 4(2^{k-2}) - 2^{k-2} +3 \\ &\leq 2^{k} + 2^{k} - 2^{k-2} +3 \\ &\leq 2^{k} + 2^{k} \\ &\leq 2^{k+1} \end{align*} Observe that even in the minimal case when $k=5$, $-2^{k-2} +3 < 0$ as $- 2^{5-2} + = -4 < 0$, so $a_{k+1} \leq 2^{k+1}$, which was what we wanted to prove for the induction step. Therefore, by the Strong Principle of Mathematical Induction, for all integers $n \geq 5$, $a_{n} \leq 2^{n}$.

-
Since you mentioned this is homework, I added the corresponding tag. – Arturo Magidin Oct 30 '11 at 4:12
Please, do not add "solved" to the title. – Arturo Magidin Oct 30 '11 at 18:30
Rather than adding "solved" to the question, it's usually better to accept and answer by clicking the check mark next to it. – The Chaz 2.0 Oct 30 '11 at 18:31
The second $\leq$ is actually a $=$. The phrase "since we know that $k-2\geq 5$ we can say $k\geq 5$" is superfluous: you are already assuming $k\geq 7$. You need to justify that $-2^{k-2}+3\lt 0$ for the penultimate inequality, and you should not do this by saying "even in the minimal case." Instead, write something like "since $k\geq 7$, then $k-2\geq 5$, so $2^{k-2}\geq 2^5 \gt 3$, so $3-2^{k-2}\lt 0$" – Arturo Magidin Oct 30 '11 at 18:33

For strong induction your induction hypothesis should be that $a_k\le 2^k$ for all integers $k$ such that $5\le k < n$, and you’ll use this to deduce that $a_n\le 2^n$. Start with what you know about $a_n$: $$a_n = a_{n-1}+3a_{n-3}+3\;.\tag{1}$$ In order for this to be useful, you need to make sure that $n-3\ge 5$, so that you can apply your induction hypothesis to it. Thus, you’d better assume that $n\ge 8$. This is not a problem, because you can check by hand that $a_5\le 2^5,a_6\le 2^6$, and $a_7\le 2^7$; that is, in fact, your basis step for this argument.

Now go back to $(1)$ and apply your induction hypothesis: \begin{align*} a_n &= a_{n-1}+3a_{n-3}+3\\ &\le 2^{n-1}+3\cdot 2^{n-3}+3\;,\tag{2} \end{align*} and you’d like somehow to conclude that the expression in $(2)$ is at most $2^n$. Simply using the fact that $3<4=2^2$ almost works: \begin{align*} 2^{n-1}+3\cdot 2^{n-3}+3 &< 2^{n-1}+2^2\cdot 2^{n-3}+3\\ &= 2^{n-1}+2^{n-1}+3\\ &=2^n + 3\;; \end{align*} the only problem is that extra $+3$. But since we used a pretty estimate when we replaced $3$ by $4$ in the second term of $(2)$, and since that almost worked, we can reasonably hope that in fact $3\cdot 2^{n-3}+3\le 2^{n-1}$, which would be enough to make $2^{n-1}+3\cdot 2^{n-3}+3\le 2^n$.

The inequality $3\cdot 2^{n-3}+3\le 2^{n-1}$ can be written $3+\dfrac3{2^{n-3}}\le 4$, and you’re assuming that $n\ge 8$, so ...

-

Be sure to apply your inductive hypothesis. You can do something like this:

$a_k+3a_{k−2}+3\leq 2^k+3\cdot2^{k-2}+3$

Factor out $2^k$ and you can show that what remains is less than $2$.

Also note that when you say "for some $i$," you should say "for all $i$," and you must explicitly state that $k\geq 7$ so that you can use $a_{k-2}\leq 2^{k-2}$.

-

You don't have any (explicit) assumption on $k$ that allows you to assert that $k-2\geq 5$. You should note that the result is true for $k=5$, $k=6$, and $k=7$, (you never note that $a_5\leq 2^5$, for instance), and then you should explicitly say that you are assuming that $k\geq 7$.

Your induction assumption is that $a_k\leq 2^k$ and $a_{k-2}\leq 2^{k-2}$. So $$a_{k+1} = a_k + 3a_{k-2}+3 \leq 2^k + 3\times 2^{k-2} + 3.$$

As a hint: if you can show that $3(2^{k-2})+3\leq 2^k$, you'll be set. And $$3(2^{k-2}) = 4(2^{k-2}) - 2^{k-2} = 2^k -2^{k-2};$$ so...

-