# Use complete induction to prove that $a_n < 2^n$ for every integer $n \geq 2$

Define the sequence of integers $$a_0, a_1, a_2, \cdots$$ as follows

$$a_i = \begin{cases} i+1 & 0 \leq i \leq 2 \\ a_{i-1} + a_{i-2} + 2a_{i-3} & i > 2 \\ \end{cases}$$

Use complete induction to prove that $$a_n < 2^n$$ for every integer $$n \geq 2$$

I will prove $$a_n < 2^n, \forall n \geq 2$$ by using complete induction

Base Case: Three cases $$n = 2, 3, 4$$

let $$n = 2$$

$$a_{n} = a_{2} = 2 + 1 = 3 < 4 = 2^2 = 2^n$$ By definition, and holds

let $$n = 3$$

$$a_{n} = a_{3} = 3 + 2 + 1 = 6 < 8 = 2^3 = 2^n$$ By definition, and holds

let $$n = 4$$

$$a_{n} = a_{4} = 4 + 3 + 2 = 9 < 16 = 2^4 = 2^n$$ By definition, and holds

Inductive step: let $$n > 4$$. Suppose $$a_j < 2^j$$ whenever $$2 \leq j < n$$. [Inductive hypothesis]

What to prove: $$a_n < 2^n$$

$$a_{n} = a_{i-1} + a_{i-2} + 2a_{i-3}$$ [By definition]

$$< 2^{n-1} + 2^{n-2} + 2^{n-3+1}$$ [By Inductive hypothesis]

$$= 2^{n-1} + 2^{n-2} + 2^{n-2}$$

$$= 2^{n-1} + 2^{n-2 + 1}$$

$$= 2^{n-1 + 1}$$

$$= 2^n$$

as wanted.

Would this be correct?

The second part is fine. But the base case is not just the $$n=2$$ case. You should have checked it for $$n=0$$, and $$n=1$$ too.
• But it doesn't hold for $n = 0$ or $n = 1$? Commented Dec 1, 2018 at 8:01
• You are right. My mistake. But the you should have checked it for $n\in\{2,3,4\}$. Because only then will your inductive proof shows that it works for $n=5$. Commented Dec 1, 2018 at 8:06
• I'm confused why. Why three numbers? And I thought the base case for recurrence functions was just so we can use "$a_{i-1} + a_{i-2} + 2a_{i-3}$" part but that part holds for all $i > 2$ so wouldn't going all the way to $n = 5$ be redundant? Commented Dec 1, 2018 at 8:14
• Three numbers because each $a_i$ is defined from the three previous terms. So, in order to prove it it holds for $a_5$, you must know that it holds for $a_2$, $a_3$, and $a_4$. Commented Dec 1, 2018 at 8:26