My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
September 25th, 2012, 10:47 AM   #1
Newbie
 
Joined: Sep 2012

Posts: 6
Thanks: 0

proving a property of the fibonacci sequence

Greetings everyone,
I need to prove the following property:


where means the term on the fibonacci's sequence.
This is an exercise from a list where all the previous were solved using induction, so I expect the solution also goes through this way.
juarez.asf is offline  
 
September 25th, 2012, 11:28 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: proving a property of the fibonacci sequence

Do you know how to set up a proof by induction? Often the best way (at this level) is to start by filling in the skeleton of the proof, which makes it easier to find the rest.

For example, suppose you wanted to prove that n + n = 2n by induction. The proof would look like this:

For the base case, 1 + 1 = 2*1; the left side and right side are both 2, so this is true. Otherwise, suppose n > 1 and that (n-1) + (n-1) = 2(n-1). Then [color=#00BFFF](inductive step here.)[/color] Thus n + n = 2n on this assumption. By induction, n + n = 2n for all n >= 1.

Can you fill out the same for your problem? Once you do, make any simplifications you can from the inductive hypothesis. You might just solve it from there; if not, I'd be happy to help you fill in the gaps (unless someone beasts me to it).
CRGreathouse is offline  
September 25th, 2012, 12:02 PM   #3
Newbie
 
Joined: Sep 2012

Posts: 6
Thanks: 0

Re: proving a property of the fibonacci sequence

yes, I do know how to use induction. We check the proposition for a first element then find a way to prove that assuming it works for n it shall work for n+1.
The thing is, I am not being able to 'jump' from de n to the n+1
juarez.asf is offline  
September 25th, 2012, 12:07 PM   #4
Newbie
 
Joined: Sep 2012

Posts: 3
Thanks: 0

Re: proving a property of the fibonacci sequence

wow, I was trying to solve this exercise someday (using induction too). Assuming that it's true for k-1, I couldn't reach that it would be true for k.
I want this demonstration too, so I'll follow this topic.

10 points for whom answer this!
rodrigomkt is offline  
September 25th, 2012, 12:08 PM   #5
Newbie
 
Joined: Sep 2012

Posts: 6
Thanks: 0

Re: proving a property of the fibonacci sequence

Normally when using iduction just some manipulation, even that some times a lot of manipulations, of one equation will get you from de n-term to the n+1-term, bur here I don't see how to do thoese manipulations. Mainly, because on the left side we have while on the right . Those index are really kiling me. I didn't find a relation betwen then, no way to convert one into another.
juarez.asf is offline  
September 25th, 2012, 06:36 PM   #6
Senior Member
 
MarkFL's Avatar
 
Joined: Jul 2010
From: St. Augustine, FL., U.S.A.'s oldest city

Posts: 12,168
Thanks: 472

Math Focus: Calculus/ODEs
Re: proving a property of the fibonacci sequence

After having shown the base case to be true, state the hypothesis :

(1)

By the definition of the sequence, we have:



Using the hypothesis, this is:



(2)

Adding (1) and (2), we have:







We have derived from thereby completing the proof by induction.
MarkFL is offline  
September 28th, 2012, 06:52 AM   #7
Newbie
 
Joined: Sep 2012

Posts: 6
Thanks: 0

Re: proving a property of the fibonacci sequence

Quote:
Originally Posted by MarkFL
After having shown the base case to be true, state the hypothesis :

(1)

By the definition of the sequence, we have:



Using the hypothesis, this is:



(2)

Adding (1) and (2), we have:







We have derived from thereby completing the proof by induction.
Just before yesterday I was able to prove this property without induction, using the Binet's formula. Just show that the sum of squares of the consecutives Fibonacci's number is another Fibonacci's, then find what is the index of this new term.
anyway, thank you a lot Mark! This is just what I was looking for. As I expected, the solution is really simple(after you know her). Brilliant!
juarez.asf is offline  
September 28th, 2012, 07:30 AM   #8
Newbie
 
Joined: Sep 2012

Posts: 6
Thanks: 0

Re: proving a property of the fibonacci sequence

Quote:
Originally Posted by MarkFL
After having shown the base case to be true, state the hypothesis :

(1)

By the definition of the sequence, we have:



Using the hypothesis, this is:



(2)

Adding (1) and (2), we have:







We have derived from thereby completing the proof by induction.
Realized just now: just before equation (2) you used the hypotesis on but wasn't it what you were trying to prove?
juarez.asf is offline  
September 28th, 2012, 07:37 AM   #9
Newbie
 
Joined: Sep 2012

Posts: 6
Thanks: 0

Re: proving a property of the fibonacci sequence

I belive this invalidate the demonstration.
by the way, is it possible to edit a post on the forum?
juarez.asf is offline  
September 28th, 2012, 08:56 AM   #10
Senior Member
 
MarkFL's Avatar
 
Joined: Jul 2010
From: St. Augustine, FL., U.S.A.'s oldest city

Posts: 12,168
Thanks: 472

Math Focus: Calculus/ODEs
Re: proving a property of the fibonacci sequence

Since we have assumed the hypothesis to be true, we may use it in the inductive step. I would prefer not to of course, but I have seen this done before.

Once your status changes from Newcomer, you will be able to edit posts.

Perhaps we may alleviate the problem by observing:









Continuing in this fashion, we will find:



Now we may add this to the induction hypothesis.
MarkFL is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
fibonacci, property, proving, sequence



Search tags for this page
Click on a term to search for related topics.
Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Variation on the Fibonacci Sequence Jerald_Stephan Calculus 1 December 6th, 2011 12:25 PM
Fibonacci Sequence aaron-math Calculus 2 December 6th, 2011 07:57 AM
proving the reflective property of a hyperbola rg057 Algebra 1 April 15th, 2009 09:09 AM
Fibonacci Sequence scarymovie Algebra 2 September 21st, 2008 07:27 PM
Fibonacci Sequence BobDole2000 Algebra 2 August 4th, 2008 11:18 PM





Copyright © 2018 My Math Forum. All rights reserved.