Solving Proof by Induction Homework w/ Simple Induction

[roam]

Homework Statement

http://img10.imageshack.us/img10/8418/56729818.gif

The Attempt at a Solution

Firstly do I need to use the "simple induction" or "complete induction"?

I will try the simple induction.

Base Case: P(1) = f_1 f_0 - f_{1}^2 = (-1)^1

We don't know what the value of f_0 is, but if f_0 = 0 we get 1 .0 - 1=-1. Therefore P(1) is true.

Inductive Step: Suppose P(k) is true, where k \in N. Now I'm stuck & don't know how to deduce that P(k+1) is true.

i.e. show that P(k+1) = f_{k+1}.f_k - f^2_{k+1}=(-1)^{k+1} is true.

any help or clues here is very appreciated

 

[lanedance]

i think you may have to extend it a bit, show P(1) & P(2) true, then assume P(n) & P(n-1) now try and show P(n+1)

 

[HallsofIvy]

Homework Statement

http://img10.imageshack.us/img10/8418/56729818.gif

The Attempt at a Solution

Firstly do I need to use the "simple induction" or "complete induction"?

I will try the simple induction.

Base Case: P(1) = f_1 f_0 - f_{1}^2 = (-1)^1

We don't know what the value of f_0 is, but if f_0 = 0 we get 1 .0 - 1=-1. Therefore P(1) is true.

There is NO "f_0". Your base case is f_3f_1- f_2^2= (-1)^2[/quote]<br /> <br /> [/quote]Inductive Step: Suppose P(k) is true, where k \in N. Now I&#039;m stuck &amp; don&#039;t know how to deduce that P(k+1) is true.<br /> <br /> i.e. show that P(k+1) = f_{k+1}.f_k - f^2_{k+1}=(-1)^{k+1} is true.<br /> <br /> any help or clues here is very appreciated <img src="https://cdn.jsdelivr.net/joypixels/assets/8.0/png/unicode/64/1f642.png" class="smilie smilie--emoji" loading="lazy" width="64" height="64" alt=":smile:" title="Smile :smile:" data-smilie="1"data-shortname=":smile:" />[/QUOTE]<br /> You are writing the formula incorrectly: it is NOT &quot;P(k+1) = f_{k+1}.f_k - f^2_{k+1}=(-1)^{k+1}&quot;, it is f_{k+2}f_{k}- f^2_{k+1}= (-1)^{k+1}

 

[roam]

Hi!

Thanks, lanedance. We know that f_1 = f_2 =1 and using the given formula f_n = f_{n-1}+f_{n-2} we find f_3 = 2.

So the base case is:f_3 . f_1 - f_2 = (-1)^2
2.1-1=(-1)^2
Base case is true.

Inductive step:
Suppose P(k) is true for some k \in \mathbb{N}
Sorry Halls, it was a typo. I meant P(k+1) is f_{k+2}f_{k}- f^2_{k+1}= (-1)^{k+1} = (-1)^k .(-1)

Here's where I'm stuck. Any hints on how to prove P(k+1)?

 

[roam]

We know that f_{k+1}f_{k-1}- f^2_{k}= (-1)^{k}

I can simplify f_{k+2}f_{k}- f^2_{k+1} to:

(f_{k+1}+f_k)f_{k}- f^2_{k+1}

Now how can we simplify this to show it equals to (-1)^{k+1} and finish the proof?