58 CHAPTER 4. FUNCTIONS AND SEQUENCES
the positive integers given recursively as just described and An is the amount at thebeginning of the nth payment period. Now if you wanted to find out An for large n,how would you do it? One way would be to use the recurrance relation n times. Abetter way would be to find a formula for An. Look for one in the form An =Czn + swhere C,z and s are to be determined. Show that C = P
r ,z = (1+ r) , and s =−Pr .
19. 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.
4.4 The Limit of a SequenceThe concept of the limit of a sequence was defined precisely by Bolzano.3 The followingis the precise definition of what is meant by the limit of a sequence. Our sequences willhave values in Fp ≡
{(x = (x1, · · · ,xp)) : xi ∈ F
}.
Definition 4.4.1 A sequence {an}∞
n=1 converges to a, written as
limn→∞
an = a or an→ a
if and only if for every ε > 0 there exists nε such that whenever n≥ nε , ∥an−a∥< ε . Herea and an are assumed to be in Fp for some integer p≥ 1. Thus an is in the Cartesian product
3Bernhard 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 appearsthat Bolzano believed in the words of Jesus and did not hesitate to enthusiastically promote them. This got him introuble with the political establishment of Austria who forced him out of the university and did not allow him topublish. 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 can in any way depend on our feelings. This is the right way to regard truth in mathematics.
The intermediate value theorem from calculus is due to him. These days, this theorem is considered obviousand is not discussed well in calculus texts, but Bolzano knew better and gave a proof which identified exactlywhat was needed instead of relying on vague intuition.
Like many of the other mathematicians, he was concerned with the notion of infinitesimals which had beenpopularized by Leibniz. Some tried to strengthen this idea and others sought to get rid of it. They realizedthat something needed to be done about this fuzzy idea. Bolzano was one who contributed to removing it fromcalculus. He also proved the extreme value theorem in 1830’s and gave the first formal εδ description of continuityand limits.
This notion of infinitesimals did not completely vanish. These days, it is called non standard analysis. It can bemade mathematically respectable but not in this book.