# Generalized mathematical induction

#### Dog

##### New member
Recall that the fibonacci sequence is defined as

{ f0=0; f1 = 1 and
{fn = f n - 1 + fn -2 for n 2

Prove by generalized mathematical induction that

fn = 1/sqrt(5)[ϕn - (-ϕ)-n]

where ϕ = [1+sqrt(5)]/2

is the golden ratio.. (This is known as de Moivre's formula.)

So I'm completely lost as to how I should start this and I need someone to point me in the right direction. Thanks.

#### MarkFL

Staff member
First, you want to demonstrate that the base case $P_0$ is true:

$$\displaystyle F_0=\frac{1}{\sqrt{5}}\left(\phi^{0}-\phi^{-0} \right)=0$$

Is this true?

Next, state the induction hypothesis:

$$\displaystyle F_k=\frac{1}{\sqrt{5}}\left(\phi^{k}-(-\phi)^{-k} \right)$$

As your inductive step, the recursive definition of the sequence will be helpful. During this process you will want to demonstrate that:

$$\displaystyle \phi^{k}+\phi^{k-1}=\phi^{k+1}$$

and

$$\displaystyle (-\phi)^{-k}+(-\phi)^{-(k-1)}=(-\phi)^{-(k+1)}$$

#### Evgeny.Makarov

##### Well-known member
MHB Math Scholar
Hi, and welcome to the forum. Please see the section on strong induction in Wikipedia and possibly other sections of that article.

#### Dog

##### New member
First, you want to demonstrate that the base case $P_0$ is true:

$$\displaystyle F_0=\frac{1}{\sqrt{5}}\left(\phi^{0}-\phi^{-0} \right)=0$$

Is this true?

Next, state the induction hypothesis:

$$\displaystyle F_k=\frac{1}{\sqrt{5}}\left(\phi^{k}-\phi^{-k} \right)$$

As your inductive step, the recursive definition of the sequence will be helpful. During this process you will want to demonstrate that:

$$\displaystyle \phi^{k}+\phi^{k-1}=\phi^{k+1}$$

and

$$\displaystyle \phi^{-k}+\phi^{-(k-1)}=\phi^{-(k+1)}$$
So my base cases check to be true. I've attached my work here.

And fn is true for n. But I'm not sure how to prove for n + 1.

fn+1= f(n+1)-1 + f(n+1)-2

=fn+f(n-1)
=1/sqrt(5)[ϕn-n] + 1/sqrt(5) [ϕ(n-1) ϕ-(n-1)

What do I do next? If I'm even going in the right direction.

Last edited by a moderator:

#### MarkFL

Staff member
While it didn't hurt to show it is true for $n=1$, you really only need to show it is true for one case, and demonstration that it is true for $n=0$ is simpler.

Okay, next you want to state the induction hypothesis $P_k$:

$$\displaystyle F_k=\frac{1}{\sqrt{5}}\left(\phi^{k}-(-\phi)^{-k} \right)$$

Now, I suggest adding to this $P_{k-1}$

$$\displaystyle F_{k-1}=\frac{1}{\sqrt{5}}\left(\phi^{k-1}-(-\phi)^{-(k-1)} \right)$$

Aided by the recursion:

$$\displaystyle F_{k+1}=F_{k}+F_{k-1}$$

the left side immediately becomes what you need. And the right side also becomes what you need if you prove the two properties involving $\phi$ I listed in my first post are true.

#### Evgeny.Makarov

##### Well-known member
MHB Math Scholar
$$\displaystyle F_k=\frac{1}{\sqrt{5}}\left(\phi^{k}-\phi^{-k} \right)$$
This should say
$F_k=\frac{1}{\sqrt{5}}\left(\phi^{k}-(-\phi)^{-k} \right)$
just as the original post says.

While it didn't hurt to show it is true for $n=1$, you really only need to show it is true for one case
Hmm...

Okay, next you want to state the induction hypothesis $P_k$:

$$\displaystyle F_k=\frac{1}{\sqrt{5}}\left(\phi^{k}-\phi^{-k} \right)$$

Now, I suggest adding to this $P_{k-1}$

$$\displaystyle F_{k-1}=\frac{1}{\sqrt{5}}\left(\phi^{k-1}-\phi^{-(k-1)} \right)$$
Let's set $k=1$. We have proved $P_0$, but what about $P_1$?

#### MarkFL

Staff member
This should say
$F_k=\frac{1}{\sqrt{5}}\left(\phi^{k}-(-\phi)^{-k} \right)$
just as the original post says.

Hmm...

Let's set $k=1$. We have proved $P_0$, but what about $P_1$?
I fixed my posts to correctly state the hypothesis. My mistake also that both given initial values need to be shown are true.

#### MarkFL

Staff member
As as aside, we can derive the required result. If we write the recursion as the linear homogeneous difference equation:

$$\displaystyle F_{n}-F_{n-1}-F_{n-2}=0$$

We then find the associated characteristic equation is:

$$\displaystyle r^2-r-1=0$$

Application of the quadratic formula yields the characteristic roots:

$$\displaystyle r=\frac{-(-1)\pm\sqrt{(-1)^2-4(1)(-1)}}{2(1)}=\frac{1\pm\sqrt{5}}{2}$$

Now, if we define:

$$\displaystyle \phi=\frac{1+\sqrt{5}}{2}$$

We then see that:

$$\displaystyle \frac{1-\sqrt{5}}{2}\cdot\frac{1+\sqrt{5}}{1+\sqrt{5}}= \frac{1-5}{2\left(1+\sqrt{5} \right)}=- \frac{2}{1+\sqrt{5}}=(-\phi)^{-1}$$

Hence the characteristic roots may be given as:

$$\displaystyle r=\phi,\,(-\phi)^{-1}$$

And thus, we know the closed form for $F_n$ is given by:

$$\displaystyle F_n=A\phi^n+B(-\phi)^{-n}$$

Now, using the initial values of the sequence, we may determine the values of the parameters $A$ and $B$:

$$\displaystyle F_0=A\phi^0+B(-\phi)^{-0}=A+B=0\implies B=-A$$

$$\displaystyle F_1=A\phi^1+B(-\phi)^{-1}=A\frac{1+\sqrt{5}}{2}-A\frac{1-\sqrt{5}}{2}=A\sqrt{5}=1\implies A=\frac{1}{\sqrt{5}}$$

Hence, we find the solution satisfying the difference equation and the initial values is:

$$\displaystyle F_n=\frac{1}{\sqrt{5}}\phi^n-\frac{1}{\sqrt{5}}(-\phi)^{-n}$$

Factoring gives us:

$$\displaystyle F_n=\frac{1}{\sqrt{5}}\left(\phi^n-(-\phi)^{-n} \right)$$

#### Andrei

##### Member
fn = 1/sqrt(5)[ϕn - (-ϕ)-n]

where ϕ = [1+sqrt(5)]/2
Prove that this is the same as $$\displaystyle F_n=\frac{\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n}{\sqrt{5}}$$.

On induction step calculate $$\displaystyle F_{n+1}=F_{n-1}+F_n$$ by using

$$\displaystyle \left(\frac{1+\sqrt{5}}{2}\right)^2=1+\frac{1+ \sqrt{5}}{2}$$

$$\displaystyle \left(\frac{1-\sqrt{5}}{2}\right)^2=1+\frac{1-\sqrt{5}}{2}$$