# In the induction proof for $(1+p)^n \geq 1 + np$, a term is dropped and I don't understand why.

In What is Mathematics, pg. 15, a proof of

$(1+p)^n \geq 1 + np$, for $p>-1$ and positive integer $n$

goes as follows:

1. Substitute $r$ for $n$, then multiply both sides by $1+p$, obtaining: $(1+p)^{r+1}\geq 1+rp+p+rp^2$

2. "Dropping the positive term $rp^2$ only strengthens this inequality, so that $(1+p)^{r+1}\geq 1+rp+p$, which shows that the inequality will hold for $r+1$."

I don't understand why the $rp^2$ term can be dropped -- if we're trying to prove that the inequality holds, and dropping $rp^2$ strengthens the inequality, then why are we allowed to drop it?

Thanks!

-
We can see that $1+rp+p+rp^2 \geq 1+rp$ since $rp^2$ is positive thus dropping it in the original we still have that $(1+p)^{r+1}\geq 1+rp+rp^2 \geq 1+rp$ – Jeremy Dec 18 '12 at 9:50
$(1+p)^{r+1}\geq 1+rp+p+rp^2\ge 1+rp+p=1+(r+1)p$, since $rp^2>0$. – juniven Dec 18 '12 at 9:50

We know that $$(1+p)^{r+1}\ge 1+rp+p+rp^2\;.\tag{1}$$

We know that $rp^2\ge0$, which means that $$1+rp+p+rp^2\ge1+rp+p\;.\tag{2}$$

Put $(1)$ and $(2)$ together:

$$(1+p)^{r+1}\ge 1+rp+p+rp^2\ge1+rp+p\;.\tag{3}$$

And this is what we wanted to show: $(1+p)^{r+1}\ge1+(r+1)p$. The point is really just that if $(1)$ is true, then $(2)$ is certainly true, and since $(2)$ is what we want, we can ignore the fact that the stronger statement $(1)$ is also true.

-
ah, I get it now. Because we already know that the left hand statement is larger than the sum on the right, dropping one of the right hand terms makes it a stronger inequality. I was getting it backwards. Thanks! – Chris Gregg Dec 18 '12 at 9:56
@Chris: You’re understanding it right but using the word stronger incorrectly. The inequality $a>b$ is stronger than the inequality $a>c$ if $b>c$, because it says more: it’s harder for something to be bigger than $b$ than it is to be bigger than $c$. What you’re calling stronger is actually weaker in the standard terminology. You’re welcome! – Brian M. Scott Dec 18 '12 at 9:59
@Scott: got it. Interesting that the book says, "Dropping the positive term $rp^2$ only strengthens this inequality." Cheers! – Chris Gregg Dec 18 '12 at 10:10
Actually we only know $rp^2\geq 0$, since $p=0$ is within the allowed range, so the strict inequalities should be weak ones. – Marc van Leeuwen Dec 18 '12 at 10:14
@Marc: Thanks; fixed. – Brian M. Scott Dec 18 '12 at 10:19

One point I am missing in both the question and the other answers is the proper context: this is a proof by induction. That means that we assume the inequality for $n$, which is then renamed $r$ so that we can now focus on proving the same result for $r+1$ (which we can then call our new $n$). Therefore, before and after step 1. we are dealing with inequalities that are known to hold, and we can combine them with other inequalities like $rp^2\geq0$ in the usual fashion, as explained in other answers.

However if this had been a non-induction proof, then $(1+p)^n \geq 1 + np$ would just be our goal, and dropping positive terms from the right hand side would indeed be illegal, as this weakens the goal (we would end up proving less than we claimed). Incidentally, the multiplication by the positive factor $(1+p)$ in step 1. would still be justified (as $a\geq b$ if and only if $ra\geq rb$ when $r>0$), but for the opposite reason: in the actual induction proof we are saying "we assume $(1+p)^r \geq 1 + rp$ and this implies $(1+p)^{r+1} \geq 1 + rp+p+rp^2$" while in a non-induction proof we could validly argue "we need to prove $(1+p)^r \geq 1 + rp$, and this will follow from $(1+p)^{r+1} \geq 1 + rp+p+rp^2$" (but then we would get stuck, and in particularly dropping $rp^2$ would be disallowed).

By the way, the book is really wrong in saying that dropping $rp^2$ strengthens the inequality, it really weakens it, as I said above. But what the author probably wanted to say is that dropping the term only makes the inequality more (easily) true, with a greater distance between the two members.

-
Thanks! This was my original confusion. Once I understood that we already know that $(1+p)^n \geq 1 + rp + p + rp^2$ so we can drop the last term without harm, it started making sense. I was originally thinking that we were trying to show that the left side was greater than the right side, which is why I didn't understand how we could drop the last term. – Chris Gregg Dec 18 '12 at 10:57

In $1.$ we have shown that $$(1+p)^{r+1}\geq 1+rp+p+rp^2$$

But we also know that $r > 1$ (because we're doing an induction proof from $1$ upwards); and obviously $p^2 \ge 0$ (because $p$ is real); so we know that $rp^2 \ge 0$. Therefore

$$1+rp+p+rp^2 \ge 1+rp+p$$

So putting these two together gives

$$(1+p)^{r+1}\geq 1+rp+p$$

as required.

In short, if we know that $a \ge b + c$, and we know $c$ is non-negative, we can immediately conclude that $a \ge b$.

-

We can drop it, because the inequality still holds true if we drop it. We are not proving the inequality here, inequality is already assumed true. So we just derive a weaker inequality from a stronger one, because the weaker version is the one that is useful for our purpose. Of course if we were trying to prove the original inequality, then we could not drop terms from it, prove the weak version and then say that we proved the original inequality.

-

if $a \geq b$ and $b \geq c$, then $a \geq c$. Since $rp^2$ is positive then it is clear that $x+ rp^2 > x$

-