C. Credits for Exercises

The exercises in this book have been drawn from many sources. The authors have tried to trace the origins of all the problems that have been published before, except in cases where the exercise is so elementary that its inventor would probably not think anything was being invented.

Many of the exercises come from examinations in Stanford’s Concrete Mathematics classes. The teaching assistants and instructors often devised new problems for those exams, so it is appropriate to list their names here:

Year	Instructor	Teaching Assistant(s)
1970	Don Knuth	Vaughan Pratt
1971	Don Knuth	Leo Guibas
1973	Don Knuth	Henson Graves, Louis Jouaillec
1974	Don Knuth	Scot Drysdale, Tom Porter
1975	Don Knuth	Mark Brown, Luis Trabb Pardo
1976	Andy Yao	Mark Brown, Lyle Ramshaw
1977	Andy Yao	Yossi Shiloach
1978	Frances Yao	Yossi Shiloach
1979	Ron Graham	Frank Liang, Chris Tong, Mark Haiman
1980	Andy Yao	Andrei Broder, Jim McGrath
1981	Ron Graham	Oren Patashnik
1982	Ernst Mayr	Joan Feigenbaum, Dave Helmbold
1983	Ernst Mayr	Anna Karlin
1984	Don Knuth	Oren Patashnik, Alex Schäffer
1985	Andrei Broder	Pang Chen, Stefan Sharkansky
1986	Don Knuth	Arif Merchant, Stefan Sharkansky

The TA sessions were invaluable, I mean really great.

Keep the same instructor and the same TAs next year.

Class notes very good and useful.

I never “got” Stirling numbers.

In addition, David Klarner (1971), Bob Sedgewick (1974), Leo Guibas (1975), and Lyle Ramshaw (1979) each contributed to the class by giving six or more guest lectures. Detailed lecture notes taken each year by the teaching assistants and edited by the instructors have served as the basis of this book.

1.1     Pólya [297, p. 120].

1.2     Scorer, Grundy, and Smith [322].

1.5     Venn [359].

1.6     Steiner [338]; Roberts [310].

1.8     Gauss [144].

1.9     Cauchy [53, note 2, theorem 17].

1.10   Atkinson [15].

1.11   Inspired by Wood [377].

1.14   Steiner [338]; Pólya [297, chapter 3]; Brother Alfred [42].

1.17   Dudeney [87, puzzle 1].

1.21   Ball [20] credits B. A. Swinden.

1.22   Based on an idea of Peter Shor.*

1.23   Bjorn Poonen.*

1.25   Frame, Stewart, and Dunkel [130].

2.2     Iverson [191, p. 11].

2.3     [207, exercise 1.2.3–2].

2.5     [207, exercise 1.2.3–25].

2.22   Binet [30, §4].

2.23   1982 final.

2.26   [207, exercise 1.2.3–26].

2.29   1979 midterm.

2.30   1973 midterm.

2.31   Stieltjes [342].

2.34   Riemann [309, §3].

2.35   Euler [106] gave a fallacious “proof” using divergent series.

2.36   Golomb [150]; Vardi [358].

2.37   Leo Moser.*

3.6     Ernst Mayr, 1982 homework.

3.8     Dirichlet [80].

3.9     Chace [54]; Fibonacci [122, pp. 77–83].

3.12   [207, exercise 1.2.4–48(a)].

3.13   Beatty [22]; Niven [281, theorem 3.7].

3.19   [207, exercise 1.2.4–34].

3.21   1975 midterm.

3.23   [207, exercise 1.2.4–41].

3.28   Brown [45].

3.30   Aho and Sloane [4].

3.31   Greitzer [165, problem 1972/3, solution 2].

3.32   [160].

3.33   1984 midterm.

3.34   1970 midterm.

3.35   1975 midterm.

3.36   1976 midterm.

3.37   1986 midterm; [215].

3.38   1974 midterm.

3.39   1971 midterm.

