Fibonacci Properties by Matrix Methods

Author(s): J. R. Silvester
Source: The Mathematical Gazette, Vol. 63, No. 425 (Oct., 1979), pp. 188-191
Published by: The Mathematical Association
Stable URL: http://www.jstor.org/stable/3617892 .
Accessed: 06/09/2013 08:47

Your use of the JSTOR archive indicates your acceptance of the Terms & Conditions of Use, available at .
http://www.jstor.org/page/info/about/policies/terms.jsp

.
JSTOR is a not-for-profit service that helps scholars, researchers, and students discover, use, and build upon a wide range of
content in a trusted digital archive. We use information technology and tools to increase productivity and facilitate new forms
of scholarship. For more information about JSTOR, please contact [email protected].

The Mathematical Association is collaborating with JSTOR to digitize, preserve and extend access to The
Mathematical Gazette.

http://www.jstor.org

This content downloaded from 128.83.63.20 on Fri, 6 Sep 2013 08:47:13 AM

All use subject to JSTOR Terms and Conditions
188 THE MATHEMATICALGAZETTE

the vector of partialderivatives aS/9bi as 21 (Ax + b - y). Settingthese to

zero and solving yields
A = (n i yxT-
y > yxT)(ny i XXT- x xT)-1,
b= (1/n)( y-
y AX x).
The correspondenceof these equations to their scalar counterparts

ni xy - x y y -a x
a= b=
n. x2 ( X)2 n

for the model y = ax + b is striking, and a tribute to the design of matrix

algebra. Both the methods outlined above have been extensively tested by
computer on data having up to 8 dimensions, producing most acceptable
results.
N. W. RICHARDS

Melton Mowbray College, Leicestershire

Fibonacci propertiesby matrixmethods

J. R. SILVESTER

The Fibonacci sequence

0, 1, 1, 2, 3, 5, 8, 13,...
is defined by u0 = 0, u- = 1, and un = u_ - + u_ 2 for n > 2. There are many
elementary formulae relating the various u,, most of which, since the
sequence is defined inductively, are themselves usually proved by induction.
For example,

Un- 1n+1-U- (-1) (1)

is certainlytrue for n = 1, and then

+
Un Un+2 - U+1 = Un(Un1 Un)- (Un + U,_) Un+

=U2-Un_l
U -Un n+l
U+1

provides the inductive step, showing that (1) holds for all n > 1. This article
describes a method by which many such formulae can be obtained instantly

This content downloaded from 128.83.63.20 on Fri, 6 Sep 2013 08:47:13 AM

All use subject to JSTOR Terms and Conditions
FIBONACCI PROPERTIES BY MATRIX METHODS 189

from easy matrix identities, the inductive arguments all being confined to
one preliminarylemma:

LEMMA.
'
'0 1- u
LetA = .Then A" n-
1 1 Un Un+1

PROOF. Thisis clearfor n = 1, andthen

An+ = An A

U_n-l u -0 1- U U n- + Un

Un Un+l 1 1 Un+ Un + Un+

Un Un+1

Un+1 Un+2

We can now obtain (1) by taking determinants:

n-I Un+
Un n-= det(An) = (det A)n = (-)n.
n++ - U1n

Since A is invertible,it is useful before proceedingto consider

A-" = (-l)"n n+1

-Un Un-1

From this it is clear that if we define u_n = (-l)"+1 u, for n > 1, the lemma
remains true for all integers n, positive, negative or zero. What we have
actually done is to use the defining recurrence relation to extend the
Fibonacci sequence to the left:
...,-3,2,-1, 1,0, 1, 1,2,3,....
As a harder example of the type of calculation we can now make with ease,
consider
Un- 1 Un Un+1 ~Un
An + (-1)n A-+ Un+l + Un-) I
Un Un + 1 n Un-I

Multiplyingthrough by Am, for any m, and taking the off-diagonal entries,

yields
=
Um+n + (-1)n Um-n (U n+1 + Un-) Um'

Here are some more calculations. A2"= (A")2gives

U2n- 1 2n Un-_ + u2n and u2n
2n
= - 11n+ + unUn+

This content downloaded from 128.83.63.20 on Fri, 6 Sep 2013 08:47:13 AM

