Rabbits, Matrices and the Golden Section – nth term of the Fibonacci Sequence by diagonalising a matrix

Fibonacci Sequence

Leonardo Pisano, or Leonardo Fibonacci, studied rabbit populations in 1202 in the following way.

Rabbit couples (male and female) inhabit an island.  Each rabbit couple becomes fertile 2 months after being born and then begets a male-female pair every month thereafter.  If the population of the island starts with one couple, how many couples, f_{n}, are there after n months?

To work this out one needs to add the number of rabbit couples alive after n-1 months, f_{n-1} (since there are no deaths), with the new-born couples.  The number of new-born couples is equal to the number of  fertile rabbit couples, which is just the number of rabbit couples alive two months previously, f_{n-2}.  Hence,

f_{n}=f_{n-1}+f_{n-2}[\latex],

resulting in the numbers,

0, 1, 1, 2, 3, 5, 8, ... .

Some quote the first term as 1, but let's say that f_{0}=0 and start from there instead.

Matrices

After teaching matrices as a Further Mathematics topic for many years I had always concentrated on geometric interpretations to illustrate the topic.  The topic of diagonalisation, was restricted to symmetric matrices, which produce mutually perpendicular eigen-vectors.  The denationalization process could be visualised as a rotation to a new set of axes, a readable transformation (stretch etc.) followed by a rotation back the original basis.

Recently, whilst reading a a text book on Number Theory and Cryptography (Baldoni,Ciliberto,Piacentini Cattaneo) I came across the following example, which should be within the reach of Further Mathematics students.

Fibonacci Sequence by Matrices

The Fibonacci Sequence can be expressed in matrices:

A=\begin{pmatrix} 0 & 1\\ 1 & 1 \end{pmatrix}

then,

A \begin{pmatrix} f_{n-2} \\f_{n-1} \end{pmatrix}= \begin{pmatrix} f_{n-1} \\f_{n-2} +f_{n-1}\end{pmatrix}=\begin{pmatrix} f_{n-1} \\f_{n} \end{pmatrix}.

This is a recursive definition.  A good questions is: Is there a formula for of f_{n}, which does not involve calculating intermediate values?

Well, each stage of this calculation involves a matrix multiplication by A, thus

A \begin{pmatrix} f_{n-2} \\f_{n-1} \end{pmatrix}=A^{n}  \begin{pmatrix} f_{0} \\f_{1} \end{pmatrix}

and all that is needed is to calculate A^{n}.

A little bit of matrix multiplication yields the following matrix power series for A:

A^{1}=\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}

A^{2}=\begin{pmatrix} 1 & 1 \\ 1 & 2 \end{pmatrix}

A^{3}=\begin{pmatrix} 1 & 2 \\ 2 & 3 \end{pmatrix}

A^{4}=\begin{pmatrix} 2 & 3 \\ 3 & 5 \end{pmatrix}

and so on, where the Fibonacci numbers appear as entries in successive matrices.

Interesting, but finding a formula for the n^{th} Fibonacci number looks to be no closer.

Had the matrix A been a diagonal matrix, things would have been different because if

B=\begin{pmatrix} a & 0 \\ 0 & b \end{pmatrix}

then,

B^{n}=\begin{pmatrix} a^{n} & 0 \\ 0 & b^{n}\end{pmatrix}.

However, it is possible to diagonalise the matrix A.

An n \times n matrix can be diagonalised if and only if it has n distinct eigen-values.

Eigen values are given by the characteristic equation,

\begin{vmatrix} 0-t & 1 \\ 1 & 1-t \end{vmatrix}=0

that is,

-t(1-t)-1=0 or t^{2}-t-1=0.

The solution to this quadratic is the Golden Ratio \Phi,

t=\Phi=\dfrac{ 1+ \sqrt{5}}{2} and \dfrac{ 1- \sqrt{5}}{2}

As it has distinct roots, A can be diagonalised using it's eigen-vectors,

\begin{pmatrix} \frac{-1+\sqrt{5}}{2} \\ 1\end{pmatrix} and \begin{pmatrix} \frac{-1-\sqrt{5}}{2} \\ 1\end{pmatrix},

to get matrix C,

C=\begin{pmatrix}  \frac{-1-\sqrt{5}}{2} &  \frac{-1+\sqrt{5}}{2} \\ 1 & 1 \end{pmatrix},

in which case,

C^{-1}AC=D=\begin{pmatrix} \frac{1-\sqrt{5}}{2} & 0 \\ 0 & \frac{1+\sqrt{5}}{2} \end{pmatrix}

or

A=CDC^{-1}.

It is now an easy matter to find successive powers of A:

A^{n}=(CDC^{-1})^{n}=CD^{n}C^{-1}.

Hence,

\begin{pmatrix} f_{n-1} \\f_{n} \end{pmatrix}=A \begin{pmatrix} f_{n-2} \\f_{n-1} \end{pmatrix}=A^{n}  \begin{pmatrix} f_{0} \\f_{1} \end{pmatrix}= CD^{n}C^{-1}\begin{pmatrix} f_{0} \\f_{1} \end{pmatrix}

where,

\begin{pmatrix} f_{n-1} \\f_{n} \end{pmatrix}=A^{n}  \begin{pmatrix} f_{0} \\f_{1} \end{pmatrix}=\begin{pmatrix}  \frac{-1-\sqrt{5}}{2} &  \frac{-1+\sqrt{5}}{2} \\ 1 & 1 \end{pmatrix} \begin{pmatrix} \left(\frac{1-\sqrt{5}}{2}\right)^{n} & 0 \\ 0 & \left(\frac{1+\sqrt{5}}{2}\right)^{n} \end{pmatrix}\begin{pmatrix} -\frac{1}{\sqrt{5}} & \frac{5-\sqrt{5}}{10}\\\frac{1}{\sqrt{5}} & \frac{5+\sqrt{5}}{10}\end{pmatrix}\begin{pmatrix} f_{0} \\f_{1} \end{pmatrix}

thus,

\begin{pmatrix} f_{n-1} \\f_{n} \end{pmatrix}=\begin{pmatrix} \frac{1}{\sqrt{5}} \left[ \left( \frac{1+\sqrt{5}}{2} \right) ^{n-1}- \left( \frac{1-\sqrt{5}}{2} \right) ^{n-1}\right] \\ \frac{1}{\sqrt{5}} \left[ \left( \frac{1+\sqrt{5}}{2} \right) ^{n}- \left( \frac{1-\sqrt{5}}{2} \right) ^{n}\right]\end{pmatrix},

and hence the formula for the n^{th} Fibonacci number is,

f_{n}=\frac{1}{\sqrt{5}} \left[ \left( \frac{1+\sqrt{5}}{2} \right) ^{n}- \left( \frac{1-\sqrt{5}}{2} \right) ^{n}\right].

Matrices and Wolfram Alpha

Tricky calculations are need to verify the above by hand.  Help is at hand from the Wolfram Alpha website.  Other computational engines and environments exist but this is free and readily available.

Encoding matrix A as [[0,1],[1,1]] etc. a long string of characters can be prepared separately and then pasted into the command line as follows.

 

 

Area of a circle – proof by exhuastion

Once \pi has been defined as the ratio circumference to diameter, the area of a circle must be \pi r^{2}.

A proof relies on an infinite, limiting process which paves the way to some calculus-like ideas.

A circle is cut up into 6 sectors which are then rearranged into a near rectangle,

What doesn’t look too close to a rectangle at 6 sectors looks better at 26:

As the number of sectors becomes very big the shape becomes indistinguishable from a rectangle and the argument is complete.

I think that Archimedes used such arguments, or, proof by exhaustion, in some of his solid geometry work.

Integration by Substitution

Current UK exam textbooks pass over proofs and mathematical discussions in a hurry to show the ‘how to’ of exam questions.

Integration by substitution is a little more than just backwards chain-rule and deserves a fuller treatment.

Try this,

Let,

y=\displaystyle \int \textnormal{f}(x) \ \textnormal{d}x

then,

\dfrac{\textnormal{d}y}{\textnormal{d}x}=\textnormal{f}(x)

Suppose that there exists a function g, of another variable u, such that x=\textnormal{g}(u) and let, \textnormal{f}(x)=\textnormal{f}(\textnormal{g}(u))=\textnormal{F}(u). So that,

\dfrac{\textnormal{d}y}{\textnormal{d}x}=\textnormal{F}(u)

Now, by the chain rule,

\dfrac{\textnormal{d}y}{\textnormal{d}u}=\dfrac{\textnormal{d}y}{\textnormal{d}x}\times \dfrac{\textnormal{d}x}{\textnormal{d}u}=\textnormal{F}(u)\dfrac{\textnormal{d}x}{\textnormal{d}u}

Hence,

y=\displaystyle \int \dfrac{\textnormal{d}y}{\textnormal{d}u} \ \textnormal{d}u=\displaystyle \int \textnormal{F}(u)\dfrac{\textnormal{d}x}{\textnormal{d}u} \ \textnormal{d}u

i.e.

y=\displaystyle \int \textnormal{f}(x) \ \textnormal{d}x=\displaystyle \int \textnormal{F}(u)\dfrac{\textnormal{d}x}{\textnormal{d}u} \ \textnormal{d}u

Differentiation From First Principles

The gradient of a smooth curve, \textnormal{f}(x), at a point x is the gradient of the tangent to the curve at the point x. Point P is on the curve and Q is a neighbouring point whose x value is displaced a small quantity, \delta x.

The idea behind differentiation is that as \delta x becomes very small, the gradient of PQ tends towards the gradient of the curve. In the limit as \delta x becomes infinitesimally close to zero, the gradient PQ becomes the gradient of the curve.

We write:

\textnormal{gradient f}(x)=\dfrac{\textnormal{d}y}{\textnormal{d}x}=\lim_{\delta x \rightarrow 0}\left(\dfrac{\delta y}{\delta x}\right)=\lim_{\delta x \rightarrow 0}\left(\dfrac{\textnormal{f}(x+\delta x)-\textnormal{f}(x)}{\delta x}\right)

