Proof by induction - Fibonacci sequence

Natasha1
Messages
494
Reaction score
9
I need to proove by induction that:

1, 1, 2, 3, 5, 8, 13...


if you do take f1*f3 - f2^2 you get 1
for the next in the series f2 you get f2*f4 - f3^2 you get -1
and so on...

You keep getting 1, -1, 1, -1 for ever... and i need to proove that. Could someone please do it, or has anyone got a link on the internet to it? I have been looking for hours :-(


(F_n \cdot F_{n+2}) - (F_{n+1})^2 = (-1)^{n+1}

Fn being a Fibonacci number

By convention F0 = 0, F1 = 1, so that F2 = 1.
 
Physics news on Phys.org
Natasha1 said:
I need to proove by induction that:

1, 1, 2, 3, 5, 8, 13...

if you do take f1*f3 - f2^2 you get 1
for the next in the series f2 you get f2*f4 - f3^2 you get -1
and so on...

You keep getting 1, -1, 1, -1 for ever... and i need to proove that. Could someone please do it, or has anyone got a link on the internet to it? I have been looking for hours :-(


(F_n \cdot F_{n+2}) - (F_{n+1})^2 = (-1)^{n+1}

Fn being a Fibonacci number

By convention F0 = 0, F1 = 1, so that F2 = 1.

Okay, It's clearly true for n= 1 as you showed.

Now, assume that is true for some number k:
(F_k \cdot F_{k+2}) - (F_{k+1})^2 = (-1)^{k+1}
Now look at what happens for k+1:
(F_{k+1} \cdot F_{k+1+2}) - (F_{k+1+1})^2 = F_{k+1}\cdot F_{k+3}- F_{k+2}^2

Of course F_{k+3}= F_{k+1}+F_{k+2} and F_{k+2}= F_k+ F_{k+1}. Substitue those into the formula above (the one with Fk+3 in it) and see if you can't rearrange it to get something like you "inductive hypothesis" which you can then replace with (-1)n.
 
HallsofIvy said:
Okay, It's clearly true for n= 1 as you showed.

Now, assume that is true for some number k:
(F_k \cdot F_{k+2}) - (F_{k+1})^2 = (-1)^{k+1}
Now look at what happens for k+1:
(F_{k+1} \cdot F_{k+1+2}) - (F_{k+1+1})^2 = F_{k+1}\cdot F_{k+3}- F_{k+2}^2

Of course F_{k+3}= F_{k+1}+F_{k+2} and F_{k+2}= F_k+ F_{k+1}. Substitue those into the formula above (the one with Fk+3 in it) and see if you can't rearrange it to get something like you "inductive hypothesis" which you can then replace with (-1)n.


Is this good? Please see attached picture
 

Attachments

  • proof.jpg
    proof.jpg
    16.6 KB · Views: 675
Natasha1 said:
Is this good? Please see attached picture
Aaarrrrggg, why don't you just LaTeX? I've been waiting for that attachment to be approved for ages. :cry: :cry: :cry:
 
VietDao29 said:
Aaarrrrggg, why don't you just LaTeX? I've been waiting for that attachment to be approved for ages. :cry: :cry: :cry:

Who approves these documents anyway?? It takes not weeks but months!

Anyway...

Here is what I've done, if not please correct me :-):

Since there is a k\geq 2 such as,
F(k)^2-F(k+1)F(k-1)=(-1)^{k-1}
Then proof it hold for k+1. But the expression,
F(k+1)^2-F(k+2)F(k)=(-1)(F(k)^2-F(k+1)F(k-1))
But,
F(k)^2-F(k+1)(k-1)=(-1)^{k-1}
Thus,
F(k+1)^2-F(k+1)F(k)=(-1)(-1)^{k-1}=(-1)^k
Thus, it hold true for k+1.
 
You haven't proven anything yet. Start by showing that the formula is valid for k=0, i.e. that F_0 \cdot F_{2}-F_{1}^2=(-1)^{1}. Then prove F_{k+1} \cdot F_{k+3}-F_{k+2}^2=(-1)^{k+1} knowing that F_k \cdot F_{k+2}-F_{k+1}^2=(-1)^{k+1} and F_k+F_{k+1}=F_{k+2}.
 
Natasha1 said:
But,
F(k)^2-F(k+1)(k-1)=(-1)^{k-1}
Thus,
F(k+1)^2-F(k+1)F(k)=(-1)(-1)^{k-1}=(-1)^k
Thus, it hold true for k+1.
Why? This is what you have to prove! You cannot assume things like that. You must prove it.
The idea for Proof By Induction is that say if the statement holds for n = 1, and you can prove that if the statement holds for n = k then it also holds for n = k + 1. Then the statement holds for every n \geq 1. Why? Besause say the statement is true for n = 1 (you can test to see if it's true), then the statement is also true for n = 1 + 1 = 2.
And because the statement is true for n = 2, it's also true for n = 2 + 1 = 3, and because the statement is true for n = 3, it's also true for n = 3 + 1 = 4, and so on... So the statement is true for all n greater than or equal to 1.
--------------
Example:
Prove that:
\sum_{i = 1} ^ n i = \frac{n (n + 1)}{2}, \ n \geq 1
Proof:
Step 1: For n = 1, we have:
LHS : \sum_{i = 1} ^ 1 i = 1
RHS : \frac{1 (1 + 1)}{2} = \frac{2}{2} = 1
So LSH = RHS, hence the equation holds for n = 1.
Step 2: Assume that the equation is true for n = k (inductive hypothesis), we have:
\sum_{i = 1} ^ k i = \frac{k (k + 1)}{2}
Step 3: We then have to use our inductive hypothesis to prove that the statement is also true for n = k + 1, i.e we have to prove:
\sum_{i = 1} ^ {k + 1} (i) = \frac{(k + 1) (k + 2)}{2}
So we have:
\sum_{i = 1} ^ k i = \frac{k (k + 1)}{2} (this is our inductive hypothesis, we'll start from it)
\Leftrightarrow \sum_{i = 1} ^ k (i) + k + 1 = \frac{k (k + 1)}{2} + k + 1
\Leftrightarrow \sum_{i = 1} ^ {k + 1} (i) = \frac{k (k + 1) + 2 (k + 1)}{2}
\Leftrightarrow \sum_{i = 1} ^ {k + 1} (i) = \frac{(k + 1) (k + 2)}{2} (factor (k + 1) out in the RHS)
Hence the equation holds true for n = k + 1.
--------------
This means you have proven that:
If the statement is true for n = k => it's true for n = k + 1
You have tested that it's true for n = 1 (the first step)
So the equation holds for n = 1 => it holds for n = 1 + 1 = 2 => it holds for n = 2 + 1 = 3 => it holds for n = 3 + 1 = 4 => ... => it holds for all n greater than or equal to 1.
Can you get this?
--------------
Back to your problem, now you have to test to see if it's true for n = 0 first, then you have to prove
IF (F_k \cdot F_{k+2}) - (F_{k+1})^2 = (-1)^{k+1}
THEN
(F_{k + 1} \cdot F_{k+3}) - (F_{k+2})^2 = (-1)^{k+2}
Can you go from here? :)
Hint: You can re-read HallsofIvy's post to have some ideas on how to start off the problem.
 
Last edited:
VietDao29 said:
Why? This is what you have to prove! You cannot assume things like that. You must prove it.
The idea for Proof By Induction is that say if the statement holds for n = 1, and you can prove that if the statement holds for n = k then it also holds for n = k + 1. Then the statement holds for every n \geq 1. Why? Besause say the statement is true for n = 1 (you can test to see if it's true), then the statement is also true for n = 1 + 1 = 2.
And because the statement is true for n = 2, it's also true for n = 2 + 1 = 3, and because the statement is true for n = 3, it's also true for n = 3 + 1 = 4, and so on... So the statement is true for all n greater than or equal to 1.
--------------
Example:
Prove that:
\sum_{i = 1} ^ n i = \frac{n (n + 1)}{2}, \ n \geq 1
Proof:
Step 1: For n = 1, we have:
LHS : \sum_{i = 1} ^ 1 i = 1
RHS : \frac{1 (1 + 1)}{2} = \frac{2}{2} = 1
So LSH = RHS, hence the equation holds for n = 1.
Step 2: Assume that the equation is true for n = k (inductive hypothesis), we have:
\sum_{i = 1} ^ k i = \frac{k (k + 1)}{2}
Step 3: We then have to use our inductive hypothesis to prove that the statement is also true for n = k + 1, i.e we have to prove:
\sum_{i = 1} ^ {k + 1} (i) = \frac{(k + 1) (k + 2)}{2}
So we have:
\sum_{i = 1} ^ k i = \frac{k (k + 1)}{2} (this is our inductive hypothesis, we'll start from it)
\Leftrightarrow \sum_{i = 1} ^ k (i) + k + 1 = \frac{k (k + 1)}{2} + k + 1
\Leftrightarrow \sum_{i = 1} ^ {k + 1} (i) = \frac{k (k + 1) + 2 (k + 1)}{2}
\Leftrightarrow \sum_{i = 1} ^ {k + 1} (i) = \frac{(k + 1) (k + 2)}{2} (factor (k + 1) out in the RHS)
Hence the equation holds true for n = k + 1.
--------------
This means you have proven that:
If the statement is true for n = k => it's true for n = k + 1
You have tested that it's true for n = 1 (the first step)
So the equation holds for n = 1 => it holds for n = 1 + 1 = 2 => it holds for n = 2 + 1 = 3 => it holds for n = 3 + 1 = 4 => ... => it holds for all n greater than or equal to 1.
Can you get this?
--------------
Back to your problem, now you have to test to see if it's true for n = 0 first, then you have to prove
IF (F_k \cdot F_{k+2}) - (F_{k+1})^2 = (-1)^{k+1}
THEN
(F_{k + 1} \cdot F_{k+3}) - (F_{k+2})^2 = (-1)^{k+2}
Can you go from here? :)
Hint: You can re-read HallsofIvy's post to have some ideas on how to start off the problem.


Is this good?

Step 1: For n = 1, we have


(F_1 \cdot F_{1+2}) - (F_{1+1})^2 = (-1)^{1+1} = 1


Hence the equation holds for n = 1

Step 2: Assume the equation is true for n = k (inductive hypothesis), we have:

(F_k \cdot F_{k+2}) - (F_{k+1})^2 = (-1)^{k+1}

Step 3: We then have to use our inductive hypothesis to prove that the statement is also true for n = k + 1, i.e we have to prove:

(F_{k+1} \cdot F_{k+3}) - (F_{k+2})^2 = (-1)^{k+2}

So we have:

(F_k \cdot F_{k+2}) - (F_{k+1})^2 = (-1)^{k+1}
(F_k \cdot F_{k+2}) - (F_{k+1})^2 + k+1= (-1)^{k+1} + k+1
Could someone write what goes here please?
.
.
(F_{k+1} \cdot F_{k+3}) - (F_{k+2})^2 = (-1)^{k+2}

Hence the equation holds true for n = k + 1
 
Last edited:
No, that is not right. Firstly, you need to put inexplicitly what F_1,F_2 and F_3 are to prove the base case, and no we are not going to put in the missing steps for you since that would be 'doign your homework for you' and that is not allowed.Start with the expression for k+1 (do not put in =(-1)^{whatever}) just put in the LHS, now, what do you know about the fibonacci sequence? use that to get rid of the F_{k+3} and now try t manipulate it to get it ina form that let's you use the inductive hypothesis (i.e. the identity for k)
 
  • #10
Any better?

Step 1: For n = 1, we have

(F_1 \cdot F_{1+2}) - (F_{1+1})^2 = (-1)^{1+1} = 1

Where f_1=1m f_2 = 1, f_3 = 2
Hence the equation holds for n = 1

Step 2: Assume the equation is true for n = k (inductive hypothesis), we have:

(F_k \cdot F_{k+2}) - (F_{k+1})^2 = (-1)^{k+1}

Step 3: We then have to use our inductive hypothesis to prove that the statement is also true for n = k + 1, i.e we have to prove:

(F_{k+1} \cdot F_{k+3}) - (F_{k+2})^2 <br /> <br /> So we have:<br /> <br /> Since there is a k\geq 2 such as,<br /> F(k)^2-F(k+1)F(k-1)=(-1)^{k-1}<br /> <br /> Then proof it hold for k+1. <br /> <br /> But the expression,<br /> F(k+1)^2-F(k+2)F(k)=(-1)(F(k)^2-F(k+1)F(k-1))<br /> But,<br /> F(k)^2-F(k+1)(k-1)=(-1)^{k-1}<br /> Thus,<br /> F(k+1)^2-F(k+1)F(k)=(-1)(-1)^{k-1}=(-1)^k<br /> Thus, it hold true for k+1.<br /> <br /> (F_{k+1} \cdot F_{k+3}) - (F_{k+2})^2 = (-1)^{k+2}<br /> <br /> Hence the equation holds true for n = k + 1[/QUOTE]
 
Last edited:
  • #11
Natasha1 said:
But,
F(k)^2-F(k+1)(k-1)=(-1)^{k-1}
Thus,
F(k+1)^2-F(k+1)F(k)=(-1)(-1)^{k-1}=(-1)^k
No, it's still wrong. How can you go from the former equation to the latter one? You have to prove it, why is it true? You cannot just claim that it's true without giving any proof.
Ok, what you have to do know is to use the Fibonacci sequence's property, i.e:
Fn + 2 = Fn + Fn + 1 to rearrange the expression F_{k + 1} \cdot F_{k+3}) - (F_{k+2})^2 to something like this: ( F_{k} \cdot F_{k+2}) - (F_{k+1})^2) \cdot \mbox{something}
I personally think that you should read the chapter about Proof by Induction in your book again, find some examples there, try to read, and think thoroughly to understand why did the author do that, and how can he use Proof by Induction. And when you understand it a bit better, try to tackle this problem again.
 
Last edited:
  • #12
If someone could be king enough to have a read through my induction proof attached and mention if there are any mistakes. Thanks
 
Last edited:

Similar threads

Fibonacci Proofs via Induction
Replies
5
Views
4K
How to prove that every third Fibonacci number is even?
Replies
1
Views
3K
Do these two statements imply an underlying induction proof?
Replies
7
Views
1K
Finding GCD with Fibonacci: Base Case
Replies
1
Views
2K
Induction with binomial coefficient
Replies
15
Views
2K
Sierpinskis Gasket - Linear Algebra
Replies
1
Views
1K
Mathematical Induction Problem Fibonacci numbers
Replies
11
Views
2K
Fibonacci sequence: what's wrong here?
Replies
6
Views
3K
Prove the typewriter sequence does not converge pointwise.
Replies
2
Views
5K
Induction Proof, Apostol Calc Vol I, I.4.4.7
Replies
6
Views
2K

Hot Threads

Recent Insights

Back
Top