Practice question · Put in order
Order the parts of a proof by induction that the sum of the first n positive integers equals n(n+1)/2.
- Assume as the inductive hypothesis that the formula holds for n = k
- Conclude that the formula holds for k + 1, and hence for every n at least 1
- Check the base case: for n = 1 the sum is 1 and the formula gives 1
- Consider the sum for n = k + 1, which is the sum for k plus the extra term k + 1
- Substitute the assumed formula for the sum up to k and simplify
Hints
- The chain has to be started before it can be extended, so one part comes first no matter how obvious it looks.
- The inductive hypothesis must be stated before the step can use it, and used before the conclusion can be drawn.
Show the answer
- Check the base case: for n = 1 the sum is 1 and the formula gives 1
- Assume as the inductive hypothesis that the formula holds for n = k
- Consider the sum for n = k + 1, which is the sum for k plus the extra term k + 1
- Substitute the assumed formula for the sum up to k and simplify
- Conclude that the formula holds for k + 1, and hence for every n at least 1
Why
The base case knocks over the first domino and the step shows each domino knocks the next. The order matters logically, not just presentationally: the step is only meaningful once there is something to assume, and the general conclusion only follows once both parts are in place.
Practise Mathematical Induction
The app has 8 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.