Proof-verification exercise problem

Question

Let $a_1=2$, $a_2=4$, and define for $n > 2$, $n$ a natural number:

$$a_n=\:a_{n-1}+2a_{n-2}$$

How to prove that $a_n\:\ge \:2^n$ is always true?

When n = 3

$$a_3=a_{3-1}+2a_{3-2}\:=a_2\:+2a_1=4\:+2\cdot 2=8$$ $$2^3=8$$

when n +1

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

Answer 1

Assuming that $a \ge 0$:

Start of indudction: n = 3

$$a_3 = a_2 + 2a_1 = 4 + 2*2 = 8 \ge 2^3$$

Thus

$$a_n \ge 2^n$$

for an $n \in \mathbb{N}$.

Induction Step: $n \rightarrow n+1$

$$a_{n+1}=a_n + 2a_{n-1}$$

Since $$a_n \ge 2^n$$

$$\Rightarrow a_n + 2a_{n-1}\ge 2^n $$

Answer 2

The associate caracteristic equation is

$x^2-x-2=0$ which has $x=-1$ and $x=2$ as solutions.

thus

$u_n=a(-1)^n+b(2)^n$.

with

$-a+2b=u_1=2$ and $a+4b=u_2=4$

so $b=1$ and $a=0$.

thus, we get

$u_n\color{red}{=}2^n$ for each integer $ n$.