Page 336 - Discrete Mathematics and Its Applications

5.1 Mathematical Induction 315

You can prove a conjecture once it is has been made (and is true). The bad thing about it is that it cannot
a theorem by be used to find new theorems. Mathematicians sometimes find proofs by mathematical in-
mathematical
duction unsatisfying because they do not provide insights as to why theorems are true. Many
induction
theorems can be proved in many ways, including by mathematical induction. Proofs of these the-
even if you do
not have the orems by methods other than mathematical induction are often preferred because of the insights
slightest idea they bring.
why it is true!

Examples of Proofs by Mathematical Induction

Many theorems assert that P (n) is true for all positive integers n, where P (n) is a propositional
function.Mathematicalinductionisatechniqueforprovingtheoremsofthiskind.Inotherwords,
mathematical induction can be used to prove statements of the form ∀n P (n), where the domain
is the set of positive integers. Mathematical induction can be used to prove an extremely wide
variety of theorems, each of which is a statement of this form. (Remember, many mathematical
assertions include an implicit universal quantifier. The statement “if n is a positive integer, then
3
n − n is divisible by 3” is an example of this. Making the implicit universal quantifier explicit
3
yields the statement “for every positive integer n, n − n is divisible by 3.)
We will use how theorems are proved using mathematical induction. The theorems we will
prove include summation formulae, inequalities, identities for combinations of sets, divisibility
results, theorems about algorithms, and some other creative results. In this section and in later
sections, we will employ mathematical induction to prove many other types of results, including
the correctness of computer programs and algorithms. Mathematical induction can be used to
prove a wide variety of theorems, not just summation formulae, inequalities, and other types of
examples we illustrate here. (For proofs by mathematical induction of many more interesting
and diverse results, see the Handbook of Mathematical Induction by David Gunderson [Gu11].
This book is part of the extensive CRC Series in Discrete Mathematics, many of which may be
of interest to readers. The author is the Series Editor of these books).
Note that there are many opportunities for errors in induction proofs. We will describe some
incorrect proofs by mathematical induction at the end of this section and in the exercises. To
avoid making errors in proofs by mathematical induction, try to follow the guidelines for such
proofs given at the end of this section.

SEEINGWHERETHEINDUCTIVEHYPOTHESISISUSED Tohelpthereaderunderstand
each of the mathematical induction proofs in this section, we will note where the inductive
IH
Look for the = symbol to hypothesis is used. We indicate this use in three different ways: by explicit mention in the text,
see where the inductive
by inserting the acronym IH (for inductive hypothesis) over an equals sign or a sign for an
hypothesis is used.
inequality, or by specifying the inductive hypothesis as the reason for a step in a multi-line
display.

PROVING SUMMATION FORMULAE We begin by using mathematical induction to prove
several summation formulae. As we will see, mathematical induction is particularly well suited
for proving that such formulae are valid. However, summation formulae can be proven in other
ways. This is not surprising because there are often different ways to prove a theorem. The major
disadvantage of using mathematical induction to prove a summation formula is that you cannot
use it to derive this formula. That is, you must already have the formula before you attempt to
prove it by mathematical induction.
Examples 1–4 illustrate how to use mathematical induction to prove summation formulae.
The first summation formula we will prove by mathematical induction, in Example 1, is a closed
formula for the sum of the smallest n positive integers.