Proving $(1+x)^n\ge nx$ is easier by just proving $(1+x)^n\ge nx+1$. Exercise: explain this paradox

Question

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.

Answer 1

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).

Answer 2

This is a general phenomenon in inequalities, many times you need some intermediate steps. I think that this happens in general because certain expressions are easier to compare with one another, than others.

In your example:

$$ (1+x)^n , 1 + nx $$

are easier to compare than $(1+x)^n$, $nx$. " easier of course is very subjective, but an elementary example that should help make sense of the point is the following

Q. Which number is larger:

$31^{11}$ or $17^{14}$ ?

This at first seems ridiculous to compare by hand, but actually:

$$ 31^{11} < 32^{11} =(2^{5})^{11} < 2^{56} = (2^{4})^{14} = 16^{14} < 17^{14} $$

in proving that $31^{11}$ is larger than $17^{14}$ you do prove a series of "sharper" inequalities, but each one seems reasonable as you are just using powers of 2.

By a generalization argument your "paradox" can be explained that what is stronger can be easier for us to prove, because we can use our intuition better.

Answer 3

If you wish to prove a proposition $P$ by induction, where $P$ is a proposition of the form $P = \bigwedge_{n \in \mathbb N} P(n)$ (that is, for each positive integer $n$, $P(n)$ is a proposition, and $P$ is the proposition that all of these propositions are true) then the principle of induction asserts that the propositions $P(1)$ and $[P(n)\implies P(n+1)]$ together imply $P$.

Now if $P_1 = \bigwedge_{n \in \mathbb N} P_1(n)$ is another such proposition, and $P_1(n) \implies P(n)$ then one can establish $P$ by showing either the implications $a_n$ holds for all $n$, or the implications $b_n$ holds for all $n$: $$ \require{AMScd} \begin{CD} P_1(n) @>{}>> P(n) \\ @V{a_n}VV @VV{b_n}V\\ P_1(n+1) @>{}>> P(n+1) \end{CD} $$ where we are assuming the horizontal implications are known. But note that neither of $a_n$ or $b_n$ imply each other, so in particular there is no reason to believe $(a_n)$ is easier or harder to demonstrate than $(b_n)$ -- it assumes more, so the fact that its validity implies more does not indicate much.

For example, take $P_1(n)$ to be $P(n)\wedge P(n+1)$. Then $P_1(n)$ clearly implies $P(n)$, but showing $P_1(n)$ implies $P_1(n+1)$ requires showing $P(n)\wedge P(n+1)$ implies $P(n+1)\wedge P(n+2)$, or equivalently, $P(n)\wedge P(n+1)\implies P(n+2)$. Extending this line of thinking leads to the principle of "strong induction", that is, if $P(1)$ and $[\bigwedge_{1\leq k<n} P(k)\implies P(n)]$ are true, then $P$ is true. This is a very useful variant which is equivalent to ordinary induction, even though its "inductive assumption" $\bigwedge_{1\leq k <n} P(k)$ is apparently much stronger.