All use subject to JSTOR Terms and Conditions
190 THE MATHEMATICALGAZETTE

the latter showing that un divides u2n.More generally we have that, modulo
u,, A" is a diagonal matrix, and so (A")' is also diagonal modulo u, for any
m; but (A")m= A"mhas off-diagonal entries u,,, from which it follows that
un divides unmfor all n, m. As an immediateconsequence, if u, is prime and
n =rs with 1 < r < n, 1 < s < n, then ur and us both divide un,whence ur
us= 1, and so n is either itself prime or equal to 4.
Next, given r and s, write d = (r, s) (the greatest common divisor). Then
d divides r and s, so ud divides ur and us; hence it divides (ur, us). But now
An+m = A" Am gives

Un+m = Un-1 IUm + Un U+ (2)

and we also know that d = rx + sy for some integersx andy, whence

Ud = Urx+ssy Urx- Usy
+ Urx
Usy+ 1

Since (ur, us) divides both u, and us, it divides urxand u,y; hence it divides
Ud. We have thus shown that (ur, us) = Ud.
Note that it is vital here that (2) is true without regard to the signs of n
and m. The above argument should be compared with [1] Theorem 179,
where the proof involves not only an auxiliary sequence (that of Lucas), but
parity considerations also complicate the argument.
Now let n be a positive integer. Since A is invertibleover Z, it is certainly
invertible modulo n; that is, we may consider A as a member of the finite
group GL2(Z,) (the group of invertible 2 x 2 matrices with elements in
Z,). So A has finite order in this group; in other words Am= I (modulo n)
for some m > 0, and we have shown that given n > 0 there exists m > 0
such that n divides um(cf [1] Theorem 180). A more elementaryversion of
this argument might run as follows: A, A2, A3, ... cannot all be distinct
modulo n, so there exist r, m > 0 with Ar+m= Ar (modulo n), and on multi-
plying by A-r we obtain Am= I (modulo n).
The usual formula for u, in terms of the roots cr, ,/ of the equation
x2 - x - 1 0 can be obtained from A. For the characteristicpolynomial
of A is
det(A-x I)= x2 x- 1,
and so r, / are the eigenvalues of A, and we can diagonalise A to obtain
A = P-l DP, where P is invertibleand

a 0
D=
O/
so A" = P-~ D" P, and on noting that
crn 0
Dn =
0 /~

This content downloaded from 128.83.63.20 on Fri, 6 Sep 2013 08:47:13 AM

All use subject to JSTOR Terms and Conditions
FIBONACCI PROPERTIES BY MATRIX METHODS 191

it is clear that u, = aa" + b/ for some a, b. Putting n = 0, 1 gives

immediately
an -Pf
un= a fi * (3).

Finally, the formula

lim U" = /(V5 - 1), (4),

n-oo Un+

which is usually obtained from (3) by noting that if a > f/ then Ii1 < 1
and f" -, 0 as n -. oo, can also be obtained from A by going projective:
writing
1
f(z) =
z+ 1
for the M6bius transformationcorrespondingto A, we have

n-1
fn(z)=
UnZ + Un+1

by the lemma, where fn means f iterated n times. So we must evaluate

lim fn(O),or lim f"-'(l), since f(O)= 1. Now if I < z < 1, then < z + 1 < 2,
n_oo n- oo
so that 4< f(z) < . Further,if z, z' E [, 1] then

If(z)- f(z')l = Iz- z' If(z)f(z') < Iz- z'l.

So the restriction f:[?, 11 - [, 1] is a contraction map, and has a unique
fixed point z* = f(z*); furthermore,

z* = lim fn(z) for any z E [, 1].

n- oo

But z* = l/(z* + 1) and z* E [, 11gives z* = (yV5- 1), as required.

Reference
1. G. H. Hardy and E. M. Wright, An introduction to the theory of numbers (4th edition).
Oxford University Press (1960).
J. R. SILVESTER

Department of Mathematics, Universityof London, King's College, Strand,

London WC2R 2LS

This content downloaded from 128.83.63.20 on Fri, 6 Sep 2013 08:47:13 AM

All use subject to JSTOR Terms and Conditions