Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

(original image)

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

share|improve this question
2  
Use LaTex to format your equation! –  ncmathsadist Jan 3 '13 at 2:37
1  
Watch it: the recurrence in the link you gave has a minus where you put a plus...! –  DonAntonio Jan 3 '13 at 2:37
3  
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
1  
Welcome to Math.SE. You may find this LaTeX tutorial helpful. –  user53153 Jan 3 '13 at 2:49
add comment

3 Answers

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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