Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

My lecturer was explaining how the Fibonacci sequence can be displayed for a number n.

The formula is fib(n)=fib(n-1) +fib(n-2)

Say we had to find the fib for 5 that would be:

fib(5)= fib(5-1) +fib(5-2)

=fib(4) + fib(3)

=fib(3) +fib(1)

=fib(2) + fib (-1)?

This is where i get stuck on the sequence, when you hit 1. Do you stop at 1 or keep applying the formula, and if we stop at 1 why?

I am also confused to how we actually reach 5 at the end of the sequence, do we just add up trailing 1s?

Could someone explain the remaining sequence please?

Thanks in advance!

Solved***

Since i have low reputation, i cant answer my own question so i will post here:

okay so i've worked it out how to do it recursively which gives me a better understanding of how the sequence works! firstly we must use the following recursive algorithm (i have coded in python):

def fib(n):

if n==0:
   return 0
elif n==1
   return 1   
return (fib(n-1)+fib(n-2))

This is how it goes:

Fib (5)

to get to fib (5) you need to work out what fib(4) is:

fib(4) =fib(3) + fib(2)

to find this out you need to work out what fib(3) is:

fib(3) = fib(2) +fib(1)

to find out what fib(3) is you need to find out what fib(2) is:

fib(2) = fib(1)+fib(0)

and we know that fib(1) = 1 because the algorithm states if n=1 return 1.

so now we can work our way back up to find the values:

fib(2) = fib(1)+fib(0) = 1

fib(3) = fib(2) +fib(1) = 1 + 1 = 2

fib(4) =fib(3) + fib(2) = 2 + 1 = 3

now we know what fib (4) and fib(3) is we can work out what fib(5) is:

fib(5) = fib(4) + fib(3) = 3 + 2 = 5

Hope this helped anyone who had the same confusion as me!

share|improve this question
1  
Two things: We fix the values of $fib(0)$ and $fib(1)$ to start with, so we know what to do when we get down to those values. Also, you have not applied the recursive rule correctly. You should be getting more and more terms. –  Tobias Kildetoft Oct 1 '13 at 10:41
    
Do you mean something like $f(5)=f(4)+f(3) $ $= 2f(3)+f(2) $ $= 3f(2)+2f(1) $ $=5f(1)+3f(0) $ $= 5\times 1 +3 \times 0 =5$? –  Henry Oct 1 '13 at 11:00

1 Answer 1

In Fibonacci sequence (Recursive sequence in general), you need to determine the first two term of $f(n)$, namely $f(1)$ and $f(2)$. For example, if you choose $f(1)=f(2)=1$ then $$f(3) = f(2) + f(1) = 2$$ $$f(4) = f(3) + f(2) = 3$$ ..... and so on

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.