3.40   1980 midterm.

3.41   Klamkin [203, problem 1978/3].

3.42   Uspensky [355].

3.45   Aho and Sloane [4].

3.46   Graham and Pollak [162].

3.48   Håland and Knuth [170].

3.49   R. L. Graham and D. R. Hofstadter.*

3.52   Fraenkel [128].

3.53   S. K. Stein.*

4.4     [214, §526].

4.16   Sylvester [346].

4.19   [212, pp. 148–149].

4.20   Bertrand [27, p. 129]; Chebyshev [56]; Wright [379].

4.22   Brillhart [39]; Williams and Dubner [375]; Dubner [86].

4.23   Crowe [68].

4.24   Legendre [241, second edition, introduction].

4.26   [208, exercise 4.5.3–43].

4.31   Pascal [284].

4.36   Hardy and Wright [181, §14.5].

4.37   Aho and Sloane [4].

4.38   Lucas [257].

4.39   [159].

4.40   Stickelberger [340].

4.41   Legendre [241, §135]; Hardy and Wright [181, theorem 82].

4.42   [208, exercise 4.5.1–6].

4.44   [208, exercise 4.5.3–39].

4.45   [208, exercise 4.3.2–13].

4.47   Lehmer [242].

4.48   Gauss [142, §78]; Crelle [67].

4.52   1974 midterm.

4.53   1973 midterm, inspired by Rao [303].

4.54   1974 midterm.

4.56   Logan [252, eq. (6.15)].

4.57   A special case appears in [216].

4.58   Sierpiński [327].

4.59   Curtiss [70]; Erdős [93].

4.60   Mills [272].

4.61   [207, exercise 1.3.2–19].

4.63   Barlow [21]; Abel [1].

4.64   Peirce [287].

4.66   Ribenboim [308]; Sierpiński [328, problem P²₁₀].

4.67   [157].

4.69   Cramér [66].

4.70   Paul Erdős.*

4.71   [95, p. 96].

4.72   [95, p. 103].

4.73   Landau [239, volume 2, eq. 648].

5.1     Forcadel [126].

5.3     Long and Hoggatt [254].

5.5     1983 in-class final.

5.13   1975 midterm.

5.14   [207, exercise 1.2.6–20].

5.15   Dixon [81].

5.21   Euler [99].

5.25   Gauss [143, §7].

5.28   Euler [118].

5.29   Kummer [229, eq. 26.4].

5.31   Gosper [154].

5.34   Bailey [18, §10.4].

5.36   Kummer [230, p. 116].

5.37   Vandermonde [357].

5.38   [207, exercise 1.2.6–56].

5.40   Rødseth [311].

5.43   Pfaff [292]; [207, exercise 1.2.6–31].

5.48   Ranjan Roy.*

5.49   Roy [314, eq. 3.13].

5.53   Gauss [143]; Richard Askey.*

5.58   Frazer and McKellar [133].

5.59   Stanford Computer Science Comprehensive Exam, Winter 1987.

5.60   [207, exercise 1.2.6–41].

5.61   Lucas [258].

5.62   1971 midterm.

5.63   1974 midterm.

5.64   1980 midterm.

5.65   1983 midterm.

5.66   1984 midterm.

5.67   1976 midterm.

5.68   1985 midterm.

5.69   Lyle Ramshaw, guest lecture in 1986.

5.70   Andrews [9, theorem 5.4].

5.71   Wilf [373, exercise 4.16].

5.72   Hermite [185].

5.74   1979 midterm.

5.75   1971 midterm.

5.76   [207, exercise 1.2.6–59 (corrected)].

5.77   1986 midterm.

5.78   [210].

5.79   Mendelsohn [268]; Montgomery [276].

5.81   1986 final exam; [219].

5.82   Hillman and Hoggatt [188].

5.85   Hsu [190].

5.86   Good [153].

5.88   Hermite [186].

5.91   Whipple [369].

