Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
A student wants to prove that
for every . Her first attempt fails: from "the sum up to is less than " she cannot show the same for .
The stronger claim is the key: it carries enough room from one step to the next.
Check an answer or open a hint to unlock the worked solution.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Step 1. Part (a). Adding a positive term to a number that is below can push it past , so the hypothesis gives no room for the new term.
Step 2. Base case of (b). For : the sum is and . So "at most" holds.
Step 3. What the step needs. Assume the sum up to is at most . Adding , we need
Step 4. Check it. Multiply both sides by : we need . That is true for every .
Step 5. Conclusion. By induction, the sum up to is at most for every .
Step 6. Part (c). The bound is . The sum is about , well below it.
Answer: the bound for is and the sum is about .
Log in to join the discussion.
Loading…
An inequality may hold only from some on: check , then in the step use . Bernoulli: for . If the step fails, try to prove a stronger statement.