A corollary here (not hard to incorporate into your inductive proof) is that you not only have all the terms in the sum as distinct Fibonacci numbers, but you don't even have _neighbouring_ Fibonacci numbers in the sum. I've also seen this presented as a base-Fibonacci number system... If you have a positional number system where each digit is worth F_n, then you can write any natural number with just the digits 0 and 1, without having two 1s next to each other.
Alternative proof. Given n, if n is a Fibonacci number then we are done. Otherwise find the largest Fibonacci number f that is < n. Because n - f < f for n>2, you can repeat this process until it ends with no duplicates.
I still feel like your idea is best expressed inductively -- the idea of "repeat this process" can be succinctly expressed with strong induction. Note 1 and 2 are Fibonacci. Now let n > 2. If n is Fibonacci, then we're done; otherwise, find the largest Fibonacci number f < n, and we have n - f < f. By the induction hypothesis, n - f can be written as a Fibonnaci sum, so f + (n - f) = n can, as well.
This proof doesn't only apply to the Fibonacci numbers, I think it shows that, given any sequence of positive integers a(n) which is strictly increasing, i.e. a(n+1) > a(n), and whose growth is no faster than doubling, i.e. a(n+1)
This seems to be right, as long as you include that the sequence must begin with 1. Of course without 1 in the sequence you won't be able to sum to 1, and also you can get sequences that only sum to even numbers, etc
Fairly sure the representation is unique if you require that no two Fibonacci numbers in the sum are consecutive. Take the biggest F number less than or equal to your n, knock off n and rinse and repeat. Like the km miles conversion though it’s not a given that F_n / F_{n-1} is a progressively better conversion factor as n-> inf. it may be that 8/5 (or some other ratio of consecutive F numbers) is better than phi.
Nice, your explanations are always easy to follow. I think you're really good at preparing a presentation. It's increasing in difficulty, it's detailed but clear, and it all comes up together eventually. Are you a teacher? I feel like you could be a great teacher, because those competence are a big part of what makes great teachers.
I think the 1 going to 2 in the last part is such a poor approximation of that ratio because it doesn't account for the whole story. Because of how Fibonacci numbers begin 1 goes to both 1 and 2, so on average it goes to 1.5, a much better approximation.
7:19 -- Not true! The best approximation of these is the "5 --> 8" one. All those which go further down the line are worse, the worst of them _(relatively)_ being "8 --> 13". Those from "55 --> 89" onward are not even good _integer_ approximations, e.g. 55 miles is closer to 88 chilometers than 89.
Binary Fibonacci coding is a very interesting thing. Not only is it a universal code (you can cram a load of digits from numbers with different lengths together, and still recover the original numbers), but it is also a self-synchronising code (if you corrupt some of the digits, you might get some junk, but you eventually can get back to the correct sequence) ... en.wikipedia.org/wiki/Fibonacci_coding
You can use the Fibonacci numbers to encode PCM audio. You compute the delta between two samples, take the fibonacci number that is closest and emit its ordinal together with a sign bit. The error then gets propagated to the next sample. On the receiving end you just add or subtract the encoded Fibonacci numbers. This will converge if your audio is lowpass enough, which is true of speech.
Hey this is random, but I remember recent finding out something with the Fibonacci numbers: The (n+1)th Fibonacci number = sum from k=0 to n/2 of (n-k) choose k I haven’t looked into this myself yet, but I’m curious if there’s a good proof for this
You can show that sum is equal to the Fibonacci numbers if the first 2 terms are consecutive Fibonacci numbers and they satisfy that the next term is the sum of the previous two
The formula which gives Fn rather than F(n+1), and effectively sums the "shallow diagonals" of Pascal's triangle, is Fn = Σ (from k = 0 to floor((n-1)/2)) of nCk(n - k - 1 choose k). You can prove it by expanding the generating function x / (1 - x - x^2) = x + x^2(x + 1) + x^3(x + 1)^2 + ... + x^(k+1)^k + ... = Σ (from n = 0 to ∞) of Fn*x^n , then grouping like terms of x^n. For illustrative purposes: 5 = 1+1+1+1+1 = 2+1+1+1 = 1+2+1+1 = 1+1+2+1 = 1+1+1+2 = 2+2+1 = 2+1+2 = 1+2+2 which is ( 5 choose 0 ) + ( 4 choose 1 ) + ( 3 choose 2 ), where we are choosing the positions of k twos from n−k−1 terms.
@@stickfiftyfive Yo thanks! Actually the way you described the example with 5, I got it from a recent numberphile video about the frog jumping on lilypads, which was really cool to see how the numbers both worked the same!
Does the number of distinct Fibonacci numbers needed to add to the most 'needy' numbers get arbitrarily big when those numbers get arbitrarily large, or does some definite lower bound exist?
A corollary here (not hard to incorporate into your inductive proof) is that you not only have all the terms in the sum as distinct Fibonacci numbers, but you don't even have _neighbouring_ Fibonacci numbers in the sum.
I've also seen this presented as a base-Fibonacci number system... If you have a positional number system where each digit is worth F_n, then you can write any natural number with just the digits 0 and 1, without having two 1s next to each other.
Alternative proof. Given n, if n is a Fibonacci number then we are done. Otherwise find the largest Fibonacci number f that is < n. Because n - f < f for n>2, you can repeat this process until it ends with no duplicates.
I still feel like your idea is best expressed inductively -- the idea of "repeat this process" can be succinctly expressed with strong induction. Note 1 and 2 are Fibonacci. Now let n > 2. If n is Fibonacci, then we're done; otherwise, find the largest Fibonacci number f < n, and we have n - f < f. By the induction hypothesis, n - f can be written as a Fibonnaci sum, so f + (n - f) = n can, as well.
@@NateROCKS112 Isn't that effectively the same as Dr Barker's proof? He just goes through it in more detail.
@@RGP_Maths yeah, pretty much.
This is a wonderful opportunity to be even more annoying than I am usually on car journeys with my attempts at edifying conversations
This proof doesn't only apply to the Fibonacci numbers, I think it shows that, given any sequence of positive integers a(n) which is strictly increasing, i.e. a(n+1) > a(n), and whose growth is no faster than doubling, i.e. a(n+1)
This seems to be right, as long as you include that the sequence must begin with 1. Of course without 1 in the sequence you won't be able to sum to 1, and also you can get sequences that only sum to even numbers, etc
Fairly sure the representation is unique if you require that no two Fibonacci numbers in the sum are consecutive. Take the biggest F number less than or equal to your n, knock off n and rinse and repeat.
Like the km miles conversion though it’s not a given that F_n / F_{n-1} is a progressively better conversion factor as n-> inf. it may be that 8/5 (or some other ratio of consecutive F numbers) is better than phi.
21 / 13 is the best :)
You just rediscovered Zeckendorf's theorem!
en.m.wikipedia.org/wiki/Zeckendorf%27s_theorem
So all you need to convert miles to km is addition. No multiplication or division!
Nice, your explanations are always easy to follow. I think you're really good at preparing a presentation. It's increasing in difficulty, it's detailed but clear, and it all comes up together eventually. Are you a teacher? I feel like you could be a great teacher, because those competence are a big part of what makes great teachers.
I think the 1 going to 2 in the last part is such a poor approximation of that ratio because it doesn't account for the whole story. Because of how Fibonacci numbers begin 1 goes to both 1 and 2, so on average it goes to 1.5, a much better approximation.
Any sequence with the conditions
a_1 = 1
1 < a_(n+1) / a_n
7:19 -- Not true! The best approximation of these is the "5 --> 8" one. All those which go further down the line are worse, the worst of them _(relatively)_ being "8 --> 13". Those from "55 --> 89" onward are not even good _integer_ approximations, e.g. 55 miles is closer to 88 chilometers than 89.
Yes. And also:
phi = 1.618033988...
miles / kilometers = 1.609344
Binary Fibonacci coding is a very interesting thing. Not only is it a universal code (you can cram a load of digits from numbers with different lengths together, and still recover the original numbers), but it is also a self-synchronising code (if you corrupt some of the digits, you might get some junk, but you eventually can get back to the correct sequence) ... en.wikipedia.org/wiki/Fibonacci_coding
You can use the Fibonacci numbers to encode PCM audio. You compute the delta between two samples, take the fibonacci number that is closest and emit its ordinal together with a sign bit. The error then gets propagated to the next sample. On the receiving end you just add or subtract the encoded Fibonacci numbers. This will converge if your audio is lowpass enough, which is true of speech.
Aproximating mile/km = Golden ratio is the least mathematical thing I saw in this channel
Hey this is random, but I remember recent finding out something with the Fibonacci numbers:
The (n+1)th Fibonacci number =
sum from k=0 to n/2 of (n-k) choose k
I haven’t looked into this myself yet, but I’m curious if there’s a good proof for this
You can show that sum is equal to the Fibonacci numbers if the first 2 terms are consecutive Fibonacci numbers and they satisfy that the next term is the sum of the previous two
The formula which gives Fn rather than F(n+1), and effectively sums the "shallow diagonals" of Pascal's triangle, is
Fn = Σ (from k = 0 to floor((n-1)/2)) of nCk(n - k - 1 choose k).
You can prove it by expanding the generating function
x / (1 - x - x^2)
= x + x^2(x + 1) + x^3(x + 1)^2 + ... + x^(k+1)^k + ...
= Σ (from n = 0 to ∞) of Fn*x^n
, then grouping like terms of x^n.
For illustrative purposes:
5 = 1+1+1+1+1
= 2+1+1+1 = 1+2+1+1 = 1+1+2+1 = 1+1+1+2
= 2+2+1 = 2+1+2 = 1+2+2
which is ( 5 choose 0 ) + ( 4 choose 1 ) + ( 3 choose 2 ), where we are choosing the positions of k twos from n−k−1 terms.
@@stickfiftyfive Yo thanks! Actually the way you described the example with 5, I got it from a recent numberphile video about the frog jumping on lilypads, which was really cool to see how the numbers both worked the same!
Not much of a fan of applied mathematics... :) but this was a beautiful video, once more. Thanks!
Does the number of distinct Fibonacci numbers needed to add to the most 'needy' numbers get arbitrarily big when those numbers get arbitrarily large, or does some definite lower bound exist?
That's a very complicated way of inaccurately multiplying by 1.609344
Could it be useful in CS also?
I wrote up a script to solve this problem just then, cant see if it's useful, but it's a good exercise!
Someone else in the comments mentioned Binary Fibonacci coding for error correction.
Ah yes my favouritr number system.
I'd have no problem if these numbers wanted to date my mom
You'd be known as "the son of Fibonacci". Sounds impressive.
Hi my name is 34