1

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!

Alonso
  • 435
  • 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 01 '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 01 '13 at 11:00

1 Answers1

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

Redsbefall
  • 4,845