Chapter 6.3 in "How to prove it" by velleman has a theorem:
The last exercise of the chapter asks the reader to explain what the paradox was in the proof:
At first I thought it has something to do with the binomial theorem since the chapter had a lot of content about it and the inequality has the expression $(1+x)^n$, but now after googling for a proof of $(1+x)^n\ge nx+1$ it seems to be Bernoulli's inequality, so I guess that's the answer to the last exercise?
My second question is, what is the exercise actually asking for?
Definition of paradox:
a statement that is seemingly contradictory or opposed to
common sense and yet is perhaps true
So I guess the paradox here is something like:
"Proving $(1+x)^n\ge nx$ by induction is hard, but proving it by showing that $(1+x)^n\ge nx+1$ is easier." (1)
Using common sense reasoning, if you have a hard time proving $(1+x)^n$ is greater than $nx$, then of course you are also gonna have a hard time proving $(1+x)^n$ is greater than or equal to $nx+1$
So to explain this paradox, I guess I should explain why the statement (1) is actually true, even though it seems that it is false?
The answer to that question would just be explaining that $(1+x)^n\ge nx+1$ is a well known inequality that has been proved already, and the proof is fairly simple.
Best Answer
I think the answer they’re looking for is simply that for a proof by induction it’s good to have a very strong inductive hypothesis, so that “you have more to work with” in the intermediate step. If you only prove $(1+x)^n\geq nx$ then in the inductive step you can’t proceed further. Note all this says is that for the purposes of a proof by induction only, proving $(1+x)^n\geq 1+nx$ is easier. Of course, one can now make the argument that there is more to establish in the inductive step; so all I can say is there’s a balance one has to strike, and any failed attempts will hopefully lead you closer to that balance.
Anyway, as a heads up, sometimes it is the case (counterintuitively) that it is easier to prove a seemingly harder statement. For example the statement “there exist transcendental real numbers” is true and the way this is proved is by showing that “the cardinality of the set of transcendental numbers is larger than the cardinality of algebraic numbers”, but to actually give an example (and prove that the example you gave is actually transcendental) is pretty tough. For example, showing that $e$ or $\pi$ are transcendental (or even simply irrational) is pretty hard (or at the very least, not a trivial task).
There are many other such examples where for instance rather than showing existence of a single item, you prove the existence of a whole bunch of them, and at the end say “therefore the set of ___ is non-empty” (Baire’s category theorem provides many such examples).