5.92   Clausen [60], [61].

5.93   Gosper [154].

5.95   Petkovšek [291, Corollary 3.1].

5.96   Petkovšek [291, Corollary 5.1].

5.98   Ira Gessel.*

5.100 Staver [336′].

5.102 H. S. Wilf.*

5.104 Volker Strehl.*

5.105 Henrici [183, p. 118].

5.108 Apéry [14].

5.109 Gessel [146].

5.110 R. William Gosper, Jr.*

5.111 [95, p. 71].

5.112 [95, p. 71].

5.113 Wilf and Zeilberger [374].

5.114 Strehl [344] credits A. Schmidt.

6.6     Fibonacci [122, p. 283].

6.15   [209, exercise 5.1.3–2].

6.21   Theisinger [350].

6.25   Gardner [138] credits Denys Wilquin.

6.27   Lucas [257].

6.28   Lucas [259, chapter 18].

6.31   Lah [235]; R. W. Floyd.*

6.35   1977 midterm.

6.37   Shallit [324].

6.39   [207, exercise 1.2.7–15].

6.40   Klamkin [203, problem 1979/1].

6.41   1973 midterm.

6.43   Brooke and Wall [41].

6.44   Wasteels [361′].

6.46   Francesca [131]; Wallis [360, chapter 4].

6.47   Lucas [257].

6.48   [208, exercise 4.5.3–9(c)].

6.49   Davison [73].

6.50   1985 midterm; Rham [307]; Dijkstra [79, pp. 230–232].

6.51   Waring [361]; Lagrange [233]; Wolstenholme [376].

6.52   Eswarathasan and Levine [97].

6.53   Kaucký [200] treats a special case.

6.54   Staudt [336]; Clausen [62]; Rado [300].

6.55   Andrews and Uchimura [13].

6.56   1986 midterm.

6.57   1984 midterm, suggested by R. W. Floyd.*

6.58   [207, exercise 1.2.8–30]; 1982 midterm.

6.59   Burr [47].

6.61   1976 final exam.

6.62   Borwein and Borwein [36, §3.7].

6.63   [207, section 1.2.10]; Stanley [335, proposition 1.3.12].

6.65   Tanny [349].

6.66   [209, exercise 5.1.3–3].

6.67   Chung and Graham [59].

6.68   Logan [253].

6.69   [209, exercise 6.1–13].

6.72   Euler [110, part 2, chapter 8].

6.73   Euler [108, chapters 9 and 10]; Schröter [321].

6.75   Atkinson [16].

6.76   [209, answer 5.1.3–3]; Lengyel [248].

6.78   Logan [253].

6.79   Comic section, Boston Herald, August 21, 1904.

6.80   Silverman and Dunn [329].

6.82   [217].

6.83   [156], modulo a numerical error.

6.85   Burr [47].

6.86   [226].

6.87   [208, exercises 4.5.3–2 and 3].

6.88   Adams and Davison [3].

6.90   Lehmer [243].

6.92   Part (a) is from Eswarathasan and Levine [97].

7.2     [207, exercise 1.2.9–1].

7.8     Zave [380].

7.9     [207, exercise 1.2.7–22].

7.11   1971 final exam.

7.12   [209, pp. 63–64].

7.13   Raney [302].

7.15   Bell [24].

7.16   Pólya [296, p. 149]; [207, exercise 2.3.4.4–1].

7.19   [221].

7.20   Jungen [198, p. 299] credits A. Hurwitz.

7.22   Pólya [298].

7.23   1983 homework.

7.24   Myers [279]; Sedláček [323].

7.25   [208, Carlitz’s proof of lemma 3.3.3B].

7.26   [207, exercise 1.2.8–12].

7.32   [95, pp. 25–26] credits L. Mirsky and M. Newman.

7.33   1971 final exam.

7.34   Tomás Feder.*

7.36   1974 final exam.

7.37   Euler [109, §50]; 1971 final exam.

