# ELEMENTARY REFERENCES FOR MATHEMATICAL INDUCTION

*From*: "Dave L. Renfro" <renfr1dl@xxxxxxxxx>*Date*: 15 Jan 2007 13:17:39 -0800

A discussion of mathematical induction came up in another

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.

.

**Follow-Ups**:**Re: ELEMENTARY REFERENCES FOR MATHEMATICAL INDUCTION***From:*Dave L. Renfro

- Prev by Date:
**Re: FLT - new thread** - Next by Date:
**Re: Representation of partially ordered sets** - Previous by thread:
**continuity f+g** - Next by thread:
**Re: ELEMENTARY REFERENCES FOR MATHEMATICAL INDUCTION** - Index(es):