Skip to content

Instantly share code, notes, and snippets.

@siddMahen
Created March 8, 2015 00:02
Show Gist options
  • Save siddMahen/f9a47bc703b76f526512 to your computer and use it in GitHub Desktop.
Save siddMahen/f9a47bc703b76f526512 to your computer and use it in GitHub Desktop.
#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)
@siddMahen
Copy link
Author

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment