# Mathematical induction proof; $g_k=3g_{k-1} - 2g_{k-2}$

Can someone help me with this problem? I'm having a hard time proving this. It's been a long time since I have done mathematical proofs.

Suppose that $g_1,\ g_2,\ g_3,\ \ldots$ is a sequence of integers defined as follows:

$g_1=3$
$g_2=5$
$g_k=3g_{k-1} - 2g_{k-2}$ for all integers $k\geq 3$.

Prove that $g_n=2^n+1$ for every integer $n\geq 1$.

Looking at the problem, it looks like I would want to use induction.

-
Use LaTex to format your equation! –  ncmathsadist Jan 3 '13 at 2:37
Watch it: the recurrence in the link you gave has a minus where you put a plus...! –  DonAntonio Jan 3 '13 at 2:37
Here are some instructive examples of proof by induction, that help clarify how one generally approaches a proof by induction. That may help "clear cobwebs". –  amWhy Jan 3 '13 at 2:46
Welcome to Math.SE. You may find this LaTeX tutorial helpful. –  user53153 Jan 3 '13 at 2:49

For $\,k=1,2\,$ it is given , so assume it's true for any $\,k<n\,$ and we shall show for $\,k=n\,$:

$$g_n:=3g_{n-1}-2g_{n-2}\stackrel{\text{Ind. hypothesis}}=3(2^{n-1}+1)-2(2^{n-2}+1)=$$

$$=3\cdot 2^{n-1}-2^{n-1}+3-2=2\cdot 2^{n-1}+1$$

and we're done.

-

Induction Step:

$\begin{array}{lll} g_{n+2}& = & 3\cdot g_{n+1}-2\cdot g_n\\ & = & 3\cdot(2^{n+1}+1)-2\cdot(2^n +1)\\ & = & 3\cdot(2\cdot 2^n +1)-2\cdot(2^n+1) \\ & = & 2\cdot 2^n\cdot(3-1) +(3-2) \\ & = & 2^{n+2}+1. \end{array}$

-

Using this, $g_k=Aa^k\implies Aa^{k-2}(a^2-3a+2)=0$

For non-trivial solution $Aa\ne 0\implies a^2-3a+2=0\implies a=1,2$

So, $g_k=B2^k+C1^k=B2^k+C$ where $B,C$ are arbitrary constants.

$3=g_1=2B+C$ and $5=4B+C\implies B=C=1\implies g_k=2^k+1$

-