SUNY Geneseo Department of Mathematics
Wednesday, March 13
Math 239 01
Spring 2019
Prof. Doug Baldwin
Mostly section 4.1.
Suppose f(n) is defined for all natural numbers by f(1) = 2; f(n) = 2 + f(n-1) if n > 1.
Prove that f(n) = 2n.
Proof idea: do it by induction on n
Basis step: n = 1, f(1) = 2 from definition, 2 = 2 × 1
Induction: if f(k) = 2k for some natural k ≥ 1, then f(k+1) = 2(k+1). Assume f(k) = 2k, then f(k+1) = 2+ f(k) = 2 + 2k = 2(k+1).
The above highlights the important ideas in the proof, e.g., some variable that you do the induction on, i.e., that takes on value 1 in the basis step and k and k+1 in the induction step; the distinct basis and induction steps; careful attention to k being at least equal to (and possibly greater than) the basis step value when setting up the assumptions for the induction step.
For a formal version of the proof, see this PDF file, and its LaTeX source.
(Speaking of recurrence relations.)
F0 = 0, F1 = 1, Fn = Fn-1 + Fn-2 for n > 1
Prove that for all integers n ≥ 1, Fn ≤ 2n.
Basis step, n = 1. F1 = 1 ≤ 2 = 21.
Induction step, if Fk ≤ 2k then Fk+1 ≤ 2k+1 = 2 2k.
Fk+1 = Fk + Fk-1 ≤ 2 Fk (since Fk-1 ≤ Fk, so Fk + Fk-1 ≤ Fk + Fk); 2 Fk ≤ 2 2k.
...on induction.
See handout for details.
More about induction, especially strong induction.
Read section 4.2 if you haven’t already.