ABSTRACT
This chapter aims to introduce the powerful proof technique known as mathematical induction. Since induction is used to prove statements that are indexed by the integers, sequences are discussed first. The chapter introduces recursion and explores sequences expressed recursively. Sigma notation provides an efficient and clear way to represent long sums. Since sigma notation represents summation, it has some formal properties that are immediate consequences of the associative and distributive properties of addition. The chapter shows the power of mathematical induction for proving statements of the form ∀ integers n = a, P(n). However, there are also many such examples whose proofs are more naturally done by a stronger form of induction. The difference between regular induction and strong induction is in their inductive steps and, more specifically, in their inductive hypotheses. The chapter discusses some important theorems in number theory, highlighted by the Fundamental Theorem of Arithmetic and presents the Binomial Theorem.
