# 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! Jan 3 '13 at 2:37
• Watch it: the recurrence in the link you gave has a minus where you put a plus...! 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". 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$