3
$\begingroup$

Let the sequence $G_0, G _1, G_2, ...$ be defined recursively as follows:

$G_0=0, G_1=1,$ and $G_n=5G_{n-1}-6G_{n-2}$ for every $n\in\mathbb{N}, n\ge2$.

Prove that for all $n\in\mathbb{N}$, $G_n=3^n-2^n$.

Proof. By strong induction. Let the induction hypothesis, $P(n)$, be $G_n=3^n-2^n$

Base Case: For $(n=0)$, $P(0)$ is true because $3^0-2^0 =0$

For $(n=1)$, $P(1)$ is true because $3^1-2^1=1$

Inductive Step: Assume that $P(n-1)$ and $P(n-2)$, where $n\ge2$, are true for purposes of induction.

So, we assume that $G_{n-1}=3^{n-1}-2^{n-1}$ and $G_{n-2}=3^{n-2}-2^{n-2}$, and we must show that $G_{ n }=3^{ n }-2^{ n }$.

Since we assumed $P(n-1)$ and $P(n-2)$, we can rewrite $G_n=5G_{n-1}-6G_{n-2}$ as $G_n=5(3^{n-1}-2^{n-1})-{ 6 }(3^{n-2}-2^{n-2})$

So, we get:

$\Rightarrow G_n=5\cdot 3^{ n-1 }-5\cdot 2^{ n-1 }-(\frac { 6 }{ 3 } \cdot 3^{ n-1 }-\frac { 6 }{ 2 } \cdot 2^{ n-1 })$

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

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

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

$\Rightarrow G_n=\frac { 1 }{ 3 } \cdot 3\cdot 3^n-\frac { 1 }{ 2 } \cdot 2\cdot 2^n$

$\Rightarrow G_n=3^n-2^n$

The only real issue I have at this point is that I don't know how to properly conclude this proof with a final statement. A hint/guidance in that regard would be much appreciated.

In addition, please feel free to offer advice and/or constructive criticism about my proof.

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ It looks great, you have effectly showed that if the property $G_{i}=3^i-2^i$ holds for $i\in\{1,2,\dots n-1\}$ then $G_{n}=3^n-2^n$ also. $\endgroup$ – Jorge Fernández-Hidalgo Aug 3 '16 at 17:12
  • 1
    $\begingroup$ In your description of $P(n)$, the part "for all $n$ $\dots$" is at best superfluous, and at worst confusing or incorrect. Better, for any integer $k\ge 0$ let $P(k)$ be the assertion $G(k)=3^k-2^k$. $\endgroup$ – André Nicolas Aug 3 '16 at 17:32
  • 1
    $\begingroup$ Not necessary. But the deletion of "for all $n$ $\dots$" is. $\endgroup$ – André Nicolas Aug 3 '16 at 17:47
  • 1
    $\begingroup$ @Cherry Thanks for the link. I see that they state strong induction with a base case P(0). But often we don't need base case(s) for strong induction and the induction principle can be stated without any. For example, every integer > 1 is a product of primes. Suppose for induction it is true for all naturals < n. If n is prime we are done, else n is composite so it is a product of smaller naturals n = ab so by induction a,b are products of primes. Appending their products shows that n is a product of primes. No base case! $\endgroup$ – Bill Dubuque Aug 3 '16 at 18:05
  • 1
    $\begingroup$ The assertion $P(n)$ is not the assertion that $G(n)=3^n-2^n$ for all $n$. If we write the latter in symbols, it is $\forall n(G(n)=3^n-2^n)$. Now $n$ is a "dummy variable" which gets quantified out. We want that for any particular $n$, $P(n)$ is the assertion $\dots$. $\endgroup$ – André Nicolas Aug 3 '16 at 18:12
1
$\begingroup$

You have the right idea, but there are some minor points that need correction.

The strong induction principle in your notes is stated as follows:

Principle of Strong Induction $\ $ Let $\,P(n)\,$ be a predicate. If

  • $\ P(0)$ is true, and

  • for all $\,n\in \Bbb N,\ P(0), P(1),\ldots, P(n)\,$ together imply $\,P(n\!+\!1)\,$ then $\,P(n)\,$ is true for all $\,n\in\Bbb N$

Your $\,P(n)\,$ is $\, G_n = 3^n - 2^n.\,$ You have verified that $\,P(0)\,$ is true.

Your induction hypothesis is that $\,P(k)\,$ is true for all $k \le n.\,$ You have essentially shown that $\,P(n\!-\!1),P(n)\,\Rightarrow\,P(n\!+\!1)\,$ but that only works for $\,n\ge 1$ (else $\,P(n-1)\,$ is undefined). Thus you need to separately verify $\,P(1)\,$ (to be pedantic, this is part of the inductive step, not the base case, according to the above formulation of strong induction, though that is a somewhat arbitrary distinction)

It is illuminating to observe that the recurrence in the induction is a special case of

$$ a^{n+1}-b^{n+1} =\, (a+b)(a^n-b^n) -ab (a^{n-1} - b^{n-1})$$

which can be verified directly or derived from the fact that $\,a,b\,$ are roots of

$$(x\!-\!a)(x\!-\!b) = x^2\! - (a\!+\!b) x + ab\,\Rightarrow\, x^{n+1}\! = (a\!+\!b)\,x^n - ab\, x^{n-1}$$

The proof will be simpler (and more insightful) if you work with this general case, i.e. prove that $\,f_n = a^n - b^n\,$ satisfies $\,f_{n+1} = (a+b) f_{n} - ab f_{n-1},\ f_0 = 1,\ f_1 = a-b\,$ for all $\,n\ge 0.\,$ Then your problem is just the special case $\,a,b = 3,2,\,$ and the inductive step is much clearer.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I was under the impression that I showed that $P(n-2),P(n-1)\Rightarrow P(n)$. You stated that I showed $P(n-1),P(n)\Rightarrow P(n+1)$. Why? $\endgroup$ – Cherry_Developer Aug 3 '16 at 19:57
  • $\begingroup$ @Cherry That's why I said "essentially". Substitute $\,n+1\,$ for $\,n\,$ in your proof to get the upshifted form. I wrote the induction in the above form used in the MIT notes. $\endgroup$ – Bill Dubuque Aug 3 '16 at 20:01
  • $\begingroup$ Ah ok. I apologize for the slew of questions. I would just much rather struggle with the math, and ask these questions now, than when I actually take discrete math. Thank you for all your help. $\endgroup$ – Cherry_Developer Aug 3 '16 at 20:07
  • 1
    $\begingroup$ @Cherry_Developer It's the nature of the beast to struggle with induction proofs when one first encounters them (evolution doesn't program our minds for such). Many fit into particular patterns that are easier to comprehend in the abstract (such as the above which is essentially exploiting the uniqueness theorem for recurrences).. Another common form of induction is telescopy, e.g. see here for a vivid 2D example. $\endgroup$ – Bill Dubuque Aug 3 '16 at 20:11
0
$\begingroup$

Yes, your proof is perfectly fine. Good job! You can write something like "The assertion follows.". But honestly it isn't necessary since it is in this case pretty simple for readers to see where the proof is complete (after the inductive step).

| cite | improve this answer | |
$\endgroup$

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.