wxMaxima 0.8.5

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.

Advertisements

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