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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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_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|cite|improve this question
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

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|cite|improve this answer

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|cite|improve this answer

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|cite|improve this answer

Your Answer


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.