Nth term formula for the Fibonacci Sequence, (all steps included), difference equation

Nth term formula for the Fibonacci Sequence, (all steps included)
solving difference equations,
1, 1, 2, 3, 5, 8, ___, ___,
fibonacci,
math for fun
www.blackpenredpen.com

[@wojtek9395]

In next video show us how to find nth prime number

[@daltonysme8955]

wo997 he'd be rich if he knew

[@blackpenredpen]

I wish too

[@samuelminea5520]

wo997 haha

[@sergiokorochinsky49]

wo997 Riemann already found that formula more than 150 years ago... the only assumption is the famous Riemann's hypothesis, which everybody knows is true (but probably one of Godel's statements impossible to prove).

[@samuelminea5520]

Sergio Korochinsky I heard that it is a aproximation, it didn't gives you the exact value... or it's about Euler's formula?

[@warrickdawes7900]

Was waiting for it and then the golden ratio popped out! Sweet!

[@blackpenredpen]

yup!

[@BigJeff19999]

I think it would be interesting to see the result written in terms of Phi. Since (1-sqrt(5))/2 is 1-phi it's pretty readily put into that form. Is there any additional insight from writing it like that I wonder...

[@BigJeff19999]

and by phi I mean the golden ratio ...

[@stevethecatcouch6532]

How did that ψ get in there? And shouldn't those exponents be n+1?

[@MrRyanroberson1]

the golden ratio is ψ, and Fn:F(n-1)approaches golden ratio as n approaches infinity

[@nerdynerd5299]

5:46 into Fibonacci and chill and he gives you this look

[@AyushGupta-yj8jz]

That's same as your profile pic

[@heyyou7945]

Don't run away now it's just another board nothing to be scared of

[@karstenmeinders4844]

As someone with a software engineering background and little mathematical acumen I am deeply impressed because the Fibonacci series is always taught as prototype example why one needs recursive functions - which is not true as this video shows.

[@axelpaccalin1833]

I recently published a comment on this video about matrix and their application for sequences like Fibonacci. This is actually how the most most efficient implementations I know do. You might want to take a look at it if you're interested in this stuff!

[@efulmer8675]

The Fibonacci series is a great example of the need for recursive functions because it's super easy and clean and straightforward to program even though it's technically not required to write in a recursive way. Debugging a simple Fibonacci recursive program will probably be vastly easier than debugging the number of parentheses to write out the entire explicit formula (although if your programming language or math library has a phi value hardcoded then it will be substantially easier).

[@Brandon-xd5uc]

HE DID THE LEWIN DOTS AT THE END

[@blackpenredpen]

Fibonacci Sequence!

[@kezzyhko]

Please no more spoilers on the thumbnail

[@real_corn_man]

I love the video! But I don't understand fully why the fact that we get two different "r"s means that we have to try a linear combination of the two. Since we assumed r^n was f_n, shouldn't we be allowed to simply choose whichever of the two r's we prefer, raise it to the nth power, and claim that we have the nth term of the sequence?

[@blackpenredpen]

I just changed.

[@real_corn_man]

Sure I understand the analogy--but we're not doing differential equations; we're doing number theory. Why the linear combination? What are the analytical undergirdings for the procedure?

[@markzero8291]

Thank you for the awesome video. I find it very interesting that a & b are the golden ratio and its conjugate. I knew phi was related to the Fibonacci sequence as the limit of the ratio of adjacent terms as n goes to infinity, but I had no idea phi was also a part of the nth term formula. Amazing!

[@Arycke]

I remember doing this in a discrete mathematics course and it was quite interesting! When I saw it originally I was like pose it as a linear 2nd order DE as you have two initial conditions and a characteristic polynomial. I have only recently discovered you here but I enjoyed this video and all of your other videos! You are very insightful and express topics in an easy to understand way. Good job friend :) Lucas Numbers are cool too and applicable in numerical methods! Math is life

[@miweneia]

