2
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ But it doesn't hold for $n = 0$ or $n = 1$? $\endgroup$
    – Tree Garen
    Commented Dec 1, 2018 at 8:01
  • $\begingroup$ 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$. $\endgroup$ Commented Dec 1, 2018 at 8:06
  • $\begingroup$ 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? $\endgroup$
    – Tinler
    Commented Dec 1, 2018 at 8:14
  • $\begingroup$ 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$. $\endgroup$ Commented Dec 1, 2018 at 8:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .