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.
I thought of this 'base Fibonacci' system myself a few years ago. Then I realized that the perfect name for it was 'fibinary notation'. Then I thought it was *such* a perfect name, I bet someone else has already thought of it. So I did a web search on 'fibinary', and indeed I found stuff. It is a fun exercise to find an algorithm for adding fibinary numbers. If there is a sensible algorithm for multiplying fibinary numbers, I don't know what it is.
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
@@waffling0 Oh yes, good point! The exactly doubling case (1, 2, 4, 8, ...) gives binary place notation, and cases with less-than-doubling are like a variant on binary where we still only allow 0s and 1s, but have squeezed in some extra columns. Similarly, allowing a number to appear at most 2 times gives a variant of ternary place notation, etc.
@@rujon288 I think so, but note also that a series of less-than-doubling gaps allows a more-than-doubling gap afterwards, e.g. a sequence starting 1,2,3,5,12,.... So in general being able to represent every positive integer is more permissive than simply "no more than doubling".
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.
Suppose it' true for all integers from 0 to F_{n} - 1. There are F_{n} of these integers, and none of their sums use F_{n} (because it's bigger than all of them). We want to show it's true for the integers from F_{n} to F_{n+1}-1. There are (F_{n+1}-1) - (F_{n}) + 1 = F_{n+1} - F_{n} = F_{n-1}. So here's the punchline: If we take the numbers from 0 to F_{n} - 1 and add F_{n} to their representations (which we said they didn't contain, so we still have distinct Fibs), we get the numbers from F_{n} to 2*F_{n} - 1, which covers the range we want to prove the statement for (which is from F_{n} to F_{n+1}-1) because there are more new numbers (F_{n} of them) than the ones we wanted to prove for (F_{n-1} of them), and both ranges start from the same spot (at F_{n}). It's easier to explain visually with a number line.
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.
@@Simpson17866Yes indeed! φ≈1.618 and 1 mile=1.609344 km, slightly smaller than φ. So you only need to consider the increasing subsequence 1/1, 3/2, 8/5, 21/13, which converges to φ from below (whereas the other, decreasing, subsequence 2/1, 5/3, 13/8, 34/21 etc converges to φ from above). 8/5=1.6, a bit too small; 21/13≈1.615, larger but a bit closer. All subsequent ratios will be larger still. So 21/13 is indeed closest.
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
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.
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!
@Drayiss No problem.. I get a little excited anytime a video comes out which relates the binomial coefficients to anything, but especially recurrence relations. I've known that the Fibonacci numbers are in the diagonals for quite some time, but exploring the intricacies of the identities and relations surrounding is quite fun.
You can also do a proof by contradiction. Assume n is the smallest number that can't be written as a sum of distinct Fibonacci numbers. Let Fk be a Fibonacci number less than n. (n - Fk) must be writable as a sum of distinct Fibonacci numbers (since it is less than n). This implies that all possible sums that make up (n - Fk) must include Fk. Now consider Fm, the largest Fibonacci number less than n. From the fact that the ratio of successive Fibonacci numbers approaches phi, it follows that Fm is greater than half Fm+1. But Fm+1 > n, so Fm > n/2, which in turn implies that (n - Fm) < Fm. But we've shown that the sum for n - Fm must include Fm, which implies (n - Fm) > Fm. Which is impossible.
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?
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.
![Lp. Сердце Вселенной #60 РОЖДЕНИЕ ЛОЛОЛОШКИ [Финал] • Майнкрафт](http://i.ytimg.com/vi/YoR0pAV9FVQ/mqdefault.jpg)
This is a wonderful opportunity to be even more annoying than I am usually on car journeys with my attempts at edifying conversations
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.
I thought of this 'base Fibonacci' system myself a few years ago. Then I realized that the perfect name for it was 'fibinary notation'. Then I thought it was *such* a perfect name, I bet someone else has already thought of it. So I did a web search on 'fibinary', and indeed I found stuff.
It is a fun exercise to find an algorithm for adding fibinary numbers. If there is a sensible algorithm for multiplying fibinary numbers, I don't know what it is.
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
@@waffling0 Oh yes, good point!
The exactly doubling case (1, 2, 4, 8, ...) gives binary place notation, and cases with less-than-doubling are like a variant on binary where we still only allow 0s and 1s, but have squeezed in some extra columns. Similarly, allowing a number to appear at most 2 times gives a variant of ternary place notation, etc.
@@RamblingMathsvery true. I wonder if this means 2 is the minimum rate of growth for integers to become inaccessible
@@rujon288 I think so, but note also that a series of less-than-doubling gaps allows a more-than-doubling gap afterwards, e.g. a sequence starting 1,2,3,5,12,.... So in general being able to represent every positive integer is more permissive than simply "no more than doubling".
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.
Suppose it' true for all integers from 0 to F_{n} - 1. There are F_{n} of these integers, and none of their sums use F_{n} (because it's bigger than all of them).
We want to show it's true for the integers from F_{n} to F_{n+1}-1. There are (F_{n+1}-1) - (F_{n}) + 1 = F_{n+1} - F_{n} = F_{n-1}.
So here's the punchline: If we take the numbers from 0 to F_{n} - 1 and add F_{n} to their representations (which we said they didn't contain, so we still have distinct Fibs), we get the numbers from F_{n} to 2*F_{n} - 1, which covers the range we want to prove the statement for (which is from F_{n} to F_{n+1}-1) because there are more new numbers (F_{n} of them) than the ones we wanted to prove for (F_{n-1} of them), and both ranges start from the same spot (at F_{n}).
It's easier to explain visually with a number line.
This is called the Fibonacci coding. It can be used to uniquely represent any natural number using 0s and 1s but no two 1s are adjacent.
And to estimated the conversion of km to mi, you just add the previous Fibonacci numbers. Nice.
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
@@Simpson17866Yes indeed!
φ≈1.618 and 1 mile=1.609344 km, slightly smaller than φ.
So you only need to consider the increasing subsequence 1/1, 3/2, 8/5, 21/13, which converges to φ from below (whereas the other, decreasing, subsequence 2/1, 5/3, 13/8, 34/21 etc converges to φ from above). 8/5=1.6, a bit too small; 21/13≈1.615, larger but a bit closer. All subsequent ratios will be larger still. So 21/13 is indeed closest.
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
Aproximating mile/km = Golden ratio is the least mathematical thing I saw in this channel
Any sequence with the conditions
a_1 = 1
1 < a_(n+1) / a_n
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.
Thank you! Yes I am, it's something I enjoy a lot.
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.
So all you need to convert miles to km is addition. No multiplication or division!
Not much of a fan of applied mathematics... :) but this was a beautiful video, once more. Thanks!
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!
@Drayiss No problem.. I get a little excited anytime a video comes out which relates the binomial coefficients to anything, but especially recurrence relations.
I've known that the Fibonacci numbers are in the diagonals for quite some time, but exploring the intricacies of the identities and relations surrounding is quite fun.
You can also do a proof by contradiction. Assume n is the smallest number that can't be written as a sum of distinct Fibonacci numbers. Let Fk be a Fibonacci number less than n. (n - Fk) must be writable as a sum of distinct Fibonacci numbers (since it is less than n). This implies that all possible sums that make up (n - Fk) must include Fk.
Now consider Fm, the largest Fibonacci number less than n. From the fact that the ratio of successive Fibonacci numbers approaches phi, it follows that Fm is greater than half Fm+1. But Fm+1 > n, so Fm > n/2, which in turn implies that (n - Fm) < Fm. But we've shown that the sum for n - Fm must include Fm, which implies (n - Fm) > Fm. Which is impossible.
Very neat, I like it!
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?
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
Close enough for an approximation@@DanGRV
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.
That's a very complicated way of inaccurately multiplying by 1.609344
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