 # Exercise – Write a Fibonacci Function

This right here is a
picture of Fibonacci, one of the most famous
mathematicians of all time, and he was a mathematician
in medieval Italy. And he’s most famous for
the Fibonacci numbers. And he didn’t discover them. They were actually discovered
several centuries before him in India, but he popularized
them, especially in the West. And the Fibonacci
numbers are super simple. The first two are
defined as 0 and 1. And every number after that is
the sum of the previous two. So what I’m
constructing right here is really a Fibonacci
sequence of numbers. So the next number
in the sequence is going to be 0 plus
1, which is 1, Then the next number after that
is going to be 1 plus 1, which is 2. Then the next number
after that 1 plus 2 is 3. 2 plus 3 is 5. 3 plus 5 is 8. 5 plus 8 is 13. 8 plus 13 is 21. 13 plus 21 is 34. And the Fibonacci
numbers, especially once you start getting into
number theories, tons of fascinating
things about them. But probably the
more terms to the Fibonacci sequence, and you take
the last two terms that you’ve generated, obviously
there is no really last two terms. You could keep going on
forever, get arbitrarily large Fibonacci numbers. But say we take these last two
terms over here, 21 and 34. If we take the ratio of
these two, 21 over 34, this is going to be pretty
close to the golden ratio. And I encourage you to look up
the golden ratio on Wikipedia and the internet. You’ll find all sorts of
fascinating and mystical things about the golden ratio. What’s cool about the Fibonacci
numbers, or the Fibonacci sequence, this gives
you an approximation of the golden ratio. You’ll get even a
better approximation if you add another
term to our sequence. So the next term over
here, 21 plus 34 is 55. So the ratio of 34 to 55 is
even closer to the golden ratio. So one way, if you
wanted to compute a really good approximation
for the golden ratio, you could really just get
super high Fibonacci numbers just adding the previous two
terms to get the next one. And you will get a pretty
good approximation, when you take the ratio
of the last two terms. Now that’s what the
Fibonacci numbers are about, and now I want to pose
a challenge to you. I want you to write,
since we’ve already done some examples
using factorial, I want you to write
an implementation of a function that generates
the n-th term in the Fibonacci sequence. So the function
will be like this. So if I call your function–
Let me make it a lowercase. Let me just give
you some examples. So if I take your function,
and I call Fibonacci– and you could really implement
this in any language you want, although we’ve been
dealing in Python, it might be simplest
to do it in Python– if I call fibonacci of
1, what I want this to be is the first term. And just to make things
clear, and you should always clarify this, especially
in computer science, because it’s not always
clear what the first term is. And I’m going to make
it clear right now. The first term is not going
to be this one over here. I’m going to make it
this one over here. I’m going to call
this the 0-th term. That’s the 0-th
term, and then that is going to be the first term. This is going to be the second
term, third term, fourth term, so on and so forth. And so Fibonacci of
1, the first term will be this right over here. It should return 1. So Fibonacci of 0
should return 0. Fibonacci of 3 should
return 0, 1, 2, 3. It should return 2. Fibonacci of 5 should
return 0, 1, 2, 3, 4, 5. It should actually return 5. And what I want you to
do is write a function so we could put in
any argument over here and it will return that third
term of the Fibonacci sequence.

## 37 thoughts to “Exercise – Write a Fibonacci Function”

1. Riyadh Elalami says:

def Fibonacci (towhich):
towhich=towhich-2
number=0
number2=1
for i in range(towhich):
temp=number2
number2=number+number2
number = temp
print(number2)

Fibonacci(input("enter the number of term"))

2. jiykauu says:

thanks!

3. Jaleb says:

f(x)=f(x-1)+f(x-2)
f(0)=0, f(1)=1; at least that is the way I've always learned to do it.

4. jjkul1 says:

U_(k)=U_(k-2)+U_(k-1) ; U_0=0, U_1=1

5. Ferrus91 says:

Dynammic programming is the way to go.

6. Gilberto Montoya says:

the first example should be 34/21 which is closer to Golden Ratio 1,61… instead of 21/34. THANKS FOR YOUR VIDEOS HELP ME A LOT TO UNDERSTAND EVERYTHING IN MY UNIVERSITY, Typing from Cali, Colombia!

7. armpitpuncher says:

For anyone who doesn't have python or any other programing language implementation installed, and for some reason can't download one, check out ideone.com. Actually, I use it often even though I have several language implementations installed, because it's really convenient.