dude, I love how happy you're always on these videos, that way you make me enjoy maths again

[@blackpenredpen]

Thank you!!! Doing math is fun, so is making math videos!!!

[@Nico2718_]

4:56 when I saw "r²-r-1=0" I thought "OMG, that's amazing!" (I've already known about the relation between Fibonacci and Phi, but it keeps surprising me!)

[@wontpower]

Nice tribute to Walter Lewin at the end

[@blackpenredpen]

yes! LOL

[@chungrenkhoo9894]

I don't get the bit at 6:33. How does this have anything to do with second order linear differential equations?

[@barryhughes9764]

Brilliant sir. Absolutely brilliant. My eyes lit up when I saw the golden ratio manifest itself.

[@franciscoabusleme9085]

Wow, amazing, never seen before one of those difference equations, very clever. More like this pls!

[@carlaang109]

i do not know why but i love your face when you slide that board up HAHAHAHA. I'm also amazed by that.

[@jomama3465]

I love the sound of chalk clicking on the board XD

[@benhayter-dalgliesh5794]

Ha, my teacher uses nails

[@Sahil-ev5ms]

@@benhayter-dalgliesh5794 🤣🤣😂

[@Fire_Axus]

your feelings are irrational

[@plaustrarius]

Definitely interested in more general sequences and difference equations, explaining the motivation for the method of solution

[@vitakyo982]

This is known as Binet's formula . We are very lucky that in your demonstration the hypothesis you did start with ( f(n)=r^n ) is correct ...

[@bhagwatibhalotia7636]

Sir your channel is awesome! You make tough proofs look like a child's play. I love your videos.

[@fountainovaphilosopher8112]

That end tho...

[@blackpenredpen]

yup!

[@mchappster3790]

@@blackpenredpen what a goat

[@shardulnathtiwari4216]

Absolutely loved it Been struggling Thabk you for your kind help

[@johnskeff9617]

I would love to see more videos on Difference Equations!

[@amitbentsur6947]

I really enjoyed the math in this video and would like if you made more like it, but that ending.

[@isaacbriefer193]

Would it be reasonable to use this formula as a continuation of Fibonacci sequence? i.e. create a continuous function that has the same property as the Fibonacci sequence? Also, is there a use for such a function?

[@teddyfatimdiallo617]

That is so cool! only wondering where come from the first assumption that Fn=r^n? Can you please let me know! thank you~

[@OonHan]

for a you could have been like 1 - b = 1 - (1 / (-sqrt(5))((1 - sqrt(5)) / 2) instead of work the whole thing out again

[@minecraftkid3737]

Helpful video. I needed to find a formula for f(n)=f(n-7)+f(n-9) and with this video I was able to.

[@YoshiSohungry]

I remember proving this by induction, but this is a good way to derive as well as prove it. Nice video!

[@blackpenredpen]

Yea, Thanks

[@jay24s15]

Your amazing dude, i wish i knew you earlier... Great video.

[@ZipplyZane]

I prefer F_0 = 0, F_1 = 1 as my base when defining the formula, as it seems more pure. And it allows you to have those exponents be n, rather than n+1: which is weird, since you' think they'd have to be n-1.

[@Fire_Axus]

real

[@jimchen3641]

Would you please show how the general solution of the differences equation is equivalent to the sum of of the linear combination of the two roots?

[@saidfalah4180]

Math is very easy when you are explaining.....realy i enjoy.....

[@OLApplin]

We did that in a discrete math class, it was one of the easiest part of the class !

[@edittor1162]

I habe been searching for this for such a long time

[@sandmann6851]

You are wonderful. Why didn't you start earlyer making this video. That's exactly what I was looking for.

[@blackpenredpen]

I have been making videos for a few years now and just recently began higher level topics just for fun.

[@chhandil08]

Sir, can we find the number of term 'n' , if Fibonacci term Fn is given ? Can we have formula like this formula for it?

[@ffggddss]

0:36-Not the best choice of index. Better is F₀=0, F₁=1 (or equivalently, F₁=F₂=1), which will make the final formula a little simpler: F = (φⁿ - [-φ]⁻ⁿ)/√5 ⁿ 1:45 "n ≥ 2"-This restriction is unnecessary; removing it, facilitates extending the sequence indefinitely in the negative direction. ... -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, ... 8:20 Could simplify matters a bit by writing these as a + b = 1 ½(a + b) + ½√5(a - b) = 1 . . . 1 + √5(a - b) = 2 . . . √5(a - b) = 1 which makes it easier to obtain the solution: a + b = 1 a - b = 1/√5 a = ½(1 + 1/√5) = (√5 + 1)/(2√5) = φ/√5 b = ½(1 - 1/√5) = (√5 - 1)/(2√5) = φ⁻¹/√5

[@ibrahimjoudah]

Using the explicit formula from the begining is not efficient. The recursive formula has much less time complixity. In fact it is even faster to use the formulas: F(2n-1) = F(n)^2 + F(n-1)^2 F(2n) = F(n)^2 + 2F(n)F(n-1) If you want the general formula take a look at this paper: *On a new formula for fibonacci family m-step numbers and some applications* www.mdpi.com/2227-7390/7/9/805

[@santhiyas4092]

What you teach is awesome and easy to understand

[@christianhills8127]

great video! this really helped me on my project.

[@lt5334]

This looks like it can be applied similarly to how the factorial/gamma functions can be written as continuous integrals rather than for only discrete terms. Now we can know the 1.37th term of this sequence if we just graph this!

[@jvmguy]

Great video! This is easier, with linear algebra, if you express the recurrence relation in matrix form. A^n * [F(1),F(0)] = [ F(1+n), F(0+n)] You get the same result, of course, but fewer steps, with the eigenvalue decomposition. In this case, the eigenvalues of A are phi and 1/phi.

[@axelpaccalin1833]

Hi! First of all, I’d like to congratulate you on this greatly detailed demonstration ! Once you’ve considered the Fibonacci sequence as a 2D problem with a recurring transformation, there is a much more intuitive way to get the F(n) though. For those who aren’t familiar with matrices, what you essentially need to know about it is that it represents a transformation in a given space. Which means that for any vector U you apply it on (by matrix multiplication), you get a transformed vector V in the same space (It can be a sub-space, depending on the matrix, it's called projection and is used, for example, to draw 3D objects on 2D screen in video-games). So, let U be a 2D vector representing our Fibonacci initialisation, as: U = |0| |1| You can put 0 or 1 on the first position depending if you want F(0) = 0 or F(0) = 1 And let A be a 2D square matrix representing our transformation at each iteration, as: A = |0, 1| meaning Vx = 0*Ux + 1*Uy |1, 1| meaning Vy = 1*Ux + 1*Uy We always take Vx as our result, as a bonus we have Vy = F(n+1). for each iteration, we can do U = A * U(previous) And by the matrix formulas above, we can see that the result will be the same that the super basic approach of doing each fibonacci by adding the 2 previous ones (long but formal). But now we can see that we are just multiplying our previous vector by the same matrix n times. Which is the same as multiplying it one time but raised to the power of n. Let’s try that with F(20): We can calculate A^20 with calculator but for the sake of it, I’ll show a technique that works even with regular numbers (write downwards calculate upwards): A^20 = A^10 * A^10 = |4181, 6765| |6765,10946| A^10 = A^5 * A^5 = |34,55| |55,89| A^5 = A^2 * A^2 * A = |2,3| * |0,1| = |3, 5| |3,5| |1,1| |5, 8| A^2 = |1,1| |1,2| You might have to search for matrix multiplication :/ if you haven't seen it, you can't invent it. There is a more efficient way to raise a matrix A to the power n (A^n = P * D^n * P^-1) it's too complicated for one comment but t have a complexity of dim(A)^3 * [the complexity of the "normal" power function] so 8* in our case. But with a [0, 1] vector we practically remove the need for 4* of these 8* powers, plus we are only intrested in one element of the vecor so there only is 2* the power complexity remaining. You will essentially end up with the same algebric expression (phi^n - (1-phi)^n)/sqrt(5) (replace n by n+1 if you want it to start at 1). Finally we do A^20 * U: V = |4181*0+ 6765*1| = | 6765| |6765*0+10946*1| |10946| Vx = 6765 = F(20) (depending whether you start at 0 or 1) Vy = 10946 = F(21) To recap, F(n) = A^n * U With adjusted A and U, this can work with many other sequences (in any dimension too!).

[@Unknown-uh6du]

This is great!

[@Jihem01]

thx blackpenredpen for your videos. An elegant form of your function is: F(n):(phi^n-(1-phi)^n)/(2*phi-1) with phi the golden ratio, thx to the function fibtophi in the free computer algebra system wxMaxima, just substiute : phi for(1+sqrt(5))/2 1-phi for (1-sqrt(5))/2 (also =-1/phi) 1/(2*phi-1) for 1/sqrt(5) regards PS phi is also equal to 2* cos(pi/5)

[@christyjhoyllanes1754]

How to solve this number 1, 10, 100, 1000 in the sequence for its rule and how to identify this in the next three terms?

[@expose954]

@Blackpenredpen can u make a video on summation formula for 5 degree power series?

[@RAJSINGH-of9iy]

Is there any method or formula to check whether a number is prime or not???

[@janeeneirishbaja3765]

wait... where did you get the equation at 3:04 ??

[@MarcoMate87]

At 4:50, instead of dividing both sides by r^n and then multipling them by r^2, you could simply divide by r^(n-2). Anyway, what a beautiful proof!

[@subarnasubedi7938]

Why do you choose r^n as general solution?

[@ignorantinformer]

I understand that it works, I simply just don't understand what logical step led you to input the values of the geometric progression into the arithmetic expression of the fibonacci curve can somebody please explain.

[@whydontiknowthat]

Nice video! I had to do this problem for my linear algebra course last year for general recursive sequences of the form you described on a problem set, except that I didn't find a formula when the quadratic r^2-r-1=0 did not have any solutions. It required proving that recursive sequences of the form you described are a vector space, the sequences r_1 and r_2 are linearly independent, then finding the formula itself. It was annoying, but rewarding.

[@looney1023]

Mathologer made a cool video about this formula and the corresponding tribonnaci number formula. Another cool thing is that the base of the second term has a magnitude less than 1, so as n increases, this term --> 0. So you can just omit that term and the first term rounded to the nearest integer will be your fibonacci number!

[@manuelodabashian]

How about trying to find 2^n power is this possible?

[@sil1235]

In practice (and in some number theoretic proofs) it is more practical to avoid floating point arithmetic / real numbers and instead use formula given by matrix exponentiation, which itself can be accelerated by standard tricks for fast exponentiation. | 1 1 | ^n | F_(n+1) F_n | | 1 0 | = | F_n F_(n-1) |

[@AnonimityAssured]

Although it could be argued that the numbering of the terms in any Fibonacci-type sequence is essentially arbitrary, certain properties of the terms in the Fibonacci sequence and the Lucas numbers (and perhaps of certain other sequences based on the same additive principle) are expressed in relation to their "normal" numbering. For example: if F[n] is a prime other than 3, then n is prime (although not necessarily vice versa); if n is prime, then L[n] - 1 is divisible by n (although a small proportion of composite numbers, called Bruckman-Lucas pseudoprimes, share this property); F[n]·L[n] = F[2n]; and (F[n]·L[n+1] + L[n]·F[n+1]) / 2 = F[2n+1]. If the numbering is changed even slightly, such observations, along with a host of others, will no longer be true. Hence, the 0th term of the Fibonacci sequence is normally 0 and the 1st term is 1, while the 0th term of the Lucas numbers is 2 and the 1st term is 1. Such numbering also simplifies Binet's formula for Fibonacci numbers and the closely related formula for Lucas numbers.

[@requitLuv]

Thank you so much for this video !

[@goksu9798]

Is this what they call second order recurrence relation? I need an answer really quick

[@Gold161803]

Nice video, but like others have said, you've skipped over some crucial intuition. In any case, I prefer the derivation involving generating functions

[@bentekkie]

can you go into more detail with the difference equations

[@whabADDANKIHARIPRASANNA]

Will this work if we have different starting values (other than 1, 1) and calculate a and b accordingly?

[@ilprincipe8094]

It should

[@efulmer8675]

The most amazing thing about the end formula (known as the Binet Formula) is that if you break the terms under the n exponent into something more compact by noticing that they are the golden ratio and the negative inverse golden ratio, you get a very "Fibonacci-y" formula.

[@carlturner1027]

Mr. blackpenredpen; I find it a leap to ASSUME Fn could equal some r^n; I follow all else but that initial assumption. In general, I am crazy about your presentations--great 'stage' presence--

[@Arsalankhan_2003]

me who likes to torture myself , started studying and realised i hadn't made a c program for nth term of Fibonacci sequence (don't wanna do recursion) and here i am (and yes i subscribed , man you teach in a really intreating way ) edit: man you are a life saver,

[@_HaSSaaN_]

I laughed very much when you increase the speed of video!

[@jeremymenage1566]

I put this into a spreadsheet. It works a treat.

[@expose954]

How did u know that the general term was a difference of two geometric progression?

[@expose954]

It could have been any function?

[@rudboy9599]

my question too. I guess we just assume it can?

[@leoitshere]

It's a case of: you conjecture that a solution has a certain form and then it works.

[@expose954]

leoitshere how can you prove it's a unique solution?

[@stevethecatcouch6532]

+ritik agrawal If you want to prove that those are the only values for r1 and r2 given that the solution is a linear combination of r1 and r2, just note that r1 and r2 are the only solutions of the equation r^2 - r - 1 = 0. If you are asking if Fn can be calculated using a completely different expression, I don't know.

[@abdulwadoodkhan5591]

in some explicit formula for the Fibonacci sequence there is only power "n" and (Sir)you write "n+1" at the end which one is correct.

[@expose954]

I want exact prove that it's difference of two geometric progression??

[@andenggg4904]

What happens if you try to use a difference table to determine Fibonacci numbers? Thank you in advance for the answer! 😁

[@drscott1]

Can n be negative or imaginary ? What happens then?

[@user-vs3lw6xs7n]

What it the reason behind pluging r^n into Fn ? Is it simply because it "looks" like a differential equation ?

[@divyaaarthi4996]

kzbin.info/www/bejne/aafFeYefa9h8epI

[@vkilgore11]

Definitely do some more like this.

[@JB-iz8bi]

It's so obvious but still so amazing that phi finds its way into something like this

[@renzalightning6008]

I remember working this out, we used Z-transforms, but this seems much nicer (unless he used them without explaining them XD been a while :P )

[@tyronekim3506]

Brilliant!!

[@megathetoxic]

you're the best! the formula is a bit complicated with numbers and stuff so can we just substitute the golden ratio with its respective symbol?

[@Theo_Caro]

Yup

[@federicoforgione]

Some years ago I found a cool correlation between the factors of the powers of phi written as phi^n=a*phi+b, and the numbers in the Fibonacci sequence, but I didn't have at the time a cool equation like this to find ecery number of the Fibonacci serie given the position n. Now i can correlate the two things into an harmonious formula, and I can prove that the ration between two adjacent numbers of the Fibonacci formula is exactly Phi! This video was so illuminating! Cheers from Italy (sorry for the bad english)

[@konstanty8094]

11:10 you could have just plugged the a value and find b from single equation.

[@Zwaks]

Started learning this this year in Discrete Structures

[@Fire_Axus]

how did you know the result was of the form a(r1)^n+b(r2)^n?

[@baxtertothemax]

i though tthat was a recurisive defintion, also does anyone know where to find an explation of how to do this with linear algebra?

[@edieman24]

Look at the wikipedia page on fibonacci numbers under math. You have to use matrix diagonization.

[@MegaAlindo]

Damn bro that was awesome, thank you

[@nabajeetborah759]

In 13:31 , it was actually that you multiplied [-{1+√5}/2] with 1 but then you subtracted that portion from 1 .How?

[@GreaTeacheRopke97]

i also struggled with the difference equation lacking justification (though i totally understand why, having read the comments). for anyone else who is disappointed by not understanding the justification for it and really wants a solid proof (whether for yourself or for talented students), i would recommend just going for induction. it's probably more accessible for most people.

[@morphos2]

Please do more difference equations

[@michaelsheldrew1818]

How would you do ....r^n=r^(n-1)*n form . ?????

[@JLindo97]

How interesting is using this general formula with negative values of n. F_(-1)=0 and as long as you decrease the value of n you get the Fibonacci sequence with alternate signs: 1 -1 2 -3 5 -8 13 -21 34 -55 and so on. In fact this sequence verify the condition F_(n-2)+F_(n-1)=F_n even if the n value is negative so it's nothing extraordinary but I think it's really curious.

[@manishkumarsingh3082]

I didn't got how f(n)=r^n??

[@vibhavaggarwal237]

You should really do a video to explain why this method works.

[@harlbertmayerh7523]

I didn't know when we can start with n sub zero , when we can start with n sub 1 , can someone explain?

[@sergiydobrovolskyy4527]

What is he saying at 4:40? I didn´t understand, my english is not good.

[@johncowart9536]

Perhaps I'm doing something wrong, but this formula seems to give you the answer for F(n+1), not F(n). If I choose N=7, plug into the formula I get 1/5^(1/2) * ( [phi]^8 - [1/phi]^8 ) = 21. F(7) = 13, F(8) = 21 Same for any other number. The formula appears to be F(n) = 1/5^(1/2) * ( [phi]^n - [1/phi]^n ) Double check anyone?

[@Vidrinskas]

Worth mentioning that the second term in the answer is always less than one half, so the nth f-number is the closest integer to the 1st term.

[@ABaumstumpf]

F0 = 0. Fibonacchi started his sequence with F1 = 1 and F2 = 1.

[@madhoomishra8933]

What is Dusart formula please explain

[@mostafadid]

when I use this formula to fibonacci it give us the next fibonacci like fib 10 =55 it give fib 10=89 but when remove the on from the power it gives the correct answer can you explain why ?

[@angelodc1652]

He says that 0 is F(1) but you say that 0 is F(0)

[@joaolopes7302]

i could do this but with linear algebra. still nice to see

[@t00by00zer]

PHI raised to the Nth power gives you the nth term when rounded to the nearest integer.

[@piyushverma7774]

man hats off to you keep it up

[@blackpenredpen]

Thank you!

[@diedoktor]

You only have to do n+1 because the sequence is offset by 1. If you started at 0 so f sub 0=0 and f sub 1 = 1 then a would just be 1/sqrt(5) instead.

[@carlosmurray4520]

Where did that Fn=a(r1)^n+b(r2)^n come from? o.0

[@U014B]

Nice! Does this also work for non-integer values of n?

[@erikmensinga]

Yes i think

[@Farzriyaz]

NOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO thats why my program requires the users input to be an input // fibonacci sequence function fibonacci(x) { return x % 1 == 0 && x == Math.abs(x) ? (x == 0 || x == 1 ? x : fibonacci(x - 1) + fibonacci(x - 2)) : 0 / 0; } console.log(fibonacci(promptNum("Enter a number for the program to print something.")));

[@Farzriyaz]

and im very sorry for spamming a javascript program and things about it