A method for proving that proposition P(n) holds for every natural number n:
- Show that P(1) holds when n=1 (base case)
- Assume P(k) holds and show that P(k+1) holds (inductive step)
Once these two points are shown, P(n) holds for every n.
Example ① Prove that 1+2+…+n = n(n+1)/2 for every natural number n.
Solution:n=1: left side=1, right side=1·2/2=1. OK.
Assume it holds for n=k: 1+2+…+k = k(k+1)/2.
For n=k+1: left side = k(k+1)/2 + (k+1) = (k+1)(k+2)/2. This agrees with the right side.
Therefore, it holds for every n.
Solution:n=1: left side=1, right side=1·2/2=1. OK.
Assume it holds for n=k: 1+2+…+k = k(k+1)/2.
For n=k+1: left side = k(k+1)/2 + (k+1) = (k+1)(k+2)/2. This agrees with the right side.
Therefore, it holds for every n.
Key Point
- There are two stages: the base case and the inductive step
- The key is how the assumption is used
Practice Problems
- Prove by induction that 1+3+…+(2n−1)=n².
Solutions and Explanations
- Solution:n=1: 1=1. Assume n=k: 1+…+(2k−1)=k². For n=k+1: left side=k²+(2k+1)=(k+1)².