Mathematical Induction: A powerful and elegant method of proof

Foreword v
1 A Brief Overview of Induction 1
1.1 Theory and Examples ....................... 1
1.1.1 Introductory Notions .................... 1
1.1.2 Variants of Induction .................... 7
1.1.3 Paradox of Induction .................... 9
1.1.4 Well-Ordering and Transfinite Induction ......... 17
1.2 Proposed Problems ......................... 22
2 Sums, Products, and Identities 23
2.1 Theory and Examples ....................... 23
2.2 Proposed Problems ......................... 37
3 Functions and Functional Equations 39
3.1 Theory and Examples ....................... 39
3.2 Proposed Problems ......................... 54
4 Inequalities 57
4.1 Theory and Examples ....................... 57
4.2 Proposed Problems ......................... 71
5 Sequences and Recurrences 75
5.1 Theory and Examples ....................... 75
5.2 Proposed Problems ......................... 85
6 Number Theory 91
6.1 Theory and Examples ....................... 91
6.1.1 The p and [g] Technique ................. 94
6.1.2 Divisibility ......................... 97
6.1.3 Representations ....................... 104
6.2 Proposed Problems ......................... 111
7 Combinatorics 117
7.1 Theory and Examples ....................... 117
7.1.1 Partitions and Configurations ............... 117
7.1.2 Graph Theory ....................... 128
7.1.3 Combinatorial Geometry ................. 137
7.2 Proposed Problems ......................... 145
8 Games 155
8.1 Theory and Examples ....................... 155
8.2 Proposed Problems ......................... 163
9 Miscellaneous Topics 165
9.1 Geometry .............................. 165
9.1.1 Examples .......................... 165
9.1.2 Proposed Problems ..................... 174
9.2 Induction in Calculus ....................... 176
9.2.1 Examples .......................... 176
9.2.2 Proposed Problems ..................... 184
9.3 Induction in Algebra ........................ 186
9.3.1 Examples .......................... 186
9.3.2 Proposed Problems ..................... 191
10 Solutions 193
1 A Brief Overview of Induction ................... 193
2 Sums, Products, and Identities .................. 202
3 Functions and Functional Equations ............... 209
4 Inequalities ............................. 231
5 Sequences and Recurrences .................... 252
6 Number Theory ........................... 283
7 Combinatorics ........................... 326
8 Games ................................ 380
9 Miscellaneous Topics ........................ 391
9.1 Geometry .......................... 391
9.2 Induction in Calculus ................... 403
9.3 Induction in Algebra .................... 414
Notations and Abbreviations 425
Bibliography 427
Other Books from XYZ Press 429