Math puzzle: fibonacci sequence in bits

If you write the Fibonacci sequence using binary representation for each number, a picture like this emerges:

Every column of small rectangles is a Fib(N) value, written vertically in binary, with lowest bit at the bottom. Looking at the picture, it is quite clear that the dependency between N and the number of bits to represent Fib(N) is linear. I’m curious though, how to mathematically prove that… (I’m sure @LoopSpace can do that in like 5 seconds, but still… :slight_smile: )

Code is here, if anyone needs it:

--# Main
-- Fibobits


-- Use this function to perform your initial setup
function setup()
    A,B = 0,WIDTH/5
    bitSize = 5
    i = 0

    nums = {{ 1 }, { 1 }}
    for i=3,B do
        nums[i] = add(nums[i-2], nums[i-1])
    print("prepped: " .. B)

function add(a, b)
    local c = {}
    local n = math.max(#a,#b)
    local carry = 0
    for i=1,n do
        c[i] = (a[i] or 0) + (b[i] or 0) + carry
        if c[i] > 1 then
            carry = 1
            c[i] = c[i] - 2
            carry = 0 
    if carry > 0 then
        c[n+1] = 1
    return c

-- This function gets called once every frame
function draw()
    -- This sets a dark background color 
    background(40, 40, 50)

    -- This sets the line thickness

    -- Do your drawing here
    if fibImg then
        translate(WIDTH/2, HEIGHT/2)
        text("Preparing image ...", WIDTH/2, HEIGHT/2)
        stroke(85, 83, 140, 255)
        rect(WIDTH/2 - 150, HEIGHT/2 - 50, 300, 20)
        fill(95, 92, 111, 255)
        rect(WIDTH/2 - 150, HEIGHT/2 - 50, 300*i/(B-A), 20)

        co = co or coroutine.create(function()
            local img = image(WIDTH, HEIGHT)
            local count = 0
            local s = bitSize
            i = 1
            while i<=B-A do
                local b = nums[i+A]
                for j=1,#b do
                    count = count + 1 
                    if b[j] == 1 then
                    if count % 1000 == 0 then
                i = i + 1 
            fibImg = img

@Juce Very interesting.

@Juce I looked up Fibonacci linear and it took me to this site. This might explain it being linear.

@dave1707, thanks for the link - very good article. They even have the same picture! They don’t mention the linear nature of the graph, perhaps it is obvious from other formulas and facts… I shall read it carefully

( My thinking so far was like this: to represent a number X, you need Log2(X) bits. In our case X = Fib(N), so for the dependency to be linear, Fib(N) needs to be something 2^(k * N), where k is some constant. Then we have Log2(2^(k * N)) = k * N. But Fib(N) is not 2^(k * N)… So i’m confused :slight_smile: … )

@Juce I haven’t read the article yet, but it looks interesting. What kind of picture do you get if you used prime numbers.

@Juce I tried running your code with a bitSize=.5 and B=WIDTH*2 . Still nice and linear.

Fib(N) is 2^(k N), or as near as makes no difference.

More accurately, the numbers in any Fibonacci-like sequence are of the form a phi^n + b phi^{-n} where a and b are constants and phi is the golden ratio. (By “Fibonacci-like” I mean a sequence generated using the same rule as “the” Fibonacci sequence but with possibly different starting points.)

The first crucial point is that phi^{-n} quickly becomes very small. So Fib(n) is approximately a phi^n. In fact, a quick way to calculate Fib(n) is to take the nearest integer to a phi^n.

Thus log_2 Fib(n) is approximately log_2 (a phi^n) which is log_2 a + n log_2 phi.

This is linear. It’s slightly offset by log_2 a, but for the actual Fibonacci sequence then a is 1/sqrt(5) so log_2 of that is around -1. Also, log_2 phi is a bit over 1/2. So the equation is roughly -1 + n/2. The -1 offset is so small you probably don’t notice it.

nice ! And how do explain those recurring structures?

@Jmv38, those are cool, indeed! Many of those triangles there…

@LoopSpace, thanks for the explanation. Makes sense. I’m curious how the formula for Fib(n) with powers of phi is derived - i’ll read up on that.

Fibonacci-like sequences are generated by F_{n+2} = F_{n+1} + F_n. We assume that there is a formula of the for F_n = r^n for some r.

Substituting in, we get r^{n+2} = r^{n+1} + r^n. There’s a common factor of r^n in that, and dividing through we get r^2 = r + 1. There are two numbers that satisfy that: phi and 1/phi (where phi is the golden ratio).

So every Fibonacci sequence is of the form: a phi^n + b phi^{-n}. Then you just need to choose a and b so that the first two terms are the first two terms of your sequence.

The standard Fibonacci sequence starts 1,1, and traditionally we start counting at 0, so we choose a and b so that:

a + b = 1

a phi^1 + b phi^{-1} = 1

This leads to the coefficients as stated, since phi = (1 + sqrt(5))/2

this demonstration does not prove that

So every Fibonacci sequence is of the form: a phi^n + b phi^{-n}.

it proves only that there are sequences of this form. Some more is needed to prove every sequence is of this form.

Pick a Fibonacci sequence. Every Fibonacci sequence is completely determined by its first two values. There’s an a and b so that a phi^n + b phi^{-n} starts with those same two values (that’s not hard to show). Since a phi^n + b phi^{-n} is a Fibonacci sequence with the same first two values as our original sequence, it must therefore be the one we’re thinking of.

that’s the proof i was missing. Thanks.