Comments on: Yoak: Miles, Kilometers and Fibonacci Numbers

By: Mike Jarvis

Mike Jarvis — Tue, 29 Dec 2009 15:53:18 +0000

Proof that all numbers are representable in base Fibonacci comes from the fact that F_n <= sum(F_k,k=1..n-1).
So for example 10000 <= 1111 in baseF.
Then we proceed by induction:
Define F(n) = n’th Fibonacci number, which is 1 with n-1 0’s in baseF. (F(1) = 1, F(2) = 10, F(3) = 100, etc.)
Define G(n) = the number that is all 1’s in baseF with n 1’s. (G(1) = 1, G(2) = 11, G(3) = 111, etc.)
A) All numbers from 1 to G(1) are representable in baseF is trivially true, since G(1) = 1.
B) If all numbers from 1 to G(n) are representable in baseF, then all numbers from 1 to G(n+1) are representable.
Proof: G(n+1) = F(n+1) + G(n), so all numbers from F(n+1)+1 to F(n+1)+G(n) (=G(n+1)) are representable from the premise. And F(n+1) itself is certainly representable. So we just need to prove that the two ranges 1 — G(n) and F(n+1) — G(n+1) are overlapping ranges. i.e. that F(n+1) <= G(n) for all n>=1. (This was my statement at the start of the post.)
F(2) = G(1) = 1 (base 10)
F(3) = G(2) = 2 (base 10)
For n > 2, F(n+1) = F(n) + F(n-1) < G(n)
QED.

By: jyoak

jyoak — Wed, 16 Dec 2009 14:39:07 +0000

With the "Base Fibonacci" question, it is phrased like an easier version and a harder version of the question. I can't demonstrate the base or "easy" proposition that you can represent all numbers that way. It seems that it must be true, but I can't show it. Oddly, I can show that if it is true that you can do that, you can do it without using consecutive digits.

Assume a representation of 1's and 0's representing "places" low to high from right to left. So numbers are represented by ...8-5-3-2-1 and you could represent 16 as 11100 .

The question then is equivalent to whether we can translate this into a numerically equivalent number with no instances of the string '11'. Because of how Fibonacci numbers work, any string of '011' can be translated to '100' without changing the value of the number. Do this repetitively until there are no more instances. (This is sure to work as you can pad with zeros on the left as needed.)

So 11100 -> 011100 -> 100100

So instead of having 8+5+3 = 16 we have 13+3=16

11111 = 19

11111 -> 011111 -> 100111 -> 101001

101001 = 13+5+1 = 19

By: jyoak

jyoak — Wed, 09 Dec 2009 05:03:11 +0000

As Blaine cleverly indicated above in the comments above, the set of numbers in the post are the complete set of integers that, when expressed in hexidecimal format, are the reverse of their representation in decimal.

Must think some more about "base Fibonacci". :-)

By: strauss

strauss — Fri, 04 Dec 2009 07:56:23 +0000

I really use this trick on a regular basis! This raises another issue: writing numbers "Base Fibonacci". Can you show that every number can actually be written as the sum of Fibonacci numbers. Furthermore, that every number can be written uniquely as the sum of fibs so that no two are consecutive (i.e. not 8 & 5, for example)

By: jyoak

jyoak — Thu, 03 Dec 2009 22:41:02 +0000

Blaine, :-)

By: Blaine

Blaine — Thu, 03 Dec 2009 06:38:58 +0000

[spoiler]lamicedaxeh (-:[/spoiler]