Proof By Induction

  • Thread starter roam
  • Start date
  • #1
1,266
11

Homework Statement


http://img10.imageshack.us/img10/8418/56729818.gif [Broken]


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: [tex]P(1) = f_1 f_0 - f_{1}^2 = (-1)^1[/tex]

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

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

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

any help or clues here is very appreciated :smile:
 
Last edited by a moderator:

Answers and Replies

  • #2
lanedance
Homework Helper
3,304
2
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
HallsofIvy
Science Advisor
Homework Helper
41,833
964

Homework Statement


http://img10.imageshack.us/img10/8418/56729818.gif [Broken]


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: [tex]P(1) = f_1 f_0 - f_{1}^2 = (-1)^1[/tex]

We don't know what the value of [tex]f_0[/tex] is, but if [tex]f_0 = 0[/tex] we get [tex]1 .0 - 1=-1[/tex]. Therefore P(1) is true.
There is NO "[itex]f_0[/itex]". Your base case is [itex]f_3f_1- f_2^2= (-1)^2[/quote]

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

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

any help or clues here is very appreciated :smile:[/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}[/itex]", it is [itex]f_{k+2}f_{k}- f^2_{k+1}= (-1)^{k+1}[/itex]
 
Last edited by a moderator:
  • #4
1,266
11
Hi!

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

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

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

Here's where I'm stuck. Any hints on how to prove P(k+1)?
 
  • #5
1,266
11
We know that [tex]f_{k+1}f_{k-1}- f^2_{k}= (-1)^{k}[/tex]

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

[tex](f_{k+1}+f_k)f_{k}- f^2_{k+1}[/tex]

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

Related Threads on Proof By Induction

  • Last Post
Replies
6
Views
863
  • Last Post
Replies
9
Views
1K
  • Last Post
Replies
10
Views
1K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
4
Views
874
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
2
Views
763
  • Last Post
Replies
3
Views
942
Top