3.3. THE LIMIT OF A SEQUENCE 81
16. In the situation of the Fibonacci sequence show that the formula for the nth term canbe found and is given by
an =
√5
5
(1+
√5
2
)n
−√
55
(1−
√5
2
)n
.
Hint: You might be able to do this by induction but a better way would be to lookfor a solution to the recurrence relation, an+2 ≡ an + an+1 of the form rn. You willbe able to show that there are two values of r which work, one of which is r = 1+
√5
2 .Next you can observe that if rn
1 and rn2 both satisfy the recurrence relation then so
does crn1 +drn
2 for any choice of constants c,d. Then you try to pick c and d such thatthe conditions, a1 = 1 and a2 = 1 both hold. This general approach often works forfinding solutions to such recurrence relations.
17. In an annuity, you make constant payments P at the end of each payment period.These accrue interest at the rate of r per payment period. Let An be the amount at theend of the nth payment period. Then rAn +An +P = (1+ r)An +P = An+1 and theinitial amount is 0 = A0,P = A1. Find An. Hint: Look for An =Czn + s. A0 = 0 so
18. A well known puzzle consists of three pegs and several disks each of a differentdiameter, each having a hole in the center which allows it to be slid down each ofthe pegs. These disks are piled one on top of the other on one of the pegs, in orderof decreasing diameter, the larger disks always being below the smaller disks. Theproblem is to move the whole pile of disks to another peg such that you never placea disk on a smaller disk. If you have n disks, how many moves will it take? Ofcourse this depends on n. If n = 1, you can do it in one move. If n = 2, you wouldneed 3. Let An be the number required for n disks. Then in solving the puzzle,you must first obtain the top n− 1 disks arranged in order on another peg beforeyou can move the bottom disk of the original pile. This takes An−1 moves. Explainwhy An = 2An−1 + 1,A1 = 1 and give a formula for An. Look for one in the formAn = Crn + s. This puzzle is called the Tower of Hanoi. When you have found aformula for An, explain why it is not possible to do this puzzle if n is very large.
3.3 The Limit of a SequenceA little later, the limit of functions of real variables will be important. A sequence is just aspecial kind of function and it turns out that it is easier to consider the limit of a sequence.This also helps considerably in understanding certain other concepts like continuity of afunction also presented later. This is why I am including this topic early in the book, tomake more difficult concepts easier to understand.
The concept of the limit of a sequence was defined precisely by Bolzano.1 It is nowexpressed as follows.
1Bernhard Bolzano lived from 1781 to 1848. He had an Italian father but was born in Bohemia, and he wrotein German. He was a Catholic priest and held a position in philosophy at the University of Prague. It appears thatBolzano believed in the words of Jesus and did not hesitate to enthusiastically promote what he knew was right.This got him in trouble with the political establishment of Austria. When he refused to recant, he was forced outof the university and forbidden to publish. He also displeased the Catholic hierarchy for being too rational.
Bolzano believed in absolute rigor in mathematics. He also was interested in physics, theology, and especiallyphilosophy. His contributions in philosophy are very influential. He originated anti-psychologism also calledlogical objectivism which holds that logical truth exists independent of our opinions about it, contrary to thenotion that truth for one person may not be truth for another. His collected writings fill some 25 volumes.