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},

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.

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.

 

The Ghosts of Departed Quantities and the difficulties of teaching and learning caculus

Bishop Berkeley writes this attack on the apparent supernatural reasoning involved in calculus.  The infidel was probably Halley (of comet fame) or Newton.

If pupils find the subject difficult to understand at school, and teachers find it difficult to teach, then the reason may be articulated in this book by the great man.

160522Berkeley

Quotes include:

“Now to conceive a Quantity infinitely small, that is, infinitely less than any sensible or imaginable Quantity, or any the least finite Magnitude, is, I confess, above my Capacity. But to conceive a Part of such infinitely small Quantity, that shall be still infinitely less than it, and consequently though multiply’d infinitely shall never equal the minutest finite Quantity, is, I suspect, an infinite Difficulty to any Man whatsoever”

and.

“They are neither finite Quantities nor Quantities infinitely small, nor yet nothing. May we not call them the Ghosts of departed Quantities?”

Some sympathy for the thesis is gained by Berkeley’s examination of tangent reasoning:

“Therefore the two errors being equal and contrary destroy each other; the first error of defect being corrected by a second error of excess. ……. If you had committed only one error, you would not have come at a true Solution of the Problem. But by virtue of a twofold mistake you arrive, though not at Science, yet at Truth. For Science it cannot be called, when you proceed blindfold, and arrive at the Truth not knowing how or by what means.”

The student of sixth form level mathematics who is eager to see how this is resolved must continue their path to mathematical enlightenment by studying the \epsilon-\delta Analysis of Cauchy, Riemann and Weierstrass.

 

 

 

 

Euler and the Properties of the Second Derivative

The summer examination season sees pupils searching for maximums and minimums on their text papers.

This long-standing pursuit was initiated by the likes of Newton and Leibniz in their calculus.

It can be all too difficult to think about for some:

“our modern Analysts are not content to consider only the Differences of finite Quantities: they also consider the Differences of those Differences, and the Differences of the Differences of the first Differences. And so on ad infinitum.”

Bishop Berkeley, The Analyst, 1734

The example above is one in which Euler demonstrates the geometrical significance of the first and second derivatives.

Note that the Point of Inflection is where f''(x)=\dfrac{d^{2}y}{dx^{2}}=0 and is a change from upward to downward convex curvature, or vice versa.  There is no need for f'(x)=\dfrac{dy}{dx}=0 too.

 

 

 

 

Yachting and similar triangles

A yacht has two parallel masts which are both perpendicular to a level deck.  One mast is 12 m high, the other is 8 m.  Stays are rigged from the head if each mast to the foot of the other.  Find the perpendicular height of the crossing point above the deck.

SailBoat

Finding the height of the crossing point is a good similar triangles challenge for bright maths pupils.  In fact that the distance between the two masts is not given introduces two variables and makes this a subtle challenge.

160508SimilarSailboat

I find the independence of ‘h’ with the distance between the masts intriguing.

 

The linear combination of a sine and a cosine is itself a sine wave

A linear combination of two functions, f(x) and g(x) is a sum involving constant multiples of the functions.  That is,

a f(x)+b g(x)

where a, b \in \mathbb{R}.

So, in the case of \sin x and \cos x, we would have,

a\sin(x)+b\cos(x).

It is a slightly surprising fact that the linear combination of two sine waves is itself a sine wave.  The set of sine waves is closed under linear combination.

The in the featured animation, a\sin(x) is green and dotted and b\cos(x) is red and dotted.  The resulting linear combination is the continuous blue line.  The value a is set to 2.5, whereas the value b is animated.

This principle occurs in A level maths, Core 3, and is responsible for many long and complex questions.

depression near Greenland – logarithmic spirals in nature

Logarithmic spirals frequently occur in nature.  Is this such a manifestation?

The general equation for a logarithmic spiral is as follows.

r=ae^{b\theta}

Changing the variables a and b produces spirals of different qualities.  The a  is really an enlargement scale factor but the b controls how the spiral grows per revolution.

If b=0.2 is more representative of an ammonite then b=0.75 seems to be our Greenland depression.

Wouldn’t it be nice to take the equations for atmospheric fluid dynamics and show this explicitly.  Unfortunately this is beyond the scope of this blog: here we have circular motion on the surface of a rotating sphere in an elliptical orbit … . The way to go with this would be to take the basic baratropic equations and then perform a scale analysis to disregard ‘small’ terms.  At this point the pure mathematician get frustrated with approximations and goes into a sulk.  We are left with contemplating the beautiful images though…

third century wisdom of Diophantus gives us the essential truth about teaching and learning mathematics

The Google facsimile of the 1621 edition of Diophantus’s Arithmetica lays out, in original Greek and Latin translation, the essentials for success in teaching and learning mathematics.  Also included is the translation of the second half by Heath.

When I first studied and learned to love mathematics I was beset by friends and family who stridently claimed that this field of study was closed to them because of some biological, or other, reason.  This always seemed to undervalue my own effort in getting off the first page.

Teachers of mathematics cannot be permitted to admit that nature is able to restrict the ability to learn the subject but the oriental wisdom of the student making their way to the master is a precondition for success when things seem difficult; in tales of martial arts the student must somehow prepare themselves to learn.

So,

  1.  Mathematics appears rather difficult if one is not familiar with it.
  2. Students need energy, eagerness and enthusiasm.
  3. When such motivation is backed up by good teaching rapid learning results.

In school we struggle because of item 1 and bear our hearts to gain item 2, being so often rebuffed.  I suppose that we get paid for 1 and 2 because, when item 3 is achieved the job is it’s own reward.