I have released wxMaxima version 0.8.5. There are no major changes in this release. One of the cool things added are two new translations (Greek an Japanese). wxMaxima can now be used in 14 languages (besides English). Thanks to all the translators for their hard work.

# wxMaxima

# Fibonacci numbers

Fibonacci numbers are numbers in the Fibonacci sequence . We define the Fibonacci sequence recursively as and .

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

(%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

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 using the golden ratio . We will use the `fibtophi`

function.

(%i4) fib(n)$ (%i5) fibtophi(%); (%o5) (%phi^n-(1-%phi)^n)/(2*%phi-1)

which gives . Maxima uses the identity to simplify expressions which contain .

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 . 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:

(%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

.

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 . We search for an identity of the form

where , , and 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

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

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