Integers as Sums of Fibonacci Numbers

We show that every positive integer can be expressed as the sum of distinct Fibonacci numbers. This leads to a fun shortcut for converting between miles and km.

00:00 Starting examples
01:35 Idea of the proof
03:06 Strong induction
06:50 Application
09:20 Payoff

[peterbarber]

This is a wonderful opportunity to be even more annoying than I am usually on car journeys with my attempts at edifying conversations

[mrphlip]

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.

[RamblingMaths]

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) <= 2a(n), we can write every positive integer as a sum of distinct elements of the sequence.

[wesleydeng]

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.

[ikarienator]

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.

[f-th]

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.

[chiprollinson]

And to estimated the conversion of km to mi, you just add the previous Fibonacci numbers. Nice.

[gavintillman]

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.

[DanGRV]

Any sequence with the conditions

a_1 = 1
1 < a_(n+1) / a_n <= 2

defines a subset of the naturals which has that same sum property of the video

[MrDannyDetail]

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.

[maklovitz]

Aproximating mile/km = Golden ratio is the least mathematical thing I saw in this channel

[alipourzand]

So all you need to convert miles to km is addition. No multiplication or division!

[juandesalgado]

Not much of a fan of applied mathematics... :) but this was a beautiful video, once more. Thanks!

[Joffrerap]

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.

[Drayiss]

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

[macalmy]

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.

[pepebriguglio]

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?

[damirdukic]

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.

[lucaswilkins]

That's a very complicated way of inaccurately multiplying by 1.609344

[Sasseater]

I'd have no problem if these numbers wanted to date my mom