Welcome to our community

Be a part of something great, join today!

Generalized mathematical induction

Dog

New member
Jan 12, 2014
2
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

Administrator
Staff member
Feb 24, 2012
13,775
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
Jan 30, 2012
2,492
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
Jan 12, 2014
2
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.

dog2.jpg

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

Administrator
Staff member
Feb 24, 2012
13,775
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
Jan 30, 2012
2,492
\(\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

Administrator
Staff member
Feb 24, 2012
13,775
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

Administrator
Staff member
Feb 24, 2012
13,775
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
Jan 18, 2013
36
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}\)