Math Is Fun Forum

fibbingfibonacci

Guest

Prove Fibonacci Sequence

Help! I have no idea where to start with this!

"Prove that the formula:

is true for all fibonacci numbers."

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Prove Fibonacci Sequence

I cleaned up your latex, and deleted the two subsequent posts.  Remember in latex, every symbol (including varphi) requires a '\' before it.  But this was not the only issue.  Even with proper latex code, it still would not work.  I think you copied and pasted the code from somewhere, and formatting (invisible) characters were included in the mix.  This confuses and upsets latex.

As to your question: Which method should one use to prove almost any statement about a recurrence relation?

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

fibbingfibonacci

Guest

Re: Prove Fibonacci Sequence

I.....don't know...

Well I know how to get to that formula though, but, my professor said that that is not what the question is asking. I know that you get a difference equation, F[sub]n[/sub] = F[sub]n-1[/sub] + F[sub]n-2[/sub]

And of course a solution is F[sub]n[/sub] = k[sup]n[/sup]

And from there all we have to do is solve the quadratic equation, k² - k - 1 = 0 to get the formula.....but how do I prove that the formula works? Can't find any useful pages anywhre.......

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Prove Fibonacci Sequence

I.....don't know...

Induction is a very powerful tool when it comes to recurrence because of how much it allows you to assume.  Start off with the base case and inductive hypothesis, then do as much as you can till you get stuck.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

numen

Member

Registered: 2006-05-03

Posts: 115

Re: Prove Fibonacci Sequence

How far have you got, fibbingfibonacci? I have a solution to your problem, you need to use induction.

---

Bang postponed. Not big enough. Reboot.