symbolic_fib.jl

#a = Expr(symbol("F_{n + 1}"))
#b = Expr(symbol("F_n"))
#c = Expr(symbol("F_{n - 1}"))

a = Expr(:a)
b = Expr(:b)
c = Expr(:c)

# fibonacci matrix
F = [ a b ;
      b c ];

function *(a ::Expr, b::Expr)
    return Expr(:call, :*, a, b)
end

function +(a ::Expr, b::Expr)
    return Expr(:call, :+, a, b)
end

function min_simpl(ex::Expr)
    if length(ex.args) == 3
        if (ex.args[1] == :*) && (ex.args[2] == ex.args[3])
            return Expr(:call, :^, ex.args[2], 2)
        end
    end

    return ex
end

function min_simpl(x::Number)
    return x
end

function prettyprint(ex::Expr)
    if ex.head == :call
        print("(")
        prettyprint(min_simpl(ex.args[2]))
        print(ex.args[1])
        prettyprint(min_simpl(ex.args[3]))
        print(")")
    else
        print(ex.head)
    end
end

function prettyprint(x::Number)
    print(x)
end

# TODO: implement distributive property etc so expanding by hand is not
# required

F4 = F * F * F * F

# Conjecture: F_n | F_kn for integer k,n > 0.

# This is an expression for any fibonacci number of the form F_{4n}, in terms
# of F_{n - 1}, F_n and F_{n + 1}. We demonstrate this conjecture is true when
# k = 4; this can be seem by expanding the expression below.

# This brute force method is unlikely to generalize. Further insights are
# required. Idea: Diagonalize; D = QFQ' => Q'DQ = F and F^nk = Q'D^{nk}Q.
# Perhaps this is easier to generalize as D^nk is much simpler than F^nk. Now,
# the complexity shifts to Q := matrix of eigenvectors of F^n...

ex = F4[3]
prettyprint(ex)

The conjecture can be proven for all k by considering the Fibonacci matrix mod F_n, i.e., as a matrix whose entries are elements of the ring Z/F_nZ. Then, the Fibonacci matrix F reduces to a diagonal matrix and it follows trivially that F_n | F_nk.