Mathematical Induction for Fibonacci sequence

**hellfire127** · November 30th 2010, 01:18 PM

Ok, this looks different from my other problems with inductions.
Suppose Fn, n is greater or equal to 0 is the Fibonacci sequence (i.e. F0=F1 = 1, and Fn = Fn-1 + Fn-2 for n is greater or equal to 2). Use mathematical induction to prove that
(Fn+2)(Fn)-F^2 * n+1 = (-1)^n for all n greater or equal to 0.

Would I need to change the left side using characteristic equation?

The left side and right side are equal when using the base case = 0. i tried the p(k) and p(k+1) method but looks like I'll need to use a different equation on the left hand side.

**tonio** · November 30th 2010, 02:51 PM

Originally Posted by hellfire127

Ok, this looks different from my other problems with inductions.
Suppose Fn, n is greater or equal to 0 is the Fibonacci sequence (i.e. F0=F1 = 1, and Fn = Fn-1 + Fn-2 for n is greater or equal to 2). Use mathematical induction to prove that
(Fn+2)(Fn)-F^2 * n+1 = (-1)^n for all n greater or equal to 0.

Would I need to change the left side using characteristic equation?

The left side and right side are equal when using the base case = 0. i tried the p(k) and p(k+1) method but looks like I'll need to use a different equation on the left hand side.

$F_{n+2}F_n-F^2_{n+1}=[F_{n+1}+F_n][F_{n-1}+F_{n-2}]-(F_n+F_{n-1})^2=$

$=F_{n+1}F_{n-1}+F_{n+1}F_{n-2}+F_nF_{n-1}+F_nF_{n-2}-F_n^2-2F_nF_{n-1}-F^2_{n-1}=$

$=F_{n+1}F_{n-1}-F^2_n+F_nF_{n-2}-F^2_{n-1}+F_{n+1}F_{n-2}-F_nF_{n-1}=$

$=(-1)^{n-1}+(-1)^{n-2}+(F_n+F_{n-1})F_{n-2}-F_nF_{n-1}=$

$=(-1)^{n-2}(-1+1)+F_nF_{n-2}-F_{n-1}(F_{n-2}-F_n)=F_nF_{n-2}-F_{n-1}^2=(-1)^{n-2}$

The inductive hypothesis is that the claim is true for all $k<n$ , and we prove it for $k=n$

Check carefully, slowly and well the above, prove every step and...voila!

Tonio

**hellfire127** · November 30th 2010, 02:59 PM

hmmm, i'll have to check carefully each step as i'm already lost on the 3rd. the reordering is a bit confusing but ill get it eventually. thanks!

edit: well after looking at it for an hour i still don't see how it reaches that. i will just have to skip this problem for now.

**hellfire127** · December 1st 2010, 01:04 PM

is there another way to show the solution above? i'm having a hard time going from one step to another. i understand the process for Fn-1 + Fn-2 but this just doesn't seem to work with the induction process for me.

**tonio** · December 1st 2010, 01:12 PM

Originally Posted by hellfire127

is there another way to show the solution above? i'm having a hard time going from one step to another. i understand the process for Fn-1 + Fn-2 but this just doesn't seem to work with the induction process for me.

1) You must master thoroughly high school algebra

2) You must understand perfectly well how Fibonacci Series work.

Write down what I posted in my 1st message you and, if after some further effort, you're still

lost write back pointing out where exactly you got stuck.

Tonio

**Archie Meade** · December 1st 2010, 02:41 PM

Originally Posted by hellfire127

Ok, this looks different from my other problems with inductions.
Suppose Fn, n is greater or equal to 0 is the Fibonacci sequence (i.e. F0=F1 = 1, and Fn = Fn-1 + Fn-2 for n is greater or equal to 2). Use mathematical induction to prove that
(Fn+2)(Fn)-F^2 * n+1 = (-1)^n for all n greater or equal to 0.

Would I need to change the left side using characteristic equation?

The left side and right side are equal when using the base case = 0. i tried the p(k) and p(k+1) method but looks like I'll need to use a different equation on the left hand side.

Here is another way;

P(k)

$F_{k+2}\;F_k-\left(F_{k+1}\right)^2=(-1)^k$

P(k+1)

$F_{k+3}\;F_{k+1}-\left(F_{k+2}\right)^2=(-1)^{k+1}=(-1)(-1)^k$

Proof

Try to show that P(k+1) will be true if P(k) is true,
hence write P(k+1) in terms of P(k).

$F_{k+3}=F_{k+1}+F_{k+2}$

$F_{k+2}=F_{k+1}+F_k}$

therefore, rewriting P(k+1)

$\left(F_{k+1}+F_{k+2}\right)F_{k+1}-\left(F_{k+1}+F_k\right)\left(F_{k+1}+F_k\right)=-(-1)^k$ ?

$\left(F_{k+1}\right)^2+F_{k+2}\;F_{k+1}-\left[\left(F_{k+1}\right)^2+2F_k\;F_{k+1}+\left(F_k\rig ht)^2\right]=-(-1)^k$ ?

$F_{k+2}\;F_{k+1}-2F_k\;F_{k+1}-\left(F_k\right)^2=-(-1)^k$ ?

