Fibonacci Formula Inductive Proof
Date: 11/05/97 at 07:26:35 From: Alexander Joly Subject: Fibonacci formula inductive proof Hello! I am stuck on a problem about the nth number of the Fibonacci sequence. I must prove by induction that F(n) = (PHI^n - (1 - PHI)^n) / sqrt5 Here's what we usually do to prove something by induction: 1) Show that the formula works with n = 1. 2) Show that if it works for (n), then it will work for (n+1). But the problem is: We suppose F(n) is true, so F(n+1) is true. But when I must prove it, I have to add another thing: F(n-1), because F(n-1) + F(n) = F(n+1). So here are the questions: Can I suppose TWO things are true, F(n) and F(n-1), to prove that F(n+1) is true? How can I prove it is true for n = 1, since F(1) is DEFINED as equal to 1? Here's what I've already done: I've successfully converted (PHI^(n-1) - (1 - PHI)^(n-1)) / sqrt5 + (PHI^n - (1 - PHI)^n) / sqrt5 into (PHI^(n+1) - (1 - PHI)^(n+1)) / sqrt5 Thank you very much for your much-appreciated help! An example of the Fibonacci formula inductive proof would be very kind. Alexander
Date: 11/05/97 at 13:25:14 From: Doctor Rob Subject: Re: Fibonacci formula inductive proof You have already done the hard part, which is in your next-to-last paragraph. Answer 1. Yes, you can assume two things are true, but then you have to show that two starting values work. (Think about it.) An equivalent formulation of the Principle of Mathematical Induction is where you assume it is true for *all* values k with 1 <= k <= n, and use that to show it for n+1. Answer 2. To prove it for n = 1, you have to show that 1 = F(1) = (PHI - 1 + PHI)/sqrt(5). You do this by using the fact that PHI = (1 + sqrt(5))/2. Substitute it in and check that it works. To prove it for n = 2, you have to show that 1 = F(2) = (PHI^2 - [1 - PHI]^2)/sqrt(5). You do this the same way. By the way, this is also true for n = 0, 0 = F(0) = (PHI^0 - [1 - PHI]^0)/sqrt(5), for which you don't even need the formula for PHI. -Doctor Rob, The Math Forum Check out our web site! http://mathforum.org/dr.math/
Date: 11/05/97 at 15:31:47 From: Doctor Anthony Subject: Re: Fibonacci formula inductive proof 1+sqrt(5) Taking PHI to be ----------- 2 we first check that the formula is true for n = 1 and n = 2 F(1) = (1/sqrt(5))[(1+sqrt(5))/2 - 1 -(1+sqrt(5))/2] = (1/sqrt(5))[1/2 + sqrt(5)/2 - 1/2 + sqrt(5)/2] = 1/sqrt(5)[sqrt(5)] = 1 F(2) = (1/sqrt(5))[PHI^2 - (1-PHI)^2] = (1/sqrt(5)[PHI^2 - 1 + 2 PHI - PHI^2] = (1/sqrt(5))[2 PHI - 1] = (1/sqrt(5)[1+sqrt(5) - 1] = 1 So the formula is correct for n=1 and n=2. Now assume it is true for all terms UP TO some other value n. If we take 1 sqrt(5)+1 1 - sqrt(5) F(n+1) = -------[ (--------- )^(n+1) - ( ----------- )^(n+1)] sqrt(5) 2 2 By taking out a factor (sqrt(5)+1)^2 --------- from the first term and 2^2 (1-sqrt(5))^2 ---------- 2^2 from the second term and then squaring out these brackets it is easy to show that F(n+1) = F(n) + F(n-1). So if the expression is true for n and n-1, it is also true for n+1. But it is true for n=1 and n=2, hence it must be true for n=3. So true for n=2 and n=3 it is true for n=4. Thence to n=5, n=6, n=7 and so on to all positive integer values of n. -Doctor Anthony, The Math Forum Check out our web site! http://mathforum.org/dr.math/
Date: 11/10/97 at 11:55:23 From: Joly Subject: Re: Fibonacci formula inductive proof Dear Dr. Rob, I give up, Doctor Rob. I must use three values (F(n), F(n-1) and F(n+1)), but I can't find the way to justify this use of the induction. I know I have to show that two starting values work, but this is where I am stuck. I don't know how to show it. Thank you very much for your time!
Date: 11/10/97 at 12:44:31 From: Doctor Rob Subject: Re: Fibonacci formula inductive proof I'm sorry that my previous answer was not sufficient to solve your problem. As I understand the current state of the problem, you need the following theorem to finish it: Theorem: If P(n) is a statement involving the variable n, and if P(1) is true, P(2) is true, and the implication P(k) & P(k+1) ==> P(k+2) is true, then P(n) is true for all n >= 1. Proof: We will prove this using the Principle of Mathematical Induction. Let Q(n) be the statement "P(n) is true and P(n+1) is true." Then Q(1) holds by hypothesis. Given Q(k) is true, we know that P(k) and P(k+1) are true. Using the implication from the hypotheses of the theorem, P(k+2) is also true, so P(k+1) and P(k+2) are both true. Thus Q(k+1) is true. This means that Q(k) ==> Q(k+1). Thus by the Principle of Mathematical Induction, Q(n) is true for all n >= 1. Q(n) ==> P(n), so P(n) is true for all n >= 1. Q.E.D. This is the justification you need to use your "double-step" induction. See how the need for Q(1) to be true forces us to make sure that both P(1) and P(2) are true, so we have a two-part start for the induction. -Doctor Rob, The Math Forum Check out our web site! http://mathforum.org/dr.math/
Date: 11/10/97 at 14:21:46 From: DJoly Subject: RE: Thanks, Doctor Rob! Thank you very much! Your answers were very complete. This is all people could expect from Dr. Math's service! Alexander
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.