# Proof By Induction

1. Oct 5, 2009

### roam

1. The problem statement, all variables and given/known data
http://img10.imageshack.us/img10/8418/56729818.gif [Broken]

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

Last edited by a moderator: May 4, 2017
2. Oct 5, 2009

### 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)

3. Oct 5, 2009

### HallsofIvy

Staff Emeritus
There is NO "$f_0$". Your base case is $f_3f_1- f_2^2= (-1)^2[/quote] [/quote]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 [/QUOTE] You are writing the formula incorrectly: it is NOT "[itex]P(k+1) = f_{k+1}.f_k - f^2_{k+1}=(-1)^{k+1}$", it is $f_{k+2}f_{k}- f^2_{k+1}= (-1)^{k+1}$

Last edited by a moderator: May 4, 2017
4. Oct 8, 2009

### 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)?

5. Oct 10, 2009

### 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?