Discussion Notes #5 for Math 232

Practicing Induction Proofs

6 March 2002

We've just seen how to use mathematical induction to prove statements of the form "FORALL n: P(n)" where n is a variable of type "number" (non-negative integer). Recall the general form of such a proof:

• Identify the exact statement P(n).
• Prove the base case P(0).
• Begin proving the inductive case FORALL n:[P(n) --> P(n+1)].
• Say "let n be an arbitrary number".
• Say "assume P(n) is true".
• Use the inductive hypothesis P(n) to prove P(n+1), making use of the similarities between the statements P(n) and P(n+1).
• Conclude "P(n) --> P(n+1)".
• Say "since n was arbitrary, we have proved FORALL n:[P(n) --> P(n+1)]".
• Say "by induction, we have proved FORALL n: P(n)".

Writing exercise: Here we have four examples of statements to be proved using mathematical induction. Write down a proof of each using the above format. Remember to avoid type errors: "P(n)" is a predicate and thus a boolean, while the terms in these statement will usually be numbers.

1. An arithmetic progression is a sequence beginning with a start term a₀ such that each term increases by an offset b. The terms are thus a₀, a₀+b, a₀+2b,..., a₀+ nb. Prove that for any number n, the sum of the n terms from a₀ through a₀+nb is (n+1)[a₀+a₀+nb]/2.
2. A geometric progression is a sequence beginning with a start term a₀ where each term is multiplied by a ratio r, so we have a₀, a₀r, a₀r²,..., a₀rⁿ. Prove that if r &ne 1, the sum of these terms from a₀ through a₀rⁿ is a₀(1-rⁿ⁺¹)/(1-r).
3. Prove that for any number n, 2ⁿ⁺⁴ is greater than (n+4)!.
4. Let the relation L(x,y) be defined on numbers as follows. L(x,0) is false for any number x, and L(x,y+1) is true iff either x=y or L(x,y). Using only this definition, prove "FORALL a: (a &ne 0) <--> L(0,a)" by induction on a.

Last modified 13 March 2002