ELEMENTARY REFERENCES FOR MATHEMATICAL INDUCTION
Dave L. Renfro
math list that I participate in, and it occurred to me
that it would be a good idea to archive (in sci.math)
a list of some elementary references for mathematical
induction that I've had in a LaTex document for several
years.
Dave L. Renfro
[1] Fabio Acerbi, "Plato: Parmenides 149a7-c3. A proof by
complete induction?", Archive for History of Exact
Sciences 55 (2000), 57-76.
(from pp. 57-58) It is a generally accepted opinion
that the first instance of _conscious_use_ of Complete
Induction (henceforth CI) as a proof method is contained
in the "Traité du triangle arithmétique" by Blaise PASCAL
(1623-1662) [...] A very different question is to establish
whether, before PASCAL, convincing examples of _use_ of CI
as a proof technique are attested, disconnected from the
perception of the fact that it happened to be a particular
instance of a general demonstrative scheme. Scholars have
found proofs fitting in the scheme of CI in almost every
geographical ambit of pre-Pascalian mathematics. Some of
these proposals, especially those concerning the ancient
mathematical corpus, are untenable, even surprising in
view of the serious misunderstandings they contain. Recently,
the polemical tone of the debate has attained a local
maximum: in FOWLER 1994 _versus_ UNGURU 1994 preconceptions
of historiographical method have strongly influenced the
evaluation of the relevant instance of CI. In this sense,
both FOWLER's and UNGURU's analyses, though interesting in
several respects, seem to me to have missed their target.
Moreover, a careful survey of the literature shows that
every single scholar sets up his own reading of the principle
of CI, and on this basis he is able to affirm or to deny that
specific proofs constitute well formed examples of it. My
aim is to increase the confusion on this subject. In fact,
I suggest to regard a PLATONIC passage, i.e. "Parmenides"
149a7-c3, as a full-fledged example of proof by CI.
See Fowler (1994), Rabinovitch (1970),
and Unguru (1991, 1994).
[2] R. G. Albert, "A paradox relating to mathematical
induction", American Mathematical Monthly 57 #1
(January 1950), 31-32.
Reprinted on p. 164 of Tom M. Apostol, Gulbank D.
Chakerian, Geraldine C. Darden, and John D. Neff (editors),
SELECTED PAPERS ON PRECALCULUS, The Raymond W. Brink
Selected Mathematical Papers #1, Mathematical Association
of America, 1977.
[3] Keith Austin, "A paradox -- (2) Four weighings suffice",
Mathematical Gazette 72 #460 (June 1988), 113.
A more concise version was reprinted in College Mathematics
Journal 22 #2 (March 1991), p. 133.
[4] Arthur L. Baker, "Mathematical induction", American
Mathematical Monthly 7 #2 (February 1900), 35-37.
[5] John Baylis and Rod Haggarty, "Alice in inductionland",
Mathematical Gazette 72 #460 (June 1988), 108-112.
[6] James W. Beach, "Aids in understanding proof by mathematical
induction", Mathematics Teacher 56 #4 (April 1963), 236-237.
[7] Eric Temple Bell, "On proofs by mathematical induction",
American Mathematical Monthly 27 #11 (November 1920),
413-415.
See also the comments on pp. 407-408 in the same volume.
Bell's comments and the pp. 407-408 comments are reprinted
on pp. 159-163 of Tom M. Apostol, Gulbank D. Chakerian,
Geraldine C. Darden, and John D. Neff (editors), SELECTED
PAPERS ON PRECALCULUS, The Raymond W. Brink Selected
Mathematical Papers #1, Mathematical Association of
America, 1977.
[8] David M. Berman, "An inductive proof that no permutation
is both even and odd", Mathematical Gazette 62 #421
(October 1978), 211-212.
[9] Albert A. Blank, "Mathematical induction", pp. 118-140
in ENRICHMENT MATHEMATICS FOR HIGH SCHOOL, 28'th Yearbook,
National Council of Teachers of Mathematics, 1963.
[10] Albert V. Boyd, "An example on mathematical induction",
Mathematical Gazette 45 #353 (October 1961), 248-249.
[11] Robert Creighton Buck, "Mathematical induction and
recursive definitions", American Mathematical Monthly
70 #2 (February 1963), 128-135.
Reprinted on pp. 165-172 of Tom M. Apostol, Gulbank D.
Chakerian, Geraldine C. Darden, and John D. Neff (editors),
SELECTED PAPERS ON PRECALCULUS, The Raymond W. Brink
Selected Mathematical Papers #1, Mathematical Association
of America, 1977.
[12] Charles Brumfiel, "A note on mathematical induction",
Mathematics Teacher 67 #7 (November 1974), 616-618.
[13] Charles M. Bundrick and David L. Sherry, "A note on the
principle of mathematical induction", (Two-Year) College
Mathematics Journal 9 #1 (January 1978), 17-18.
[14] William Henry Bussey, "The origin of mathematical
induction", American Mathematical Monthly 24 #5
(May 1917), 199-207.
[15] William Henry Bussey, "Fermat's method of infinite
descent", American Mathematical Monthly 25 #8
(October 1918), 333-337.
[16] Florian Cajori, "Origin of the name "mathematical
induction"", American Mathematical Monthly 25 #5
(May 1918), 197-201.
[17] June Conklin, "Mathematical induction -- indirectly",
Mathematics Teacher 66 #1 (January 1973), 85-86.
[18] Mary Coughlin and Carolyn Kerwin, "Mathematical Induction
and Pascal's problem of the points", Mathematics Teacher
78 #5 (May 1985), 376-380.
[19] Francois Dubeau, "Cauchy and mathematical induction",
International Journal of Mathematical Education in
Science and Technology 22 (1991), 965-969.
[20] Andrejs Dunkels, "Complete induction unintentionally",
International Journal of Mathematical Education in
Science and Technology 14 (1983), 251-254.
[21] William Eames, "An inductive proof of Cauchy's inequality",
Mathematical Gazette 48 #363 (February 1964), 83-84.
[22] Theodore Eisenberg and Francis Lowenthal, "Mathematical
induction in school: an illusion of rigor?", School
Science and Mathematics 92 #5 (May/June 1992), 233-238.
[23] Paul Ernest, "Mathematical induction: A recurring theme",
Mathematical Gazette 66 #436 (June 1982), 120-125.
[24] David Fowler, "Could the Greeks have used mathematical
induction? Did they use it? Critical remarks on an article
by S. Unguru: "Greek mathematics and mathematical
induction"", Physis--Rivista Internazionale di Storia
della Scienza (N.S.) 31 (1994), 253-265.
(From p. 254) For Unguru, the symbolic form of [mathematical
induction] is an essential feature of its use. This allows
him to fit it in his general approach which starts, on the
one hand, from his uncontentious observation that there is
no sign of such symbolic manipulation in Greek mathematics,
and, on the other, from his attitude to modern mathematics
which can be encapsulated in his assertion: <<Modern number
_it_ a symbol>> (p. 282). Given such an approach, Unguru
has no difficulty in establishing that it would be
impossible for the Greeks to have employed _his_kind_ of
mathematical induction [...] I prefer a less formal approach
to mathematical induction, which I will characterise here
by a loose translation from the French of Pascal's own
description [...]
See Acerbi (2000), Rabinovitch (1970),
and Unguru (1991, 1994).
[25] Bernard Friedman, "Teaching mathematical induction",
School Science and Mathematics 41 #3 (March 1941),
279-280.
[26] Raymond Garver, "Mathematical induction", Mathematics
Teacher 26 #2 (February 1933), 65-69.
[27] Merton Taylor Goodrich, "Teaching mathematical induction",
School Science and Mathematics 40 #5 (May 1940), 472-476.
See the criticism by William Charles Krathwohl
(SS & M 41 #1, January 1941, p. 101) and the replies
by Goodrich (SS & M 41 #1, January 1941, p. 101)
and Friedman (above).
[28] Jay Graening, "Induction: Fallible but valuable",
Mathematics Teacher 64 #2 (February 1971), 127-131.
[29] Shay Gueron, "Yet another refreshing induction fallacy
(part one)", Fallacies, Flaws, and Flimflam column,
College Mathematics Journal 31 #2 (March 2000), 120-123.
[30] Shay Gueron, "Yet another refreshing induction fallacy
(part two)", Fallacies, Flaws, and Flimflam column,
College Mathematics Journal 31 #3 (May 2000), 205-207.
[31] James C. Gussett, "Let's make Francesco Maurolico a
household word", School Science and Mathematics 86 #2
(February 1986), 144-148.
[32] Rodney T. Hansen and Leonard G. Swanson, "The equivalence
of the multiplication, pigeonhole, induction, and well
ordering principles", International Journal of Mathematical
Education in Science and Technology 19 (1988), 129-131.
[33] Glenn F. Hewitt, "Mathematical induction in high school
trigonometry", School Science and Mathematics 41 #7
(October 1941), 657-659.
[34] Christian R. Hirsch, "Making mathematical induction
meaningful", School Science and Mathematics 76 #1
(January 1976), 27-31.
[35] Roger Sherman Hoar, "On proofs by mathematical induction",
American Mathematical Monthly 29 #4 (April 1922), 162.
See also "Remarks by the Editor" that follow on
pp. 163-164 in the same volume.
[36] Paul B. Johnson, "Mathematical induction, SUM i^p and
factorial powers", Mathematics Teacher 53 #5 (May 1960),
332-334.
[37] P. D. Johnson and Martin Schlam, "Yet another perplexing
proof by induction", Fallacies, Flaws, and Flimflam #119,
College Mathematics Journal 28 #4 (September 1997),
285-286.
[38] Carol Lynn Kiaer, "Fostering an appreciation of
mathematical induction", Primus 5 #3 (September 1995),
218-228.
[39] Victor L. Klee, "A remark on mathematical induction",
Mathematics Magazine 22 (1948), 52.
Reprinted on p. 173 of Tom M. Apostol, Gulbank D.
Chakerian, Geraldine C. Darden, and John D. Neff (editors),
SELECTED PAPERS ON PRECALCULUS, The Raymond W. Brink
Selected Mathematical Papers #1, Mathematical Association
of America, 1977.
[40] Alex Kuperman, "All powers of x are constant", Fallacies,
Flaws, and Flimflam #45, College Mathematics Journal
22 #5 (November 1991), 403.
[41] Leo Macarow, "Mathematical induction", School Science
and Mathematics 72 #7 (October 1972), 647-648.
[42] Paul S. Malcom, "The well-ordering property as an
alternative to mathematical induction", School Science
and Mathematics 74 #4 (April 1974), 277-279.
[43] Roger H. Marty, "Natural numbers, order and mathematical
induction", International Journal of Mathematical Education
in Science and Technology 21 (1990), 623-627.
[44] Stephen B. Maurer, "Induction: down and back, not up",
Mathematics and Computer Education 28 #2 (Spring 1994),
122-131.
[45] Nitsa Movshovitz-Hadar, "Mathematical induction: A focus
on the conceptual framework", School Science and Mathematics
93 #8 (December 1993), 408-417.
[46] Robert Franklin Muirhead, "Notes on mathematical induction",
Proceedings of the Edinburgh Mathematical Society (1) 31
(1913), 47-53.
[47] John O. Parker, "A proof of the remainder theorem",
Mathematics Teacher 66 #2 (February 1973), 142.
A proof by mathematical induction (on the degree of
the polynomial) that, when a polynomial p(x) is divided
by x - b, the remainder is p(b).
[48] Aron Pinker, "Induction and well ordering", School Science
and Mathematics 76 #3 (March 1976), 207-214.
[49] Nachum L. Rabinovitch, "Rabbi Levi ben Gershon and the
origins of mathematical induction", Archive for History
of Exact Sciences 6 (1970), 237-248.
(From pp. 237-238) The name _mathematical_induction_ is
apparently due to DE MORGAN (1838) [Cajori above is
footnoted]. As for the use of recursion in formal proofs,
BLAISE PASCAL (1623-1662) has been credited with the
invention of this technique. Thus FLORIAN CAJORI [review
in Bull. Amer. Math. Soc. 15 (1908-09), 405-408], although
he found evidence for "recurrent processes" in CAMPANUS
(1260) and even earlier in PROCLUS (410-485), concluded
that these are "not exactly induction which is best ascribed
to Pascal". However, shortly thereafter, G. VACCA [see Vacca,
below] claimed the discovery of the principle of mathematical
induction for FRANCESCO MAUROLICO (1494-1575), and this
view remained unchallenged until recently when the entire
subject was examined anew by Professor HANS FREUDENTHAL
[MR 14,1049h; Zbl 50.24202]. He carefully reviewed
MAUROLICO'S work and found only two or at best three
instances of a very primitive kind of induction. [A footnote
mentions that Bussey (above) is more generous in his
evaluation of Maurolico.] Dr. FREUDENTHAL examines also
older sources and in passing, he refers to a report that
"Lewi ben Gerson (1288-1344) im Sefer Maasei Choscheb soll
die Anzahl n! der Permutationen von n Elementen mit Induktion
berechnet haben." However he does not investigate this
source, and concludes that PASCAL was indeed the first one
to formulate the Principle of Induction. Earlier authors
used proofs that were not really general, since they worked
with specific numbers. However, where the proof can readily
be applied to arbitrary n, FREUDENTHAL calls it
"quasi-general", but, while the use of such a proof can
properly be considered an application of mathematical
induction, its users can hardly be credited with the general
principle. A closer look at the work of R. LEVI BEN GERSHON,
in his _Maasei_Hoshev_, will show that he is in fact the
earliest writer known to have used induction systematically
in all generality and to have recognized it as a distinct
mathematical procedure.
See Acerbi (2000), Fowler (1994), and Unguru (1991, 1994).
[50] Taje I. Ramsamujh, "A paradox -- (1) All positive integers
are equal", Mathematical Gazette 72 #460 (June 1988), 113.
A more concise version was reprinted in College Mathematics
Journal 22 #2 (March 1991), p. 133. See also CMJ 23 #1
(January 1992), p. 38 (top).
[51] George Emil Raynor, "Mathematical induction", American
Mathematical Monthly 33 #7 (Aug./Sept. 1926), 376-377.
[52] Adrian Riskin and William Stein, "An inductive fallacy",
Fallacies, Flaws, and Flimflam #92, College Mathematics
Journal 26 #5 (November 1995), 382.
[53] Arthur Schach, "Two forms of mathematical induction",
Mathematics Magazine 32 #2 (Nov./Dec. 1958), 83-85.
[54] Allen J. Schwenk, "Every second square is the same",
Fallacies, Flaws, and Flimflam #94, College Mathematics
Journal 27 #1 (January 1996), 44.
[55] John C. Shepherdson, "Weak and strong induction", American
Mathematical Monthly 76 #9 (November 1969), 989-1004.
[56] Warren E. Shreve, "Teaching inductive proofs indirectly",
Mathematics Teacher 56 #8 (December 1963), 643-644.
[57] David L. Silverman, "A pseudo-induction", Journal of
Recreational Mathematics 4 #1 (January 1971), 74.
We will prove by mathematical induction that all positive
integers are odd, using only the obvious lemma that when
N is odd, N + 2 is also odd. Let P(N) denote the proposition
"All of the integers 1, 2, 3, ..., N are odd."
Step 1: P(1) obviously.
Step 2: Assume P(k). Then by definition 1, 2, 3, ..., k
are all odd. In particular k - 1 is odd. Then k - 1 + 2,
that is, k + 1 is also odd. Thus, 1, 2, 3, ... k, k + 1
are all odd, or P(k + 1). This completes the induction.
Where is the fallacy?
[58] E. T. W. Smyth, "Simultaneous discovery and proof in
mathematical induction", Mathematical Gazette 64 #429
(October 1980), 185-186.
[59] Iliya Samuilovich Sominskii [Sominski, Sominskij,
Sominsky], THE METHOD OF MATHEMATICAL INDUCTION, D. C.
Heath and Company, 1963, viii + 48 pages.
English translation by Luise Lange and Edgar E. Enochs
of the 5'th (1959) Russian edition.
[60] K. B. Subramaniam, "Mathematical induction", International
Journal of Mathematical Education in Science and Technology
12 (1981), 720-724.
[61] Hussein Tahir, "Pappus and mathematical induction",
Australian Mathematical Society Gazette 22 (1995),
166-167.
[62] Richard B. Thompson, "The special case may be the hardest
part", Mathematics Teacher 63 #3 (March 1970), 249-252.
[63] Sabetai Unguru, "Greek mathematics and mathematical
induction", Physis--Rivista Internazionale di Storia
della Scienza (N.S.) 28 (1991), 273-289.
(Author's Summary) The article examines the alleged
instances of mathematical induction in Greek mathematics
showing them to be actually noninductive. Furthermore
the author argues for the historical _impossibility_ of
the existence of genuine inductive proofs within the
confines of Greek mathematics. The article ends with
some general considerations on the nature of the history
of mathematics as a _historical_ discipline, meant to
set the specific analysis of the cited examples into
the broader methodological context of possible approaches
to the history of mathematics.
See also Acerbi (2000), Fowler (1994), Rabinovitch (1970),
and Unguru (1994).
[64] Sabetai Unguru, "Fowling after induction. Reply to
D. Fowler's comments: "Could the Greeks have used
mathematical induction? Did they use it?"",
Physis--Rivista Internazionale di Storia della
Scienza (N.S.) 31 (1994), 267-272.
(From p. 268) How can Fowler both agree with two of my
most substantive conclusions and yet disagree with my
article? By adopting a laxer interpretive viewpoint than
mine, a viewpoint, moreover, in which the guiding light
is mathematical, rather than contextual, narrow-historical,
intentional, voluntaristic, hermeneutical. To put it
bluntly, Fowler brings to the texts a willingness, which
I lack, to overinterpret them, a readiness to read into
the texts <<obvious>> mathematical implications which,
I think, are lacking and which he easily discerns with
his keen mathematical eye, as lying just below the surface
and bubbling up, bursting forth obtrusively, begging to
be acknowledged by the seer.
See also Acerbi (2000), Fowler (1994), Rabinovitch (1970),
and Unguru (1991).
[65] Giovanni Vacca, "'Maurolycus' the first discoverer of
the principle of mathematical induction, Bulletin of the
American Mathematical Society (2) 16 (1909-10), 70-73.
[66] Morgan Ward, "An interesting theorem", American Mathematical
Monthly 52 (1945), 540.
A "proof" by mathematical induction that all real numbers
are uninteresting.
[67] Albert Wilansky, "An induction fallacy", Mathematics
Magazine 39 (1966), 305.
[68] Margaret Wiscamb, "A geometric introduction to mathematical
induction", Mathematics Teacher 63 #5 (May 1970), 402-404.
[69] Douglas R. Woodall, "Inductio ad absurdum?", The
Mathematical Gazette 59 #408 (June 1975), 64-70.
[70] Adril Lindsay Wright, "Application of combinations and
mathematical induction to a geometry lesson", Mathematics
Teacher 56 #5 (May 1963), 325-328.
[71] John Wesley A. Young, "On mathematical induction", American
Mathematical Monthly 15 #8/9 (Aug./Sept. 1908), 145-153.
Reprinted on pp. 151-159 of Tom M. Apostol, Gulbank D.
Chakerian, Geraldine C. Darden, and John D. Neff (editors),
SELECTED PAPERS ON PRECALCULUS, The Raymond W. Brink
Selected Mathematical Papers #1, Mathematical Association
of America, 1977.
[72] Bevan K. Youse, MATHEMATICAL INDUCTION, Englewood Cliffs,
Prentice-Hall, 1964, 55 pages.
Dave L. Renfro
that I posted yesterday. In David Fowler's paper [24],
"<<Modern number _it_ a symbol>>" is corrected to "<<Modern
number _is_ a symbol>>". The correct phrase appears in my
LaTex document. Apparently, while removing/replacing the
LaTex code \textit{is}, which renders "is" in italicized
form, to a usenet version of italicization, namely "_is_",
I must have accidentally deleted the "s" at one point. Then,
a few seconds later, when I realized that I had deleted
one of the characters that shouldn't have been "backspaced
over", I must have retyped a "t" in its place by mistake.
Incidentally, I've doubled checked with the original papers,
and "is", as I now have it, appears in both Fowler's [24]
paper and in Unguru's [63] paper. (The phrase in question
was actually a phrase that Fowler was quoting from Unguru's
paper. Moreover, in both Fowler's rendering of the quote
and in the original version that was in Unguru's paper,
"is" is italicized. The double-arrow notation "<<...>>"
appears in the papers, by the way, and is not a form of
ASCII adjustment to the original text.)
Dave L. Renfro
_is_ a symbol>> (p. 282). Given such an approach, Unguru