Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
Let .
This is a classic example: the weaker claim cannot carry itself, but the stronger one can.
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). From we get . To reach we need . Squaring, , that is . This says , which is false. The step cannot be done.
Step 2. Base case of (b). and . Equal, so "at most" holds.
Step 3. The step. Assume . Then , and we need this to be at most . Squaring, we need . The left side is and the right side is . The right side is bigger by . So the step works, and by induction (b) holds for every .
Step 4. Part (c). , so .
Step 5. Part (d). , and .
Answer: , below the bound .
Log in to join the discussion.
Loading…
Split the problem so that a smaller copy appears: four quarter boards, one line fewer, one disc fewer. Count what one more piece adds. If the step fails, prove a stronger statement or induct on a different quantity.