PRINCIPLE OF MATHEMATICAL INDUCTION: “To prove that P(n) is true for all positive integers n, where P (n) is a propositional function, we complete two steps: BASIS STEP: We verify that P (1) is true. INDUCTIVE STEP: We show that the conditional statement P (k) → P (k + 1) is true for all positive integers k.” Source: Discrete Mathematics and its Applications by Rosen.
Let P(n) be 3+3×5+3×52+···+3×5n=3(5n+1−1)/4, for n≥0.
Basis step:
P(0): 3 = 3(50+1-1)/4=3×4/4=3
Inductive step:
P(k): 3+3×5+3×52+···+3×5k=3(5k+1−1)/4
Assuming that P(k) is true, we must prove that P(k+1) is also true. In other words, we must prove that P(k)->P(k+1).
P(k+1): 3+3×5+3×52+···+3×5k+3×5k+1=3(5k+2−1)/4, substituting P(k) in P(k+1) we get,
3(5k+1−1)/4 +3×5k+1=3(5k+2−1)/4
=3[5k+1+4×5k+1 -1]/4
=3[5×5k+1 -1]/4, using the property axan=an+1 we get,
=3[5k+2 -1]/4
⧠
Related exercises:
- a) Find a formula for 1/2 + 1/4 + 1/8 + … + 1/2^n by examining the values of this expression for small values of n. b) Prove the formula you conjectured in part (a).
- Let P(n) be the statement that 1^2 +2^2 +···+n^2 = n(n + 1)(2n + 1)/6 for the positive integer n.
- There are infinitely many stations on a train route. Suppose that the train stops at the first station and suppose that if the train stops at a station, then it stops at the next station. Show that the train stops at all stations