0
$\begingroup$

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!

$\endgroup$

marked as duplicate by Dietrich Burde, Donald Splutterwit, A. Goodier, Namaste, user223391 Apr 7 '18 at 3:45

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – B. Mars Apr 4 '18 at 19:28
  • $\begingroup$ 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,......) $\endgroup$ – Jesse Meng Apr 4 '18 at 21:32
0
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.