8. disbandedNinja says:

this was a test i received in my first job interview, haha.

9. disbandedNinja says:

btw, i think you should use R instead of python for your math lectures.

10. littleindia says:

Or you can just use the fibonacci function =p

11. Fasolati says:

Man we are on infinite series and we came up on this in my Calc 2 class.

12. IceFurnace says:

Visual Basic

Private Function fibonacci(ByVal term As Integer)
Dim value As Integer = 1
Dim prevalue As Integer = 0
Dim i As Integer = 0

Do Until i = term
value += prevalue
prevalue = value – prevalue
i += 1
Loop

Return value
End Function

the initial value of i is the first term, so in this case it starts at 0

13. krazedkat says:

Just to solidify what Khan was saying about the ratio being approx. = golden ratio
As F(n) -> inf
F(n)/F(n-1) -> phi

14. IceFurnace says:

the golden ration is ~34/21 not 21/34 (1.62)

15. Cagebreaker21 says:

lol at all the incorrect answers, not a recursive function!!!

16. PedroGynVibes says:

Does it really matter if we say 34/21 or 21/34 … the ratio is the same, just the result of the division is different.

17. Danielle MacDonald says:

I suggest a tuple in python. This was the line that took me a moment:
for i in range(term):
Careful not to let it trick you, remember range starts counting from 0. I'd paste my solution, but I don't wanna let everyone cheat. 🙂
My solution took 5 lines, so it's a relatively simple function to implement. Just careful about your order of assignments if you use separate variables for your terms. That's why I found a tuple easier.

18. superdau says:

@IceFurnace
It's the same ratio. It doesn't matter if you got 1:1,62 or 1,62:1.

19. zachem66 says:

@personkid20 shut up u douche

20. shazamo says:

@personkid20
Right….

21. athyh377 says:

ur smart

22. Carlos Henrique Machado Dias says:

Plz, use the CC function "Transcribe audio" and have fun wit the "Feminazi sequece" numbers and the "field nazis sequence"

23. hector ramos says:

that is the inverse of the golden ratio

24. superdau says:

Dude, "1,62" isn't even a ratio (1:1,62 or 0,62:1 would be).
Btw. do the math by your own definition: guess what (0,62+1)/1 equals (i. e. sum of two values divided by the larger of the two)? Guess what (1,62+1)/1,62 equals? Guess what (1+1,62)/1,62 equals?

25. Tabris Hayayi says:

he deserves one

26. Mattyd951 says:

Look up Binet's formula:

Fib(n)=((Phi^n) -(-Phi)^(-n))/√5

I could prove it, but the comments section is too small.

27. Joe Holland says:

Challenge accepted

28. مدينة العلم says:

This is the code ####

def fibon(number):
if(number == 0):
return 0
elif(number == 1 or number == 2):
return 1
else:
n = 0
m =1
l = m
for i in range(number-2):
m =  n +  m
n = l
l = m
return m

num = int(input("please inter a number : "))

print (fibon(num))

29. IThoughtYouWereMyGhost says:

I got lost on fib (3) 🙁

30. arya tirta says:

1980

31. Ashim Paudel says:

Hey Sal!
Can you make a video to Print all Prime Numbers in an Interval?

32. Timothy Wan says:

import math
def fibonacci(x):
phi=(1+math.sqrt(5))/2
term=lambda x:((phi^x)-(-phi^(-x)))/math.sqrt(5)
return term;

Is this correct?

33. Princess Pickles says:

Thank you, thank you, thank you, thank you!!!!!!!

34. Mohammed Ahmed says:

WHAT FOR FORMULA SHOULD I USE TO GET 34TH TERM OF FIBONACCI SEQUENCE OR HOW DO I GET 34TH FIBONACCI TERM THANKS

35. Jake Ambrose says:

theres no way anyone would have a clue how to write that by this point if their only experience was this tutorial

36. Jigar Prajapati says:

You already have a Video on golden ratio bro

37. Randomesque says:

13*2=26-5=21*2=42-8=34*2=68-13=55*2=110-21=89*2=178-34=144*2=288-55=233*2=466-89=377*2=754-144=610*2=1220-233=987*2=1974-377=1597*2=3194-610=2584*2=5168-987=4181*2=8362-1597=6765*2=13530-2584=10946. This pattern just keeps going. Can someone please explain why this happens? PLEASE?