# Proving a sequence by induction [duplicate]

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!

• $3^n * 3 = 3^{n+1}$ Commented Apr 4, 2018 at 18:48
• And $2G_n + 3G_{n-1}=G_{n+1}$ Commented Apr 4, 2018 at 18:48
• math.stackexchange.com/questions/2715489/… Commented Apr 4, 2018 at 18:51
• @labbhattacharjee This is still the old link with Fibonacci and $7/4$:) Commented Apr 4, 2018 at 18:56

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.

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

• But I got to where I'm stuck by using the equivalencies you just pointed out. Isn't that begging the question if I were to stop there? Commented Apr 4, 2018 at 19:28
• You are using what the question has given you and the induction hypothesis that you made. Consequently you have proven the induction step, so you can use the principles of induction to draw your conclusion. This is not begging the question(just state: my the principles of mathematical induction,......) Commented Apr 4, 2018 at 21:32

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.