Thread: Mathematical Induction for Fibonacci sequence

1. Mathematical Induction for Fibonacci sequence[SOLVED]

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.

2. 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.
$\displaystyle 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=$

$\displaystyle =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}=$

$\displaystyle =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}=$

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

$\displaystyle =(-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 $\displaystyle k<n$ , and we prove it for $\displaystyle k=n$

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

Tonio

3. 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.

4. 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.

5. 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

6. 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)

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

P(k+1)

$\displaystyle 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).

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

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

therefore, rewriting P(k+1)

$\displaystyle \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$ ?

$\displaystyle \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$ ?

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

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

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

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

$\displaystyle \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$

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

Factoring out $\displaystyle F_k$

$\displaystyle 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.

7. Originally Posted by Archie Meade
Here is another way;

P(k)

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

P(k+1)

$\displaystyle 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).

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

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

therefore, rewriting P(k+1)

$\displaystyle \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$ ?

$\displaystyle \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$ ?

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

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

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

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

$\displaystyle \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$

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

Factoring out $\displaystyle F_k$

$\displaystyle 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!

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

P(k)

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

P(k+1)

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

Proof

We only require rewriting

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

Hence...

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

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

Factoring $\displaystyle F_{k+2}$

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

Multiplying both sides by $\displaystyle -1$

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

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

$\displaystyle \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.