Proving a sequence by induction

Question

Trying to prove by induction in a non-math course and I feel like I'm getting the steps but I'm just stuck on the math.

$$G_1 = 1$$

$$G_2 = 1$$

$$G_n = 2G_{n−1} + 3G_{n−2}, \quad n \geq 3$$

Using mathematical induction, prove that for every $n ≥ 1$, $G_n ≤ 3^n$.

I used $G_1$ as my base case, since it’s given.

My induction hypothesis is to assume $G_n \leq 3^n$ for some arbitrary $n$. Thus I should prove $G_{n+1}\leq 3^{n+1}$.

Using the given formula I simplified down to $2G_n + 3G_{n-1} ≤ 3^n3$.

I feel like I'm pretty much there, but I just don't see how to solidify the proof from here. Any hints would be greatly appreciated!

Answer 1

$$G_1 = 1$$

$$G_2 = 1$$

$$G_n = 2G_{n−1} + 3G_{n−2}, n \geq 3$$

"My induction hypothesis is to assume $G_n \leq 3^n$ for some arbitrary $n$. Thus I should prove $G_{n+1}\leq 3^{n+1}$.

Using the given formula I simplified down to $2G_n + 3G_{n-1} ≤ 3^n * 3$."

Now, notice this means $$G_{n+1} = 2G_{n} + 3G_{n−1}\leq3^n*3=3^{n+1}$$ You have your desired result.

Answer 2

Suppose $g_n =ag_{n-1}+bg_{n-2} $ where $a, b > 0$.

We want to find a condition on $r$ such that $g_{n-1} \le r^{n-1}$ and $g_{n-2} \le r^{n-2}$ implies that $g_{n} \le r^{n}$.

If $g_{n-1} \le r^{n-1}$ and $g_{n-2} \le r^{n-2}$, then $g_n =ag_{n-1}+bg_{n-2} \le ar^{n-1}+br^{n-2} = r^n(a/r+b/r^{2}) $.

So it is sufficient if $(a/r+b/r^{2}) \le 1$ or $ar+b \le r^2$.

Manipulating this, $r^2-ar+a^2/4 \ge b+a^2/4$ or $(r-a/2)^2 \ge b+a^2/4$ or $r \ge a/2 +\sqrt{b+a^2/4} $. (This should look familiar.)

In your case, with $a=2$ and $b=3$, this gives $r \ge 1+\sqrt{3+1} =3 $.

This leads to the characteristic equation of a linear recurrence. Look it up.

Answer 3

You should use “complete induction”: assuming the thesis for all $m<n$, for $n>2$, prove it for $n$.

The cases $G_1$ and $G_2$ should be provided separately: $$ G_1=1\le 3^1,\qquad $G_2=1\le 3^2 $$ are OK.

Now assume the thesis holds for all $m<n$, with $n>2$. Then $$ G_n=2G_{n-1}+3G_{n-2}\le 2\cdot 3^{n-1}+3\cdot 3^{n-2} $$ because, by inductive hypothesis, $G_{n-1}\le 3^{n-1}$ and $G_{n-2}\le 3^{n-2}$. Now you should be able to finish up.

Note that $n>2$ is needed for the argument, so the cases $n=1$ and $n=2$ must be provided separately in order to start the induction.