Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

3 Answers 3

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

share|improve this answer

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.