7.38   Carlitz [49].

7.39   [207, exercise 1.2.9–18].

7.41   André [8]; [209, exercise 5.1.4–22].

7.42   1974 final exam.

7.44   Gross [166]; [209, exercise 5.3.1–3].

7.45   de Bruijn [75].

7.47   Waugh and Maxfield [363].

7.48   1984 final exam.

7.49   Waterhouse [362].

7.50   Schröder [320]; [207, exercise 2.3.4.4–31].

7.51   Fisher [124]; Percus [290, pp. 89–123]; Stanley [334].

7.52   Hammersley [177].

7.53   Euler [114, part 2, section 2, chapter 6, §91].

7.54   Moessner [274].

7.55   Stanley [333].

7.56   Euler [113].

7.57   [95, p. 48] credits P. Erdős and P. Turán.

8.13   Thomas M. Cover.*

8.15   [207, exercise 1.2.10–17].

8.17   Patil [286].

8.24   John Knuth (age 4) and DEK; 1975 final.

8.26   [207, exercise 1.3.3–18].

8.27   Fisher [125].

8.29   Guibas and Odlyzko [168].

8.32   1977 final exam.

8.34   Hardy [180] has an incorrect analysis leading to the opposite conclusion.

8.35   1981 final exam.

8.36   Gardner [139] credits George Sicherman.

8.38   [208, exercise 3.3.2–10].

8.39   [211, exercise 4.3(a)].

8.41   Feller [120, exercise IX.33].

8.43   [207, sections 1.2.10 and 1.3.3].

8.44   1984 final exam.

8.45   1985 final exam.

8.46   Feller [120] credits Hugo Steinhaus.

8.47   1974 final, suggested by “fringe analysis” of 2-3 trees.

8.48   1979 final exam.

8.49   Blom [32]; 1984 final exam.

8.50   1986 final exam.

8.51   1986 final exam.

8.53   Feller [120] credits S. N. Bernstein.

8.57   Lyle Ramshaw.*

8.58   Guibas and Odlyzko [168].

9.1     Hardy [179, 1.3(g)].

9.2     Part (c) is from Garfunkel [140].

9.3     [207, exercise 1.2.11.1–6].

9.6     [207, exercise 1.2.11.1–3].

9.8     Hardy [179, 1.2(iv)].

9.9     Landau [238, vol. 1, p. 60].

9.14   [207, exercise 1.2.11.3–6].

9.16   Knopp [205, edition ≥ 2, §64C].

9.18   Bender [25, §3.1].

9.20   1971 final exam.

9.24   [164, §4.1.6].

9.27   Titchmarsh [352].

9.28   Glaisher [149].

9.29   de Bruijn [74, §3.7].

9.32   1976 final exam.

9.34   1973 final exam.

9.35   1975 final exam.

9.36   1980 class notes.

9.37   [208, eq. 4.5.3–21].

9.38   1977 final exam.

9.39   1975 final exam, inspired by Reich [306].

9.40   1977 final exam.

9.41   1980 final exam.

9.42   1979 final exam.

9.44   Tricomi and Erdélyi [353].

9.46   de Bruijn [74, §6.3].

9.47   1980 homework; [209, eq. 5.3.1–34].

9.48   1980 final exam.

9.49   1974 final exam.

9.50   1984 final exam.

9.51   [164, §4.2.1].

9.52   Poincaré [294]; Borel [35, p. 27].

9.53   Pólya/Szegő [299, part 1, prob. 140].

9.57   Andrew M. Odlyzko.*

9.58   Henrici [182, exercise 4.9.8].

9.60   [225].

9.62   Canfield [48].

9.63   Vardi [358].

9.65   Comtet [64, chapter 5, exercise 24].

9.66   M. P. Schützenberger.*

9.67   Lieb [250]; Stanley [335, exercise 4.37(c)].

9.68   Boas and Wrench [33].

* Unpublished personal communication.