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 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!
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
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.
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!).
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.
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)
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)
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.
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.")));
+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.
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.
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!
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.
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,
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!
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?
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.
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--
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.
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?
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
Look up linearality. Based on the condition of the difference equation we are looking for two linearly independent solutions, namely r_1 and r_2 that satisfy F_n=a*r_1^n+b*r_2^n.
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.
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..)
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.
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.
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).
![The most beautiful equation in math, explained visually [Euler’s Formula]](http://i.ytimg.com/vi/f8CXG7dS-D0/mqdefault.jpg)
![The most beautiful equation in math, explained visually [Euler’s Formula]](/img/tr.png)
In next video show us how to find nth prime number
wo997 he'd be rich if he knew
I wish too
wo997 haha
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).
Sergio Korochinsky I heard that it is a aproximation, it didn't gives you the exact value... or it's about Euler's formula?
Was waiting for it and then the golden ratio popped out! Sweet!
yup!
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...
and by phi I mean the golden ratio ...
How did that ψ get in there? And shouldn't those exponents be n+1?
the golden ratio is ψ, and Fn:F(n-1)approaches golden ratio as n approaches infinity
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).
Fibonacci Sequence!
Please no more spoilers on the thumbnail
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?
I just changed.
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!
5:46 into Fibonacci and chill and he gives you this look
That's same as your profile pic
Don't run away now it's just another board nothing to be scared of
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
dude, I love how happy you're always on these videos, that way you make me enjoy maths again
Thank you!!! Doing math is fun, so is making math videos!!!
HE DID THE LEWIN DOTS AT THE END
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
Nice tribute to Walter Lewin at the end
yes! LOL
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.
real
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!).
This is great!
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.
Math is very easy when you are explaining.....realy i enjoy.....
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!
Brilliant sir. Absolutely brilliant. My eyes lit up when I saw the golden ratio manifest itself.
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.
I love the sound of chalk clicking on the board XD
Ha, my teacher uses nails
@@benhayter-dalgliesh5794 🤣🤣😂
your feelings are irrational
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 ...
What you teach is awesome and easy to understand
Sir your channel is awesome! You make tough proofs look like a child's play. I love your videos.
I don't get the bit at 6:33. How does this have anything to do with second order linear differential equations?
I habe been searching for this for such a long time
I remember proving this by induction, but this is a good way to derive as well as prove it. Nice video!
Yea, Thanks
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)
i do not know why but i love your face when you slide that board up HAHAHAHA. I'm also amazed by that.
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
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)
You are wonderful. Why didn't you start earlyer making this video. That's exactly what I was looking for.
I have been making videos for a few years now and just recently began higher level topics just for fun.
What it the reason behind pluging r^n into Fn ? Is it simply because it "looks" like a differential equation ?
th-cam.com/video/3vbHTi6sID0/w-d-xo.html
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.
I put this into a spreadsheet. It works a treat.
Nice! Does this also work for non-integer values of n?
Yes i think
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.")));
and im very sorry for spamming a javascript program and things about it
If this video was 9 seconds shorter, it would have two consecutive Fibonacci numbers as the time. (13:21)
How did u know that the general term was a difference of two geometric progression?
It could have been any function?
my question too. I guess we just assume it can?
It's a case of: you conjecture that a solution has a certain form and then it works.
leoitshere how can you prove it's a unique solution?
+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.
But how do you know Fn=r^n ???
Pls explain!!!!!
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.
That is so cool! only wondering where come from the first assumption that Fn=r^n? Can you please let me know! thank you~
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) |
We did that in a discrete math class, it was one of the easiest part of the class !
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?
Yup
Wow, amazing, never seen before one of those difference equations, very clever. More like this pls!
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!
I would love to see more videos on Difference Equations!
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.
great video! this really helped me on my project.
Absolutely loved it
Been struggling
Thabk you for your kind help
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,
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!
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.
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?
Definitely interested in more general sequences and difference equations, explaining the motivation for the method of solution
Sir,
can we find the number of term 'n' , if Fibonacci term Fn is given ?
Can we have formula like this formula for it?
I really enjoyed the math in this video and would like if you made more like it, but that ending.
PHI raised to the Nth power gives you the nth term when rounded to the nearest integer.
Who is here because computer science 😁
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?
Your amazing dude, i wish i knew you earlier... Great video.
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.
i just want to say that the fibonnachi sequence has a negative range too which is (starting from n=0) {0, 1, -1, 2, -3, 5, -8, 13, -21, ...}
That end tho...
yup!
@@blackpenredpen what a goat
Thank you so much for this video !
Why do you choose r^n as general solution?
Is there any method or formula to check whether a number is prime or not???
It's so obvious but still so amazing that phi finds its way into something like this
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--
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.
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.
This video is pure gold
11:10 you could have just plugged the a value and find b from single equation.
Will this work if we have different starting values (other than 1, 1) and calculate a and b accordingly?
It should
excelente!!!, saludos desde Bolivia!
a ver:
Como llegamos de:
1 = r^(-1) + r^(-2)
a:
r^2 = r + 1
???
porfa
ok, ya lo solucione!!!
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?
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?
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
Another good way to find an equation for the nth term is with linear algebra
Nice video, but like others have said, you've skipped over some crucial intuition. In any case, I prefer the derivation involving generating functions
wait... where did you get the equation at 3:04 ??
Please do more difference equations
Fibonacci series starts with 0,1. Subsequent terms are the sum of the immediately preceding 2 terms.
how did you know the result was of the form a(r1)^n+b(r2)^n?
Why did you write F_n = ar_1^n + br_2^n at 6:28 ?
Look up linearality. Based on the condition of the difference equation we are looking for two linearly independent solutions, namely r_1 and r_2 that satisfy F_n=a*r_1^n+b*r_2^n.
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.
F0 = 0.
Fibonacchi started his sequence with F1 = 1 and F2 = 1.
You are my best.
Like l give
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.
Etothe2iPi working out all the algebra steps isn't waste of time
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..)
Joseph Gross I need to plan a lecture on that from scratch so it takes time.
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.
Started learning this this year in Discrete Structures
How would you do ....r^n=r^(n-1)*n form . ?????
Can n be negative or imaginary ? What happens then?
What happens if you try to use a difference table to determine Fibonacci numbers?
Thank you in advance for the answer! 😁
How about trying to find 2^n power is this possible?
Is this what they call second order recurrence relation? I need an answer really quick
2:45 cute authentic smile . i hit like button
never herd of difference eqn. looked it up - confirmed it exists
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.
can you go into more detail with the difference equations
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.
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).
Yea, I just realized that too from another subscriber
Can this be done the way {n(n+1)}/2 was done?
By taking the an³ + bn² + cn +d
Wouldn't work because the final answer isn't a polynomial. The growth is exponential.