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-

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) :=
           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,
(%i22) sol1: subst(
          map(lambda([x], x=0), %rnum_list),
(%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

The Euler line of a triangle

In my first post I will use Maxima to prove a nice theorem about three special points of the triangle. The nice thing is that no special knowledge about Euclidean geometry is needed, only basic properties of lines and points in the plane.

I will investigate points and lines in the plane. A point is represented as a pair [x,y] and for lines I use the explicit form k*x+n.

I need four little Maxima functions for computing with lines and points. The first computes the line through given points A and B:

line_A_B(A, B) :=
   block([k, n],
      k: (A[2]-B[2])/(A[1]-B[1]),
      n: A[2]-k*A[1],

Next, compute the line through a point A which is perpendicular to a line l:

line_A_l(A,l) :=
      k: -1/coeff(l, x),
      n: A[2]-k*A[1],

The intersection of two lines:

line_intersection(l1, l2) :=
      [sol:solve(l1=l2, x)],
      ratsimp(subst(sol, [x, l1])))$

Finally, a function which checks if a point A is on the line l:

point_on_line(A, l) :=
   is(equal(subst(map("=", [x,y], A), y-l),0))$

Now we have everything we need to start investigating the points of the triangle. The triangle is given by its vertices P1 = [x1, y1], P2 = [x2, y2] and P3 = [x3, y3]. I assume that the vertices are positioned so that no line I compute is vertical or horizontal (otherwise we can rotate the triangle in the plane).

First I define the vertices of the triangle in Maxima:

P1: [x1, y1]$
P2: [x2, y2]$
P3: [x3, y3]$


The line through a vertex and the midpoint of the opposite side of the triangle is called a median. All three medians in a triangle intersect in a common point which is called the centroid of the triangle. Let’s prove this using Maxima.

Compute the midpoints of the sides:

M1: (P2+P3)/2$
M2: (P1+P3)/2$
M3: (P1+P2)/2$

Now compute the medians:

m1: line_A_B(P1, M1)$
m2: line_A_B(P2, M2)$
m3: line_A_B(P3, M3)$

And the intersections (lines which begin with -> show the output):

Ce: line_intersection(m1, m2);
 -> [(x3+x2+x1)/3,(y3+y2+y1)/3]
line_intersection(m1, m3);
 -> [(x3+x2+x1)/3,(y3+y2+y1)/3]
line_intersection(m2, m3);
 -> [(x3+x2+x1)/3,(y3+y2+y1)/3]

Clearly all intersections are the same, we also get a nice formula for the centroid. We can also check that Ce (intersection of m1 and m2) is on the line m3:

point_on_line(Ce, m3);
 -> true


A perpendicular bisector is a line through the midpoint of a side of the triangle, which is perpendicular to the side. All three perpendicular bisectors intersect in a common point called circumcenter. Let’s prove this using Maxima.

Define the perpendicular bisectors:

pb1: line_A_l(M1, line_A_B(P2, P3))$
pb2: line_A_l(M2, line_A_B(P1, P3))$
pb3: line_A_l(M3, line_A_B(P1, P2))$

Check that the intersection of pb1 and pb2 is on pb3:

Ci: line_intersection(pb1, pb2)$
point_on_line(Ci, pb2);
 -> true


An altitude of a triangle is a line through a vertex which is perpendicular to the opposite side. Again, all three altitudes intersect in a common point called the orthocenter of the triangle. Again we can check this using Maxima.

Compute the altitudes:

a3: line_A_l(P3, line_A_B(P1, P2))$
a2: line_A_l(P2, line_A_B(P1, P3))$
a1: line_A_l(P1, line_A_B(P2, P3))$

Check that the intersection of a1 and a2 is on the line a3:

O: line_intersection(a1, a2)$
point_on_line(O, a3);
 -> true

The Euler line

There is a nice fact about the centroid, circumcenter and the orthocenter of a triangle. They are co-linear, that is they all are on a common line. Again, we can check this using Maxima:

e: line_A_B(Ce, Ci)$
point_on_line(O, e);
 -> true

Finally here is an image of a triangle with the centroid (in blue), circumcenter (in red) and orthocenter (in green). The black line is the Euler line.

This is the code in Maxima I used to create the image:

set_draw_defaults(proportional_axes = xy)$
wxplot_size:[400, 400]$
draw_triangle(P1, P2, P3) :=
            polygon([P1, P2, P3]),
            explicit(ev(m1), x, 0, 11),
            explicit(ev(m2), x, 0, 11),
            explicit(ev(m3), x, 0, 11),
            explicit(ev(pb1), x, 0, 11),
            explicit(ev(pb2), x, 0, 11),
            explicit(ev(pb3), x, 0, 11),
            explicit(ev(a1), x, 0, 11),
            explicit(ev(a2), x, 0, 11),
            explicit(ev(a3), x, 0, 11),
            explicit(ev(e), x, 0, 11),
         axis_top = false,
         axis_bottom = false,
         axis_left = false,
         axis_right = false,
         ytics = false,
         xtics = false))$