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.

  • 2
    $\begingroup$ Use LaTex to format your equation! $\endgroup$ Jan 3 '13 at 2:37
  • 1
    $\begingroup$ Watch it: the recurrence in the link you gave has a minus where you put a plus...! $\endgroup$
    – DonAntonio
    Jan 3 '13 at 2:37
  • 3
    $\begingroup$ 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". $\endgroup$
    – amWhy
    Jan 3 '13 at 2:46
  • 1
    $\begingroup$ Welcome to Math.SE. You may find this LaTeX tutorial helpful. $\endgroup$
    – 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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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