When we have a series or numbers, a formula for the general term makes it easy to compute any term directly.
However, sometimes it is not easy to find such a formula but it is much easier to find how one term relates
to some of the earlier terms.
For instance, the Fibonacci numbers `0,1,1,2,3,5,8,13,...` have a simple description
where each term is related to the two terms before it. If `F(n)` is the `n`th
term of this series then we have `F(n) = F(n-1) + F(n-2)`. This is called a recursive formula
or a recurrence relation
since it needs earlier terms to have been computed in order to compute a later term.
A recurrence formula also needs some initial terms since at the moment we could start form any two numbers and get
very difference series: 2, 1 leads to 2+1=3, 1+3=4, 7, 11, .... called the Lucas Numbers whereas 0, 1 leads 1, 1, 2, 3, 5, ... the Fibonacci Numbers.
So the complete recurrence relation is
`F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) if n >= 2 `
There is a formula for F(n) which involves only n:
`F(n) = (Phi^n - (-phi)^n) / sqrt5`
F(n) =
Phin – (–phi)n
√5
where Phi=(√5 + 1)/2 and phi=(√5 - 1)/2
Both the recurrence formula and the direct formula are enough to describe any term in the Fibonacci series but
the difference is seen is we need to find, say, F(100).
Though the recurrence formula is easy, we need to compute F(99) and F(98)
which in turn need F(97) and so on. Indeed we need to find every
number from F(0) up to F(97)before we can compute F(100).
The direct formula does not have this disadvantage.
However, sometimes all we have is a recursive definition and we do not know any direct formula for the general term of some series.
Also, recursive definitions are often much easier to find than a direct formula and also lend themselves to a nice method of
proof that the recursive definition is indeed correct.
Some Examples
Derangements
Suppose n people sit in a circle and they play a variation of Musical Chairs.
When the music starts they all start walking round the circle of chairs but
when it stops they all take a seat as quickly as they can. In this variation, no one is left without a seat! In how many ways can everybody be sitting in a new seat?
There are n! ways to seat n people in n seats since the first person has a choice on n seats, the second a choice of the
remaining n-1, the third n-2 and so on until the last person has just 1 choice. So in total there are
n×(n-1)×(n-2)×...×3×2×1 permutations
This is called n factorial and often written as n ! .
There is obviously only 1 way that everybody can be sitting in the same seat as when they started.
There are n! ways of seating n people in n seats, so then why is answer to this
puzzle not n! - 1?
Because that just excludes the permutation where everyone is seated in the same seat as originally.
Removing that one case is just the number of permutations where at least 1 person is not sitting in their original seat.
Our puzzle here puzzle asks for everybody to be sitting in a different seat.
Such a permutation of the n numbers (people) where no number (person) is in his original position
is called
a derangement or
a complete permutation or
a permutation without a fixed point
the subfactorial written using the upside-down exclamation mark
¡
after the number or else using
the ordinary exclamation mark (as for factorial) but before the number:
n¡ or !n .
For instance, label the seats 1 to n and give each person a label which was the original seat he or she was sitting in.
When the music stops, we go round the seat in order from 1 to n and note the label of the person sitting there. Thus we might have
3 people starting as (1,2,3) and ending up as (3,2,1) but in this case, the second item, the person sitting in the second seat,
is person 2 -- so he is sitting in his original seat and this is not a derangement.
However, the final seating order of (2,3,1) is a derangement as it means that
the first seat is occupied by person 2 (originally sitting in seat 2)
the second seat has the person originally in seat 3
the third seat has the person originally in seat 1
For 3 people there are only two derangements:
(2,3,1) and (3,1,2).
How many are there for 4 people? 5 people?
We can count the number of derangements on n people as follows:
Take the person labelled 1. He can end up in any of n-1 seats. Suppose he ends up in seat i. Then
consider the person labelled i. For each of the (n-1) possibilities for i,
the person labelled i now cannot sit in her original seat (number 1 is sitting there) and so can either end up in seat 1 or one of the other n-2
seats.
If she sits in seat 1, then two people have been seated, 1 in seat i and i in seat 1,
neither in their original seat. We are left with
n-2 people in n-2 seats -- the same problem but with 2 less people
On the other hand, if she does not sit in seat 1, then we relabel seat 1 as "i" (she is not going to sit there)
and there are n-1 people to sit in n-1 seats, each with 1 seat forbidden to them - the same problem but with n-1 people and seats.
If D(n) counts the number of derangements of n people we have the formula:
D(n) = (n – 1) ( D(n-1) + D(n-2) )
So, since with 1 person there are no derangements, and with 2 people there is just 1 derangement. So, by the recurrence formula above we have
D(3) = 2 ( D(2)+D(1) ) = 2(1+0) = 2, and so we know we found all the solutions in the above example with 3 people.
We have the counts of the
number of derangements of n people as the following series:
#seats(people)
1
2
3
4
5
6
...
#derangements
0
1
2
9
44
265
...
There is a direct formula for D(n) too:
D(n) = n!/2! – n!/3! + n!/4! – ... + (-1)n), n>2
Note that the recursion formula is usually not unique. Here we can also express D(n) as
D(n) = n D(n-1) + (-1)n
Things to do
Write out all the 9 derangements of 4 numbers.
Calculate D(4) using the factorial formula.
Is D(4) easier to calculate using the factorial formula or using the recurrence relation?
What about D(10)? Which is easier in this case?
Check that D(n) = n D(n-1) + (-1)n gives the same results as in the table above
for n=2, 3 and 4. What is the missing part of this formula - that is, how many initial terms are needed to completely
fix the numbers in this series?
Can you find a proof for D(n) = n D(n-1) + (-1)n?
What is the probablility that with 4 people none are sitting in the same seat when the music stops?
What about with 5 people?
Draw a graph of the probablility of getting a derangement with n people for n from 2 to 12
What does this suggest about the probability of a derangement as the number of people increases?
Variations
Our puzzle was presented as Musical Chairs. Here are some other variations of the same puzzle:
Secret Santa A week before the office Christmas Party, everyone buys one present, wraps it and puts it in Santa's Sack
under the Christmas Tree.
At the Party, everyone picks one present at random from the sack. No one wants their own present so
what is the probability that everyone picks
a different present to the one they put in? Practical solution 1: everyone picks a random name from a hat and buys a present for that named person
Practical solution 2: If you pick your own, put it back and pick another.
The distracted secretary at a busy office is so busy that,
given n individually addressed letters to put into the n addressed envelopes to get ready for posting, gets everything
wrong, so that no letter gets put in its correct envelope! Practical solution: Buy envelopes with a clear window and fold the letter so the addressee shows through the
window
The cloakroom (American: checkroom) attendant at a theatre inadvertently opens a window on a windy day
and all the tickets for the items the audience have left there
get blown off their pegs and mixed up. The attendant puts the tickets back on the pegs at random.
What is the probablilty no one gets their own belongings back after the show?
Practical solution: make sure the tickets are given out in order and the clothes put in order on the pegs!
No snap!
Two new packs of cards are bought, both having all the cards in order of suit and pip.
One is shuffled and given to someone else to deal, one is left in order. The two packs are then dealt simultaneously,
one card at a time, each pack onto its own pile.
What is the probability that no one shouts "Snap!" during the whole game.
Does it matter is one pack is in order?
In the game of snap, when two identical cards appear as two players deal their decks,
the first to shout "Snap" wins the cards. The one
with the most cards at the end of the game, when all cards have been dealt, is the winner.
Practical solution: just shuffle two packs of cards as the answer is identical!
Things to do
In our derangements, all n items get moved to a different place.
But given a permutation of items, we can count how many remain fixed and how many move.
Take the 4×3×2=24 permutations of {1,2,3,4}. Count how many items in each permutation are
fixed (from 0 to 4) and make a table of these frequencies. A derangement is a permutation with no fixed points.
For instance, with 3 numbers {1,2,3} we have the following:
# Fixed points
0
1
2
3
Total
Perms
(2,3,1) (3,1,2)
(1,3,2) (3,2,1) (2,1,3)
-
(1,2,3)
6
Extend the table to several more rows and investigate the patterns here.
As a check, here are the frequencies of permuations of {1,2,3,4} with their fixed point counts:
# Fixed points
0
1
2
3
4
Total=n!
# Perms{1}
0
1
1
# Perms {1,2}
1
0
1
2
# Perms {1,2,3}
2
3
0
1
6
# Perms {1,2,3,4}
9
8
6
0
1
24
Try to find recurrence relations to describe your numbers or explicit formulae.
Types and Properties of a Recurrence
Recursive definitions and recurrences have been used for a long time by mathematicians.
Here are a few terms used to describe them:
the Order of a recurrence
This is the earliest number of previous terms we need to find any term.
In s(n) = s(n-2 + s(n-4) we need the 4th term before so the
order of this recurrence is 4.
the Degree of a recurrence
If we have s(n) = s(n-1)2 + 1 then one term involves squares of an earlier
term.
In the sum of terms, the highest degree of a term is the degree of the recurrence.
This example has a term of degree 2 but the Fibonacci recurrence is of degree 1.
a Linear recurrence
A recurrence of degree 1 is a linear recurrence, such as P(n) = 2 P(n-1) + P(n-2) .
a Homogeneous recurrence
If the recurrence (without initial conditions) applies to the sequence consisting only of 0's then
the recurrence is homogeneous.
Thus s(n) = s(n-1)2 - s(n) and
F(n)=F(n-1)+F(n-2) are both homogeneous but s(n) = s(n-1)2 + 1
is not.
with Constant coefficients
If all the terms in a recurrence involve only previous terms and a constant multiplier,
then the recurrence has constant coefficients.
Thus P(n) = 2 P(n-1) + P(n-2)
has constant coefficients (and is linear) but the derangement recurrence
D(n) = n (D(n-1) + D(n-2)) has n as the multiplier of D(n-1) and D(n-2)
so does not have constant coefficients.
Generating Functions
Many series have a very compact representation as the coefficients of a power series:
the series s0, s1,s1, ... ,sn, ... are the coefficients of
x0, x1,x1, ... ,xn, ... .
But the main advantage is where the power series itself is a rational form: a fraction made from two simple expressions
in x. For example:
1
= 1 + x + x2 + x2 + ...
1 – x
so we say that the series (of coefficients) 1,1,1,1,1,... has generating function1/(1–x).
1
= 1 + 2 x + 3 x2 + 4 x2 + ...
(1 – x)2
so the series of natural numbers 1,2,3,4,... has generating function1/(1–x)2.
In the following, we often use GF as an abbreviation for Generating Function.
The relationship between Recurrences and Generating Functions
The interesting thing is that there is a simple relationship between the denominator of a GF and a recurrence relation which
defines the same series. Here are some examples:
the series of natural numbers
1,2,3,4,...
has generating function
1/(1–x)2 = 1/(1 – 2 x + x2)
and it has the recurrence
sn = 2 sn-1 - sn-2
We can see the relationship more clearly if we
rewrite the recurrence in this form:
sn - 2 sn-1 + sn-2 = 0
and compare that with the denominator of the GF, namely:
1 – 2 x + x2
This is a general principle!
Definitions and Notation
Beware of different golden ratio symbols used by different authors!
Where a formula below (or a simple re-arrangement of it) occurs in either Vajda
or Dunlap's book, the reference number they use is given here. Dunlap's formulae are listed in his Appendix A3.
Hoggatt's formula are from his "Fibonacci and Lucas Numbers" booklet. Full bibliographic
details are at the end of this page in the References section.
As used here
Vajda
Dunlap
Knuth
Definition
Description
Phi Φ
τ
τ
φ, α
√5 + 1
2
= 1.6180339...
Koshy uses α (page 78)
phi φ
–σ
–φ
–β
√5 – 1
2
= 0.6180339...
Koshy uses –β (page 78)
abs(x) |x|
|x|
|x|
|x|
abs(x) = x if x≥0; abs(x) = –x if x<0
the absolute value of a number, its magnitude; ignore the sign;
floor(x)
⌊x⌋
[x]
trunc(x), not used for x<0
⌊x⌋
the nearest integer ≤ x.
When x>0, this is "the integer part of x" or "truncate x"
i.e. delete any fractional part after the decimal point.
3=floor(3)=floor(3.1)=floor(3.9), -4=floor(-4)=floor(-3.1)=floor(-3.9)
the fractional part of x, i.e. the part of abs(x) after the decimal point
(
n r
)
(
n r
)
(
n r
)
(
n r
)
n!
r! (n – r)!
nCr n choose r; the element in row n column r of
Pascal's Triangle the coefficient of xr in (1+x)n
the number of ways of choosing r objects from a set of n different objects.
n≥0 and r≥0 (otherwise value is 0)
Fibonacci-type series with the rule S(i)=S(i-1)+S(i-2) for all integers i:
i
...
–6
–5
–4
–3
–2
–1
0
1
2
3
4
5
6
...
Fibonacci F(i)
...
–8
5
–3
2
–1
1
0
1
1
2
3
5
8
...
Lucas L(i)
...
18
–11
7
–4
3
–1
2
1
3
4
7
11
18
...
General Fib G(a,b,i)
...
13a–8b
–8a+5b
5a–3b
–3a+2b
2a–b
–a+b
a
b
a+b
a+2b
2a+3b
3a+5b
5a+8b
...
Linear Recurrence Relations
These linear homogeneous recurrence relations with constant coefficients and their sequences
listed here have some relationship to the Fibonacci numbers.
The "Fibonacci Rule" that we add the latest two numbers to get the next in a series,
can be applied to starting values:
0 and 1 to get the Fibonacci sequence
2 and 1 to get the Lucas numbers
a and b to get the General Fibonacci series
But among the Fibonacci and Lucas and General Fibonacci series
we can also find recurrence relationships which use other constant
multiples of earlier values too.
If the next term is a sum of integer multiples of earlier terms
then the recurrence is a linear recurrence. If the "earliest" term used to
compute sn is sn-k,
i.e. the previous k terms are used
to compute the next, then the order of the recurrence is
k. A recurrence of order k needs k initial terms to define it completely.
Strictly, on this web page,
we are looking at linear homogenous recurrence relations with constant coefficients
and these terms are examined in the examples here:
Fibonacci: sn = sn + sn-1 is linear or order 2
sn = 2 sn - sn-1 is linear of order 2
sn = 2 sn-1 is linear of order 1
sn = sn-2 + sn-3 is linear of order 3
sn = sn-1sn-2 is not linear
sn = sn-12 is not linear
sn = sn-1 + 1 is linear but not homogeneous because the last term, 1,
does not involve an earlier term of the sequence
sn = n sn-1 starting from
s1=1 defines the factorial numbers
as a linear recurrence (of order 1) but the coefficients are not constant.
Various forms of recurrence for the same sequence
Note that sequences may have many different types of recurrence that can be used
to define them exactly. For example, the
natural numbers0,1,2,3,4,5,6,...
are defined by each of the following
sn = n: an inhomogeneous recurrence
sn = sn-1 + 1 if n>1, s0=0:
an inhomogenous linear recurrence of order 1
sn = 2 sn-1 - sn-2 if n>2,
s0=0, s1 = 1
is a linear homogeneous recurrence relation with constant coefficients
Linear homogenous recurrence relations with constant coefficients
...have the property that
if the initial terms have a common factor g then so do all the terms in the series
there is an easy method of producing a formula for sn
in terms of n.
For a given linear recurrence, the k
series with initial conditions
1,0,0,...,0
0,1,0,0...,0
...
0,0,..0,1
each with k terms,
may be called the spanning series for a linear recurrence or order k.
This means that they will be enough to define any other recurrence with the same linear relation by taking multiples
of each according to their respective starting terms, and adding them. A formula for each of the
spanning series will therefore give a formula for a series with any given initial terms.
In the table below you will find the spanning series for many of the recurrences.
A helpful page on recurrence relations on this page is Tanya Khovanova's
Recursive Sequences
Order 2
These recurrence sequences are defined by 4 numbers:
s0, s1
and P and Q, Q≠0 where
sn = P sn-1 + Q sn-2
and are also known as Horadam Sequences H( s0, s1, P, Q )
after Alwyn Horadam who wrote about them in 1965.
Hypotenuse, h, of Pythagorean triangles
with consecutive legs (a,a+1,h)
Ratios of terms are convergents
to CF 5;[1,4] = 3 + 2 √2
Pell(2n+1), the odd Pell numbers
For many series, S(n), we can find a (simple) power-series expression in x
(that is, a sum of powers of x) where the coefficients
of the nth power of x is the nth term in the series, S(n):
G(x) =
∞ Σ i=0
S(i) xi
= S(0) + S(1) x + S(2) x2 + S(3) x3 + ...
Such an expression, G(x), if it exists for the series S is called
the generating function for S or GF for short.
To shift to the right (insert a 0 at the start of the series so all other terms have an index increased by 1),
multiply the GF by x; to shift to the left, divide by x.
There is much more on GFs on my Fibonomials page.
Fibonacci(n) 0,1,1,2,3,...
x
1 – x – x2
Lucas(n) 2,1,3,4,7,...
2 – x
1 – x – x2
G(a,b,n) a,b,a+b,a+2b,...
a + (b – a) x
1 – x – x2
Fibonacci(2n) 0,1,3,8,21,...
x
x2 – 3 x + 1
Lucas(2n) 2,3,7,18,...
2 – 3 x
x2 – 3 x + 1
G(a,b,2n) a,a+b,2a+3b,...
a + (b – 2a) x
x2 – 3 x + 1
Fibonacci(2n+1) 1,2,5,13,...
1 – x
x2 – 3 x + 1
Lucas(2n+1) 1,4,11,29,...
1 + x
x2 – 3 x + 1
G(a,b,2n+1) b,a+2b,3a+5b,...
b + (a – b) x
x2 – 3 x + 1
Fibonacci(3n) 2,8,34,144,...
2 x
1 – 4 x – x2
Lucas(3n) 2,4,18,76,...
2 – 4 x
1 – 4 x – x2
G(a,b,3n) a,a+2b,5a+8b,...
a + (2 b – 3 a) x
1 – 4 x – x2
Fibonacci(3n+1) 1,3,13,55,...
3 + x
1 – 4 x – x2
Lucas(3n+1) 3,11,47,199,...
3 x + 1
1 – 4 x – x2
G(a,b,3n+1) a+b,3a+5b,13a+21b,...
b + (2 a – b) x
1 – 4 x – x2
Fibonacci(3n+2) 1,5,21,89,...
x + 1
1 – 4 x – x2
Lucas(3n+2) 2,4,18,76,...
3 – x
1 – 4 x – x2
G(a,b,3n+2) a,a+2b,5a+8b,...
a + b + (b – a) x
1 – 4 x – x2
Fibonacci(k n)
F(k) x
1 – L(k) x + (–1)k x2
Lucas(k n)
2 – L(k) x
1 – L(k) x + (–1)k x2
G(a,b,kn)
a+(F(k)b–F(k+1)a)x
1–L(k)x+(–1)kx2
Fibonacci(n)2 02,12,12,22,32,...
x – x2
1 – 2 x – 2 x2 + x3
Lucas(n)2 22,12,32,42,...
4 – 7 x – x2
1 – 2 x – 2 x2 + x3
G(a,b,n)2 a2,b2,(a+b)2,...
a2+(b2–2a2)x–(a–b)2x2
1–2x–2x2+x3
Fib(n)Fib(n+1) 1×1,1×2,2×3,3×5,...
x
1 – 2 x – 2 x2 + x3
Lucas(n)Lucas(n+1) 2×1,1×3,3×4,4×7,...
2 – x + 2 x2
1 – 2 x – 2 x2 + x3
G(a,b,n)G(a,b,n+1) ab,b(a+b), (a+b)(a+2b),...
ab + b(b–a)x + a(a–b)x2
1–2x–2x2+x3
Fibonacci(n)3 03,13,13,23,33,...
x–2x2–x3
1–3x–6x2+3x3+x4
Lucas(n)3 23,13,33,43,...
8–23x–24x2+x3
1–3x–6x2+3x3+x4
Replacing x by x2 in a GF
inserts 0's between all values of the original series.
The series of even-indexed Fibonacci numbers only is the series
0,1,1,2,3,5,8,...
so it has the same GF as Fibonacci(2n) but with x2
replacing x:
x2/(x4 – 3 x2 + 1)
for the series 0,0,1,0,3,0,8,0,21,... .
The GF of 1,2,5,13,... is that of
Fib(2n+1)
which is
(1 – x)/(x2 – 3 x + 1)
so 1,0,2,0,5,0,13,... has GF
(1 – x2)/(x4 – 3 x2 + 1)
To insert an extra 0 at the start, multiply the GF by x.
So the GF for the odd-indexed Fibonacci numbers only in their correct positions in the Fibonacci series
with Fib(2n+1) is the coefficient of x2n+1
is therefore x (1 – x2)/(x4 - 3 x2 + 1)
for the series 0,1,0,2,0,5,0,13,... .
Adding these two GFs, that is, for Fib(2n) as the coefficient of x2n
and Fib(2n+1) as the coefficient of x2n+1
should then give the complete
Fibonacci series GF:
We can check that
x2/(x4 - 3 x2 + 1) + x (1 – x2)/(x4 - 3 x2 + 1) = x/(1 – x – x2)
which is the GF of 0,1,1,2,3,5,8,13,21,... as required!
Multiplying a GF by a constant k multiples all the members of the series by k.
A series formed by adding two series S and T element-wise to form the series {S(n)+T(n) for n=1,2,3,...},
has a GF which is the sum of the two separate GFs.
Check that a Fib[n-1] + b Fib[n] gives the GF of G(a,b).
Exponential Generating Functions
∞
n
F(n)
zn
=
ePhi z - e -phi z
n!
√5
, z in C
See, e.g., Solving Linear Recurrences from Differential Equations
in the Exponential Manner and Vice Versa W Oberschelp
in Applications of Fibonacci Numbers Vol 6 (1996) pages 365-380
Trigonometric Formulae
F(n) =
floor( (n-1)/2 )
k = 1
(
3 + 2 cos
2kπ
)
n
, n ≥ 1
D Lind, Problem H-93, FQ 4 (1966), page 332
L(n) =
floor( (n-2)/2 )
k = 0
(
3 + 2 cos
(2k+1)π
)
n
, n ≥ 2
D Lind, Problem H-93, FQ 4 (1966), page 252, corrected page 332
Hyperbolic Functions
Here we use g for ln(Phi), the natural log of Phi
so that cosh(g) = √5 / 2.
Several of the formulae above can be derived
using hyperbolic functions - see chapter XI of Vajda.
A T Benjamin, J J QuinnProofs That Really Count
Mathematical Association of America, 2003, ISBN 0-88385-333-7, hardback, 194 pages.
shown as B&Q(2003) in the Table above
Art Benjamin and Jennifer Quinn have a wonderful knack of presenting proofs that involve counting arrangements
of dominoes and tiling patterns in two ways that convince you that a formula really is true and not just
"proved"! The identities proved mainly involve Fibonacci, Lucas and the General Fibonacci series with chapters on continued
fractions, binomial identites, the Harmonic and Stirling numbers too. There is so much here to inspire
students to find proofs for themselves and to show that proofs can be fun too! Important notation difference:
Benjamin and Quinn use fn for the Fibonacci number
F(n+1)
Bergum and Hoggatt (1975)
G. E. Bergum and V. E. Hoggatt, Jr.
Sums and Products for Recurring Sequences, Fib Q 13 (1975), pages 115-120.
Benjamin, Carnes, Cloitre (2009)
Recounting the Sums of Cubes of Fibonacci Numbers
A T Benjamin, T A. Carnes, B Cloitre,
Congressus Numerantium, Proceedings of the Eleventh International Conference on
Fibonacci Numbers and their Applications, William Webb (ed.), Vol 194, pp. 45-51, 2009.
is a classic and monumental reference work on all aspects
of Number Theory in 3 volumes (volume II is on Diophantine Analysis and volume III on Quadratic and Higher Forms).
Although not up-to-date (the original edition was 1952) it is still a comprehensive summary of useful
historical and early
references on all aspects of Number Theory.
The link is to a new cheap Dover paperback edition (2005) of Volume 1 which contains the most about Fibonacci Numbers,
Lucas numbers and the golden section: see
Chapter XV11 on Recurring Series, Lucas' un, vn where he uses
the series of Pisano for what we now call the Fibonacci numbers.
An introductory book strong on the geometry and natural aspects of the golden section
but it does not include much on the mathematical detail. Beware - some of the
formulae in the Appendix are wrong! Dunlap has copied them from Vajda's book (see below)
and he has faithfully preserved all of the original errors!
The formulae on this page (that you are now reading)
are corrected versions and have been verified.
Fairgrieve and Gould (2005)
Product Difference Fibonacci Identities of Simson, Gelin-Cesáro, Tagiuri and Generalizations.
S Fairgrieve and H W Gould, The Fibonacci Quarterly 43 (2005), 137-141.
Gould (1977)
H W Gould,
A Fibonacci Formula of Lucas and its Subsequent Manifestations and Rediscoveries ,
Fibonacci Quarterly vol 15 (1977) pages 25-29
R L Graham, D E Knuth, O PatashnikConcrete Mathematics
Second Edition (1994), hardback, Addison-Wesley.
No - this is not a book about proportions of sand to cement when laying foundations for buildings
.
The title is meant as an antidote to the "Abstract Mathematics"
courses so often found in the curricullum of a university maths degree.
As such, it is the book to dip into if you want to go really deeply into any part of the mathematics
covered on this Fibonacci and Phi site. However, it quickly gets to an advanced mathematics undergraduate level after some
nice introductions to every topic.
There are
notes left in the margins which were inserted by students taking the original courses based on this book at Stanford university and
they are interesting, often useful and sometimes quite funny.
V E Hoggatt Jr
"Fibonacci and Lucas Numbers" published by
The Fibonacci Association,
1969 (Houghton Mifflin).
A very good introduction to the Fibonacci and Lucas Numbers written
by a founder of the Fibonacci Quarterly.
Hoggatt and Lind (1969)
V E Hoggatt Jr, D A Lind,
Compositions and Fibonacci Numbers, The Fibonacci Quarterly, Vol.
7, No. 3 (Oct., 1969), pp. 253-266.
F T Howard (2003) "The Sum of the Squares of Two Generalized Fibonacci Numbers"
FQ vol 41
pages 80-84.
Hudson and Winans (1981)
A Complete Characterization of the Decimal
Fractions That Can Be Represented as Σ 10k(a + 1)Fai ,
where Fai is the aith
Fibonacci Number R H Hudson, C F Winans The Fibonacci Quarterly 19, no. 5 (1981)
pages 414-421.
See also: A Complete Characterization Of B-Power Fractions That Can
Be Represented As Series Of General N-Bonacci Numbers
J-Z Lee, J-S Lee Fibonacci Quarterly 25 (1987) pages 72-75.
I J Good Complex Fibonacci And Lucas Numbers, Continued
Fractions, And The Square Root Of The Golden Ratio, Fib Q 31 (1993) pages 7-19
R Johnson (Durham university) has an excellent web page
on the power of matrix methods to establish many Fibonacci formula with ease (but it does rely on
at least undergraduate level matrix mathematics). See the Matrix methods for Fibonacci and
Related Sequences link to a Postscript and PDF version on his
Fibonacci Resources web page.
The latest version (Nov 12, 2004) contains an appendix showing how formulae developed in
Johnson's paper can prove almost all the identities here in my table above.
This is a new book packed full of an amazing number of Fibonacci and related equations,
culled from the pages of the Fibonacci Quarterly.
Although initially impressive in its size and breadth,
be aware that there are far too many typos, errors and missing or irrelevant conditions in many of its formulae
as well as some glaring omissions and misattributions
particularly with respect to the original references for a number
of the formulae. Although Fibonacci representations of integers are included
Zeckendorf himself is never even mentioned!
There are lots of exercises with answers to the odd-numbered questions.
Long (1981)
The Decimal Expansion Of 1/89 And Related Results C Long Fibonacci Quarterly 19 (1985)
pages 53-55
E Lucas, "Théorie des Fonctions Numériques Simplement Périodiques"
in American Journal of Mathematics vol 1 (1878) pages 184-240 and 289-321.
A New Formula For The Sum Of The Sixth Powers
Of Fibonacci Numbers H Ohtsuka, S Nakamura, Congressus Numerantium Vol. 201 (2010),
Proceedings of the Thirteenth Conference on Fibonacci Numbers and their Applications , pp.297-300.
S Rabinowitz "Algorithmic Manipulation of Fibonacci Identities" in
Applications of
Fibonacci Numbers: Proceedings of the Sixth International Research Conference
on Fibonacci Numbers and their Applications, editors G E Bergum, A N Philippou, A F Horodam;
Kluwer Academic (1996), pages 389 - 408.
This is a wonderful book, a classic, originally published in 1989
and now back in print in this Dover edition. This book is full of formulae on
the Fibonacci numbers and Phi and the Lucas numbers. The whole book develops the formulae step by step,
proving each from earlier ones or occasionally from scratch. It has a few errors in its formulae
and all of them have been dutifully and exactly copied by authors such as Dunlap (see above) and others!
Where I have identified errors, they have been corrected here on this page.
Things to do
.
The title is meant as an antidote to the "Abstract Mathematics"
courses so often found in the curricullum of a university maths degree.
Fibonacci and Phi in the Arts
Fibonacci Home Page
© 1996-2013 Dr Ron Knott
