We will use the mathematical induction to answer b). So, let’s start with the definition of the principle of mathematical induction.
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.
a) Find a formula for 1/2 + 1/4 + 1/8 + … + 1/2n by examining the values of this expression for small values of n
n=1, 1/2 =1/2
n=2, 1/2 + 1/4 = 3/4
n=3, 1/2 + 1/4 + 1/8= 7/8
n=4, 1/2 + 1/4 + 1/8 + 1/16= 15/16
The general formula is:
1/2 + 1/4 + 1/8 + … + 1/2n = (2n-1)/2n
b) Prove the formula you conjectured in part (a)
Notice that the first term is 1/2 and the general term is 1/2n. Therefore, n takes values strictly greater than 0. So, the basis step is to prove that P(1) is true.
Basis step:
P(1): 1/2= (21-1)/21=1/2
Inductive step:
P(k): 1/2 + 1/4 + 1/8 + … + 1/2k = (2k-1)/2k
Now, let’s prove that P(k)->P(k+1).
P(k+1): 1/2 + 1/4 + 1/8 + … + 1/2k + 1/2k+1 = (2k+1-1)/2k+1, substituting P(k) in P(k+1) we get,
P(k+1): (2k-1)/2k + 1/2k+1
=[2(2k-1) + 1]/2k+1
=[2×2k-2 + 1]/2k+1, because axan=an+1 we get,
=[2k+1-1]/2k+1
⧠
This completes the two steps of a proof following the principle of mathematical induction.
Related exercises:
- Prove that 3+3 · 5+3 · 52+···+3 · 5^n=3(5^(n+1)−1)/4 whenever n is a nonnegative integer
- 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