My Math Forum proving a property of the fibonacci sequence

 Number Theory Number Theory Math Forum

 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: $F_{2n-1}= F_n^2 + F_{n-1}^2$ where $F_n$ means the $n^{th}$ 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.
 September 25th, 2012, 11:28 AM #2 Global Moderator     Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 938 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).
 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
 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!
 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 $F_{2n}$ while on the right $F_n^2$. Those index are really kiling me. I didn't find a relation betwen then, no way to convert one into another.
 September 25th, 2012, 06:36 PM #6 Senior Member     Joined: Jul 2010 From: St. Augustine, FL., U.S.A.'s oldest city Posts: 12,204 Thanks: 511 Math Focus: Calculus/ODEs Re: proving a property of the fibonacci sequence After having shown the base case to be true, state the hypothesis $P_n$: (1) $F_{2n-1}=F_{n}^2+F_{n-1}^2$ By the definition of the sequence, we have: $F_{2n}=F_{2n+1}-F_{2n-1}$ Using the hypothesis, this is: $F_{2n}=F_{n+1}^2+F_{n}^2-F_{n^2}-F_{n-1}^2=F_{n+1}^2-F_{n-1}^2$ (2) $F_{2n}=F_{n+1}^2-F_{n-1}^2$ Adding (1) and (2), we have: $F_{2n-1}+F_{2n}=F_{n+1}^2+F_{n}^2$ $F_{2n+1}=F_{n+1}^2+F_{n}^2$ $F_{2(n+1)-1}=F_{n+1}^2+F_{(n+1)-1}^2$ We have derived $P_{n+1}$ from $P_n$ thereby completing the proof by induction.
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 $P_n$: (1) $F_{2n-1}=F_{n}^2+F_{n-1}^2$ By the definition of the sequence, we have: $F_{2n}=F_{2n+1}-F_{2n-1}$ Using the hypothesis, this is: $F_{2n}=F_{n+1}^2+F_{n}^2-F_{n^2}-F_{n-1}^2=F_{n+1}^2-F_{n-1}^2$ (2) $F_{2n}=F_{n+1}^2-F_{n-1}^2$ Adding (1) and (2), we have: $F_{2n-1}+F_{2n}=F_{n+1}^2+F_{n}^2$ $F_{2n+1}=F_{n+1}^2+F_{n}^2$ $F_{2(n+1)-1}=F_{n+1}^2+F_{(n+1)-1}^2$ We have derived $P_{n+1}$ from $P_n$ 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!

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 $P_n$: (1) $F_{2n-1}=F_{n}^2+F_{n-1}^2$ By the definition of the sequence, we have: $F_{2n}=F_{2n+1}-F_{2n-1}$ Using the hypothesis, this is: $F_{2n}=F_{n+1}^2+F_{n}^2-F_{n^2}-F_{n-1}^2=F_{n+1}^2-F_{n-1}^2$ (2) $F_{2n}=F_{n+1}^2-F_{n-1}^2$ Adding (1) and (2), we have: $F_{2n-1}+F_{2n}=F_{n+1}^2+F_{n}^2$ $F_{2n+1}=F_{n+1}^2+F_{n}^2$ $F_{2(n+1)-1}=F_{n+1}^2+F_{(n+1)-1}^2$ We have derived $P_{n+1}$ from $P_n$ thereby completing the proof by induction.
Realized just now: just before equation (2) you used the hypotesis on $F_{2n+1}$ but wasn't it what you were trying to prove?

 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?
 September 28th, 2012, 08:56 AM #10 Senior Member     Joined: Jul 2010 From: St. Augustine, FL., U.S.A.'s oldest city Posts: 12,204 Thanks: 511 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: $F_{2n}=F_{2n-1}+F_{2n-2}$ $F_{2n}=F_{2n-2}+F_{2n-3}+F_{2n-2}=F_3F_{2n-2}+F_2F_{2n-3}$ $F_{2n}=F_3$$F_{2n-3}+F_{2n-4}$$+F_2F_{2n-3}=$$F_2+F_3$$F_{2n-3}+F_3F_{2n-4}=F_4F_{2n-3}+F_3F_{2n-4}$ $F_{2n}=F_4$$F_{2n-4}+F_{2n-5}$$+F_3F_{2n-4}=F_5F_{2n-4}+F_4F_{2n-5}$ Continuing in this fashion, we will find: $F_{2n}=F_{n+1}F_{2n-n}+F_{n}F_{2n-(n+1)}=F_n$$F_{n+1}+F_{n-1}$$=$$F_{n+1}-F_{n-1}$$$$F_{n+1}+F_{n-1}$$=F_{n+1}^2-F_{n-1}^2$ Now we may add this to the induction hypothesis.

 Tags fibonacci, property, proving, sequence

,

,

,

,

,

,

,

,

# summation of squares of fibonacci numbers proof by induction

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

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

 Contact - Home - Forums - Cryptocurrency Forum - Top