| Let P(n) be the claim: | n | 2j-1 | = |
2n - 1 | for all integers n 1. |
| S | |||||
| j = 1 | |||||
2c)
| Let P(n) be the claim: | n | 2j-1 | = |
2n - 1 | for all integers n1. |
| S | |||||
| j = 1 | |||||
| P(1) is the statement: | 1 | 2j-1 | = |
21 - 1. |
| S | ||||
| j = 1 | ||||
| P(k) is the statement: | k | 2j-1 | = |
2k - 1 |
| S | ||||
| j = 1 | ||||
| P(k+1) is the statement: | k + 1 | 2j-1 | = |
2k+1 - 1. |
| S | ||||
| j = 1 |
For a proof by induction, you first need to check that the statement P(1) is true. Then assume that P(k) is true and use this to show that P(k + 1) is true.
| The statement P(1) is true since | 1 | 2j-1 | = |
21-1 = 20 = 1 = 21 - 1. |
| S | ||||
| j = 1 |
Now assume that the statement P(k) is true. We now need to show that the left-hand side of P(k+1) is equal to the right-hand side of P(k+1).
| L.H.S of P(k+1) | = |
k + 1 | 2j-1 | ||
| S | |||||
| j = 1 | |||||
= |
k | 2j-1 | + |
2(k+1)-1 | |
| S | |||||
| j = 1 | |||||
| = | 2k - 1 + 2k (since we are assuming that P(k) is true) | ||||
| = | 2 · 2k - 1 | ||||
| = | 2k+1 - 1 | ||||
| = | R.H.S. of P(k+1) | ||||
| Therefore, for all integers n 1, |
n | 2j-1 | = |
2n - 1. |
| S | ||||
| j = 1 |