# Fibonacci numbers

Fibonacci numbers are numbers in the Fibonacci sequence $f_n$. We define the Fibonacci sequence recursively as $f_1=f_2=1$ and $f_n=f_{n-1}+f_{n-2}$.

In Maxima we can compute the n-th Fibonacci number with the fib function. The beginning of the sequence is

(%i1) makelist(fib(i), i, 1, 10);
(%o1) [1,1,2,3,5,8,13,21,34,55]

We can compute the well-known explicit formula for $f_n$

(%i2) load(solve_rec)$(%i3) solve_rec(f[n]=f[n-1]+f[n-2], f[n], f[1]=1, f[2]=2); (%o3) f[n]=((sqrt(5)+1)^n*(sqrt(5)+5)*2^(-n-1))/5- ((sqrt(5)-5)*(sqrt(5)-1)^n*2^(-n-1)*(-1)^n)/5 or nicer ${f}_{n}=\frac{{\left( \sqrt{5}+1\right) }^{n}\,\left( \sqrt{5}+5\right) \,{2}^{-n-1}}{5}-\frac{\left( \sqrt{5}-5\right) \,{\left( \sqrt{5}-1\right) }^{n}\,{2}^{-n-1}\,{\left( -1\right) }^{n}}{5}$ In this post I want to show how to use the explicit formula to investigate some interesting properties of the Fibonacci numbers. Usually we prove identities with Fibonacci numbers using induction, but here I also show how to find them. ### Proving identities First we need to express $f_n$ using the golden ratio $\phi=\frac{\sqrt{5}+1}{2}$. We will use the fibtophi function. (%i4) fib(n)$
(%i5) fibtophi(%);
(%o5) (%phi^n-(1-%phi)^n)/(2*%phi-1)

which gives ${f}_{n}=\frac{{\phi}^{n}-{\left( 1-\phi\right) }^{n}}{2\,\phi-1}$. Maxima uses the identity $\phi^2=\phi+1$ to simplify expressions which contain $\phi$.

A simple example is to “prove” the definition of Fibonacci numbers.

(%i6) fib(n) - fib(n-1) - fib(n-2);
(%o6) fib(n)-fib(n-1)-fib(n-2)
(%i7) ratsimp(fibtophi(%));
(%o7) 0

A little more interesting is the identity $\displaystyle \sum_{k=1}^n k f_k= n f_{n+2} - f_{n+3} + 2$. I will use the latest simplify_sum package from cvs.

(%i8) load(simplify_sum)$(%i9) sum(k*fib(k), k, 1, n) - n*fib(n+2) + fib(n+3) - 2$
(%i10) fibtophi(simplify_sum(%))$(%i11) ratsimp(%); (%o11) 0 The last example is from Wikipedia. It is the “divisibility by 11” property: $\displaystyle \sum_{k=0}^9 f_{n+k} = 11 f_{n+6}$ (%i12) sum(fib(n+k), k, 0, 9)/fib(n+6)$
(%i13) fibtophi(%)$(%i14) ratsimp(%); (%o14) 11 ### Finding identities ##### Division identities We can find more identities like the divisibility property given above. (%i15) fib_ratio(a,b) := ratsimp( fibtophi(sum(fib(n+i), i, 0, a)/fib(n+b)))$
(%i16) sublist(
create_list([a,b,fib_ratio(a,b)], a, 1, 20, b, 1, a),
lambda([l], is(integerp(last(l)))));
(%o16) [[2,2,2],[5,4,4],[9,6,11],[13,8,29],[17,10,76]]

The last triple gives the identity

$\displaystyle \sum_{k=0}^{17}f_{n+k} = 76 f_{n+10}$.

As a comparison, here is some similar code in Mathematica

In[1]:= fibRatio[a_, b_] := FullSimplify[
Sum[Fibonacci[n + i], {i, 0, a}]/Fibonacci[n + b]]

In[2]:= Select[
Flatten[Table[{a, b, fibRatio[a, b]}, {a, 1, 10}, {b, 1, a}], 1],
IntegerQ[#[[3]]] &
]

Out[2]= {{2, 2, 2}, {9, 6, 11}}

Note that the Mathematica code (in Mathematica 7.0.0) runs much longer than the Maxima code, even though I searched in a smaller sample of ratios. It also misses the case [5,4,4].

##### Sums of Fibonacci numbers

Let’s find a simple expression for $\displaystyle \sum_{k=1}^nk^2f_{k}$. We search for an identity of the form
$\displaystyle \sum_{k=1}^{n}{k}^{2}\,f_k = n^2\sum_{k=1}^{3}{a}_{k}f_{n+k} + n\sum_{k=1}^{3}{b}_{k}f_{n+k} + \sum_{k=1}^{3}{c}_{k}f_{n+k} + d$
where $a_i$, $b_i$, $c_i$ and $d$ are unknowns.

First we setup the expression for the identity.

(%i17) sm: sum(k^2*fib(k), k, 1, n) =
sum(a[k-n]*n^2*fib(k), k, n+1, n+3) +
sum(b[k-n]*n*fib(k), k, n+1, n+3) +
sum(c[k-n]*fib(k), k, n+1, n+3) + d$(%i18) sm1: simplify_sum(sm)$
(%i19) eq: fibtophi(sm1)$ Now we evaluate eq so that we get 10 equations with 10 unknowns. (%i20) makelist(''eq, n, 10, 19)$

Now solve the system. We get many solutions and pick one by setting all parameters in the solution to 0.

(%i21) sol: solve(%);
solve: dependent equations eliminated: (8 10 9)
(%o21) [[d=-8,c[3]=3-%r3,b[3]=-%r2-2,a[3]=-%r1,c[2]=%r3+2,b[2]=%r2,
a[2]=%r1+1,c[1]=%r3,b[1]=%r2,a[1]=%r1]]
(%i22) sol1: subst(
map(lambda([x], x=0), %rnum_list),
sol);
(%o22) [[d=-8,c[3]=3,b[3]=-2,a[3]=0,c[2]=2,b[2]=0,a[2]=1,c[1]=0,b[1]=0,a[1]=0]]

Let’s look at the identity.

(%i23) subst(sol1[1], sm);
(%o23) sum(k^2*fib(k),k,1,n)=-2*n*fib(n+3)+3*fib(n+3)+n^2*fib(n+2)+2*fib(n+2)-8
(%i24) map(factorsum, %);
(%o24) sum(k^2*fib(k),k,1,n)=-(2*n-3)*fib(n+3)+(n^2+2)*fib(n+2)-8

which is

$\displaystyle \sum_{k=1}^{n}{k}^{2} f_k = \left( {n}^{2}+2\right) f_{n+2} - \left( 2\,n-3\right) f_{n+3} - 8$

Of course this is not a proof yet. But the proof is easy:

(%i25) ratsimp(fibtophi(simplify_sum(rhs(%) - lhs(%))));
(%o25) 0