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
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).
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...
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.
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!
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).
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
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?
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?
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!
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!)
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
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
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.
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.
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!).
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.
+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.
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) |
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!
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.
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)
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.")));
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--
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)
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.
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.
There are just two important steps, and of course he glances over them: 3:14 "Fn = r^n, this is the idea" although F1 = 1 would mean r = 1 ! 6:20 Here comes the actual ansatz. He kind of justifies this with the correct analogy to differential equations, but it would have been much better to make a video about why this works, instead of wasting our time with extremely trivial algebra.
I meant only in comparison to the important ideas I mentioned. Everybody who understands the implied analogy between difference equations and differential equations immediately sees the solutions of a simple quadratic equation. Sorry, I got a bit frustrated, because the same thing often happened in lectures and I had to work out the underlying ideas by myself.
Etothe2iPi Something off topic: Is "ansatz" part of math terminology? Because it is the German word for "approach". I am always a little fascinated when I see German words in English :)
I understand. That has to be a separate video to talk about difference between difference eq and differential eq (I didn't want to do it here otherwise this video would have been over 30 minutes long..)
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!
You're right: the recursive approach is not fun :J (especially to computers). The real fun is to figure out how to cut off all the repeating branches of the recursion to make it linear (that is, iterative) instead of exponential ;> And even more fun is to find a way to compute it even faster, in logarithmic time and (small) constant space :> (I'll tell you how in a separate comment.) Binet's formula (the one you arduously calculated in your video but forgot to simplify at the end) indeed allows to calculate the `n`th Fibonacci number without the need of calculating all the previous ones, but only in theory. In practise, though, it turns out that the round-off errors pile up pretty quick and the calculations become numerically unstable, and if you're not careful enough, it can happen before you even reach the 100th number. Your answer could simply end up being incorrect :P
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.
Curious fact: This closed-form expression for F(n) can be applied for any real (or even complex!) n; but it's a real number for all integers n, and only for integers n.
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?
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?
Wait. Even if r is equal to 0. You would just arrive in 1=1/r+1/r^2. Which you'll multiply the entire equation by r^2... Which would ultimately give you x^2=x+1... Still arrive in the same step in getting the quadratic equation...
Long story short: Is it possible to find the sum of the Fibonacci sequence starting from a certain point and ending on another point. IE Is there a formula to get the sum of the 8th number to the 13th number? This comes up occasionally in some of the math in games I play. I've never found a formula for it. I can have my computer compute it for small sums, but it turn out that I occasionally need hundreds of thousands of terms which I can't do in a small time. A formula would save me lots and lots of work. Thanks! Edit: An actual formula would be great, but if it can be approximated to within 1% with some other formula, that'd work too.
sum=((((1+5^0.5)/2)^(n+1)*(2*((1+5^0.5)/2)^(p+1)-2)/(5^0.5-1)-((1-5^0.5)/2)^(n+1)*(2+(5^0.5-1)*((1-5^0.5)/2)^p)/(1+5^0.5))*5^-0.5) .for example n = 8 and p = 13-8 = 5; sum=932,but as this appears in your games I do not know.
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,
OMG dude! I've never seen this method before! A while ago i wanted to show that the following recursive equation is equal to the number of derangements, i.e.: F(n)=[F(n-1)+F(n-2)]*(n-1) = !n Now i think i could give that another try :) I just don't understand why we're supposed to use both the solutions of R...usually we find a solution and then we plug it in the main equation. So why both of them? What's the logic behind that particular step?
Well, i tried the method but to no avail. In the meantime i realized what i was doing. In a nutshell, the method consists in finding the binomial expansion of a recursive equation (x+y)^n where x+y=r. I got the logic now :)
Having the Fibonacci sequence start with 0,1 instead of 1,1(that is F(0) = 0, F(1) = 1) makes the calculation simpler, as it makes a=1/sqrt(5), b=-1/sqrt(5).
I prefer (GoldenRatio^n)/sqrt(5) which can be calculated fast, but is inaccurate. If an exact answer is needed then subtract ((-GoldenRatio)^-n)/sqrt(5) from that. For fractional values of n, ((-GoldenRatio)^-n)/sqrt(5) becomes (GoldenRatio^-n*cos(n*pi))/sqrt(5).
Have you seen the Maths Montage videos on Fibonacci sequences yet? I will be publishing the general formula for producing an infinite number of Binet style formulas of this type, shortly. Good work and all the best, Anthony Candy.
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.
Look, are we forced to use the general term as a power? Maybe, if we come up with a different general form, we obtain a more calculable answer? And what about the generating function (if I call it right), the Taylor coeffs of which happen to be the Fibonacci numbers?
This is a unique solution, and it would be obtained regardless of whether you use the function generator or assume a geometric sequence. The most efficient method, however, is by using matrix algebra by taking advantage of the recursive relationships that you obtain from the definition of the sequence itself and then iterating the matrix multiplication, then solving for the extracted entry that will yield the generalized function. Then the reason for assuming an exponential is obvious: linear transformations are equivalent to matrix multiplication in component space.