$\left(F_k\right)^2+2F_k\;F_{k+1}-F_{k+2}\;F_{k+1}=(-1)^k$ ?

If we now write $F_{k+2}$ in terms of $F_{k+1},$ we will obtain the $\left(F_{k+1}\right)^2$ term in P(k)...

$F_{k+1}+F_k=F_{k+2}$

$\Rightarrow\ \left(F_k\right)^2+2F_k\;F_{k+1}-\left(F_k+F_{k+1}\right)F_{k+1}=\left(F_k\right)^2 +2F_k\;F_{k+1}-F_k\;F_{k+1}-\left(F_{k+1}\right)^2$

$=\left(F_k\right)^2+F_k\;F_{k+1}-\left(F_{k+1}\right)^2$

Factoring out $F_k$

$F_k\left(F_k+F_{k+1}\right)-\left(F_{k+1}\right)^2=F_k\;F_{k+2}-\left(F_{k+1}\right)^2$

Hence if P(k) is true, P(k+1) will certainly be true.

Test the base case.

**hellfire127** · December 1st 2010, 07:20 PM

Originally Posted by Archie Meade

Here is another way;

P(k)

$F_{k+2}\;F_k-\left(F_{k+1}\right)^2=(-1)^k$

P(k+1)

$F_{k+3}\;F_{k+1}-\left(F_{k+2}\right)^2=(-1)^{k+1}=(-1)(-1)^k$

Proof

Try to show that P(k+1) will be true if P(k) is true,
hence write P(k+1) in terms of P(k).

$F_{k+3}=F_{k+1}+F_{k+2}$

$F_{k+2}=F_{k+1}+F_k}$

therefore, rewriting P(k+1)

$\left(F_{k+1}+F_{k+2}\right)F_{k+1}-\left(F_{k+1}+F_k\right)\left(F_{k+1}+F_k\right)=-(-1)^k$ ?

$\left(F_{k+1}\right)^2+F_{k+2}\;F_{k+1}-\left[\left(F_{k+1}\right)^2+2F_k\;F_{k+1}+\left(F_k\rig ht)^2\right]=-(-1)^k$ ?

$F_{k+2}\;F_{k+1}-2F_k\;F_{k+1}-\left(F_k\right)^2=-(-1)^k$ ?

$\left(F_k\right)^2+2F_k\;F_{k+1}-F_{k+2}\;F_{k+1}=(-1)^k$ ?

If we now write $F_{k+2}$ in terms of $F_{k+1},$ we will obtain the $\left(F_{k+1}\right)^2$ term in P(k)...

$F_{k+1}+F_k=F_{k+2}$

$\Rightarrow\ \left(F_k\right)^2+2F_k\;F_{k+1}-\left(F_k+F_{k+1}\right)F_{k+1}=\left(F_k\right)^2 +2F_k\;F_{k+1}-F_k\;F_{k+1}-\left(F_{k+1}\right)^2$

$=\left(F_k\right)^2+F_k\;F_{k+1}-\left(F_{k+1}\right)^2$

Factoring out $F_k$

$F_k\left(F_k+F_{k+1}\right)-\left(F_{k+1}\right)^2=F_k\;F_{k+2}-\left(F_{k+1}\right)^2$

Hence if P(k) is true, P(k+1) will certainly be true.

Test the base case.

oh wow thank you. i see how you got to the end by following the steps. i think the k+1 helped as well. thanks again!

**Archie Meade** · December 2nd 2010, 01:01 AM

I had a suspicion that I had rewritten too many terms,
so there is a more compact proof....

P(k)

$F_{k+2}\;F_k-\left(F_{k+1}\right)^2=(-1)^k$

P(k+1)

$F_{k+3}\;F_{k+1}-\left(F_{k+2}\right)^2=(-1)^{k+1}=-(-1)^k$

Proof

We only require rewriting

$F_{k+3}=F_{k+2}+F_{k+1}$

Hence...

$\left(F_{k+2}+F_{k+1}\right)F_{k+1}-\left(F_{k+2}\right)^2=-(-1)^k$ ?

$F_{k+2}\;F_{k+1}+\left(F_{k+1}\right)^2-\left(F_{k+2}\right)^2=-(-1)^k$ ?

Factoring $F_{k+2}$

$F_{k+2}\left(F_{k+1}-F_{k+2}\right)+\left(F_{k+1}\right)^2=-(-1)^k$ ?

Multiplying both sides by $-1$

$F_{k+2}\left(F_{k+2}-F_{k+1}\right)-\left(F_{k+1}\right)^2=(-1)^k$ ?

Using $F_{k+2}=F_k+F_{k+1}\Rightarrow\ F_{k+2}-F_{k+1}=F_k$

$\Rightarrow\ F_{k+2}\;F_k-\left(F_{k+1}\right)^2=(-1)^k$

Hence P(k) being true causes P(k+1) to be true.

Thread: Mathematical Induction for Fibonacci sequence

LinkBack

Thread Tools

Display

Mathematical Induction for Fibonacci sequence[SOLVED]

Similar Math Help Forum Discussions

Fibonacci Sequence - Induction Proof

[SOLVED] Fibonacci sequence induction proof

Recursive sequence (Fibonacci Sequence) & Limits

Fibonacci Sequence: Induction Proof

Fibonacci sequence - prove by induction

Search Tags