there is a fair bit of analytic work missing (higher education) to make these ideas sound.

We also write:

\dfrac{\textnormal{d}y}{\textnormal{d}x}=\textnormal{f}'(x).

STANDARD RESULTS

Standard results can be proved for different functions.

If \textnormal{f}(x)=x^{n} then

If \textnormal{f}(x)=\sin x, then we need to consider the small angle approximation that is if \delta x radians is very small (infinitesimal), then \delta x\approx\sin \delta x and \cos \delta x \approx 1, and compound trigonometry from which follows,


The differentiation process described above is linear and extends to more complicated functions. That is to say that if, y=a\textnormal{f}(x)+b\textnormal{g}(x) where a,b \in \mathbb{R},
\dfrac{\textnormal{d}y}{\textnormal{d}x}=a\textnormal{f}'(x)+b\textnormal{g}'(x)

The Fundamental Theorem of Calculus

Integration is introduced as the reversal of differentiation i.e. in solving a differential equation, \dfrac{\textnormal{d}y}{\textnormal{d}x}=\textnormal{g}(x). The link between integration and area is often passed over and is the subject of the Fundamental Theorem of Calculus. [The following discussion can be adapted for a decreasing function or, piece-wise, a function which successively increases or decreases.]

Consider and area function, A(x), defined by the area under \textnormal{f}(x) between a and and a general point, x. If a small increment, \delta x, is applied to x giving a small element, \delta A of area. Now,

\textnormal{f}(x)\delta x \leqslant \delta A \leqslant \textnormal{f}(x+\delta x)\delta x

dividing though by \delta x, gives,

\textnormal{f}(x) \leqslant \dfrac{\delta A}{\delta x} \leqslant \textnormal{f}(x+\delta x),

a limit sandwich where, as \delta x \rightarrow 0,

\dfrac{\textnormal{d}A}{\textnormal{d}x}=\textnormal{f}(x)

The curve function, \textnormal{f}(x) is the derivative of the area function; hence the area function is the anti-derivative of the curve function and,

\displaystyle\int \textnormal{f}(x) \textnormal{d}x=A(x).

 

Carr’s Synopsis and Sixth Term Entrance Papers

Students in search of extension work in maths, particularly as far as Sixth Term Entrance Papers (STEP) are concerned, should peruse Carr’s Synopsis of results in Elementary Pure Mathematics.

This book is famous for being the volume used by the autodidact Ramanujan to teach himself mathematics.  The book is merely a list of results and student how works through them, proving each one, will develop a strong ability in the subject.  This life line into higher mathematics could not be produced in the same form in today’s educational and publishing context but, perhaps, Carr deserves a place as one of the subject’s great educators.

Higher mathematics is about generalisation and abstraction.  Because of this, school mathematics students can find university text books unreadable.  In such a context how can harder, higher level questions be set using the frame work of sixth form mathematics? The answer to this question is to wind the clock back to the 1880s and see how the subject was constructed then.  Carr does this for us; many useful stages in school mathematics are listed here with extensions and generalisation written in generally sixth form recognisable form.

Take question 1 from this year’s (2016) STEP I exam.  Pupils will only have to be familiar with the first six results to tackle this quickly.

carr1to6

The question play is all about the divisibility of,

x^{2n+1}+1

which result 6, above, tells us is

(x+1)(x^{2n}-x^{2n-1}+\dots+1).

Question game play leads us to factorise large numbers (without use of calculator):

\dfrac{300^{3}+1}{301}=89911\times 90091

and

\dfrac{7^{49}+1}{7^{7}+1}=[(7^{7}+1)^{3}-7^{4}(7^{14}+7^{7}+1)][(7^{7}+1)^{3}+7^{4}(7^{14}+7^{7}+1)]

in a difference of two squares (result 1) construction.

Full solution is attached.

step-i-2016-q1

Transformations of Sine

Functional notation and transformations is always tricky to teach and understand.  GCSE students will meet this in Year 11.   In general, transformations applied after the function are more easily understood:

y=f(x)+a  or  y=af(x)

Something very un-intuitive happens when the transformation is applied to the argument of the function:

y=f(x-a)  or  y=f(ax)

with things stretching when they look like they should be compressing and other things moving the wrong way.

Mathematics is not always obvious, if it were we wouldn’t need it.

Try this for transformations of Sine.

 

Parallelograms generalise Pythagoras to any triangle

There’s always space on the inter-web for another proof of Pythagoras’s Theorem.  Here’s one that uses the following equal areas property of parallelograms.

160530AreaOfParallelogram

This kind of area chopping and shape translation is a feature of Euclidean geometry and our senses support it’s veracity at the order of size of the classroom.

The squares on the sides of a right-angle triangle set up a system of parallel lines which can then be used to demonstrate the Theorem using the above equal areas property.

160529PythagProof

The thread does not stop here though.  Taking the parallel line structure which makes this work we get a generalisation of Pythagoras to non-right-angled triangles with the area of the parallelogram on the longest side being the sum of the areas of those constructed on the other two sides.

160530PythagGeneralised