My Math Forum Find non recursive formula for the fibonacci sequence

 Number Theory Number Theory Math Forum

 May 22nd, 2009, 03:55 PM #1 Newbie   Joined: Feb 2008 Posts: 11 Thanks: 0 Find non recursive formula for the fibonacci sequence Hey there guys, I have a question in my assignment that asks to find a non recursive formula for the fibonacci sequence. Im pretty much going to bail on the question as I have no idea even where start. I know the non recursive formula however I have no idea how to arrive at the result using characteristic equations. The book we are using is pretty confusing as it really does not show a step by step example so I really can't grasp the concepts. The book we are using is Discrete Mathematics for Computing by Peter Grossman I was wondering if anyone knows how to solve this type of question or can put me on the right track as how to even attempt this question, or does anyone know of any resources that I could use to help me. Any information would be great !! Cheers Trev
 May 22nd, 2009, 04:42 PM #2 Senior Member   Joined: May 2008 From: York, UK Posts: 1,300 Thanks: 0 Re: Find non recursive formula for the fibonacci sequence The Fibonacci numbers $f_n$ satisfy $\begin{pmatrix}f_{n+1}\\f_n\end{pmatrix}=\begin{pm atrix}1&1\\\=&\ \\\=&\ \\\=&\ \\1=&0\end{pmatrix}\begin{pmatrix}f_n\\f_{n-1}\end{pmatrix}.=$ Therefore we can show that $\begin{pmatrix}f_{n+1}\\f_n\end{pmatrix}=\begin{pm atrix}1&1\\\\\=&\ \\\=&\ \\\=&\ \\1=&0\end{pmatrix}^n\begin{pmatrix}1\\\=&\ \\\=&\ \\\=&\ \\0\end{pmatrix}=$ and so by diagonalising the matrix $\begin{pmatrix}1&1\\\ &\ \\\ &\ \\\ &\ \\1&0\end{pmatrix},$ you can find the non-recursive formula.
 May 22nd, 2009, 05:03 PM #3 Newbie   Joined: Feb 2008 Posts: 11 Thanks: 0 Re: Find non recursive formula for the fibonacci sequence We have not been taught how to solve linear recurrences using matrices, so I probably should not use that method. We are to solve it by working out the characteristic equation first which I am not sure how to do, then solve the fibonacci sequence from there. Thanks for the help anyway ! Trev
 May 22nd, 2009, 09:08 PM #4 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: Find non recursive formula for the fibonacci sequence In the end you'll just have two exponential terms added or subtracted together. It's easy enough to find the first (large) term -- just find the expected ratio between numbers. You can then solve for the second term with small numbers, then prove that the recurrence relation holds.
 May 29th, 2009, 02:16 PM #5 Newbie   Joined: Jul 2008 Posts: 7 Thanks: 0 Re: Find non recursive formula for the fibonacci sequence Do you want Binet's formula? F(n) = ( g^n - (1-g)^n) / sqrt(5) where g = (1 + sqrt(5))/2 ? That's not recursive.
 May 29th, 2009, 08:58 PM #6 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: Find non recursive formula for the fibonacci sequence I assumed that's what was desired.

 Tags fibonacci, find, formula, recursive, sequence

,

,

,

,

### non recursive fibonacci formula

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

 Similar Threads Thread Thread Starter Forum Replies Last Post aaron-math Calculus 2 December 6th, 2011 07:57 AM fe phi fo Applied Math 1 December 4th, 2011 03:04 PM milagros Real Analysis 0 October 26th, 2011 11:46 AM BobDole2000 Algebra 2 August 4th, 2008 11:18 PM Sheelby Algebra 0 March 3rd, 2008 02:25 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top