Prove that for every positive integer
Solution
Let .
We will prove by induction on that for all positive integers .
Base case ():
.
Inductive step:
Assume .
Consider .
We want to show:
It suffices to show that .
Subtract from both sides:
But by the induction hypothesis, .
So it is enough to show:
which is equivalent to , which is true for all .
Therefore, by induction, for all positive integers .
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.