# Prove by induction the inequality

• docnet

#### docnet

Homework Statement
Prove by induction on ##n## that when ##x>0##,
Relevant Equations
##(1+x)^n\ge 1+nx+\frac{n(n-1)}{2}x^2## for all positive intergers ##n##.
The statements holds for the case ##n=1##
\begin{align} 1+x \leq & 1+x+\frac{1}{2}\cdot 0\cdot x^2\\
=&1+x \end{align}
Assume the statement holds true for ##n=k##
$$(1+x)^k\geq 1+kx+\frac{k(k-1)}{2} x^2$$
Then, for ##n=k+1##, we have the following
\begin{align} (1+x)^k\cdot (1+x)\geq& 1+kx+\frac{k(k-1)}{2} x^2+x+kx^2\\
(1+x)^{k+1}\geq& 1+(k+1)x+\frac{(k+1)k}{2} x^2 \end{align}
Which means the statement holds for all positive integers ##n##.

I am unsure about the term ##+kx^2## in the second to last line. I computed it by working backwards from the conclusion and solving for ##A## $$k(k-1)+A=(k+1)k$$But I do not know how to obtain the term working in the forward direction.

I think you're supposed to use the inductive hypothesis on the ##(1+x)^k##, multiply that by ##(1+x)##, expand everything, and throw out the ##x^3## term that you get since that only makes the rest of it smaller.

• hutchphd and SammyS
I think you're supposed to use the inductive hypothesis on the ##(1+x)^k##, multiply that by ##(1+x)##, expand everything, and throw out the ##x^3## term that you get since that only makes the rest of it smaller.
I do not understand what you mean. I think I already multiplied ##(1+x)^k## by ##(1+x)## in line ##(3)##. Expanding it would be impossible for large values of ##k##.

I think I figured out how to correct my mistake in the original post.

The statements holds for the case ##n=1##
\begin{align} 1+x \leq & 1+x+\frac{1}{2}\cdot 0\cdot x^2\\
=&1+x \end{align}
Assume the statement holds true for ##n=k##
$$(1+x)^k\geq 1+kx+\frac{k(k-1)}{2} x^2$$
Then, for ##n=k+1##, we have the following
\begin{align} (1+x)^k\cdot (1+x)\geq& 1+kx+\frac{k(k-1)}{2} x^2+x+0\cdot \frac{1}{2}\cdot x^2\\
=& 1+(k+1)x+\frac{k(k-1)}{2} x^2 \end{align}
\begin{align}k+1>&k-1\\
\Rightarrow\frac{(k+1)k}{2}>&\frac{k(k-1)}{2}
\end{align}
\begin{align}\Rightarrow (1+x)^{k+1}\geq& 1+(k+1)x+\frac{(k+1)k}{2} x^2\\
>& 1+(k+1)x+\frac{k(k-1)}{2} x^2
\end{align}
So the statement holds for all positive integers ##n##.

Last edited:
...

I think I figured out how to correct my mistake in the original post.
...

So the statement holds for all positive integers ##n##.
You have a logical error in your argument.

Lines (7) and (8) give us the following, which certainly follows, however, it is not a "strong" enough statement to get the desired result.

The statement in line (10) is true enough and leads to

##\displaystyle 1+(k+1)x+\frac{k(k+1)}{2} x^2 \gt 1+(k+1)x+\frac{k(k-1)}{2} x^2 ##

That inequality is in the wrong direction to give the desired result.

• docnet
I think you're supposed to use the inductive hypothesis on the ##(1+x)^k##, multiply that by ##(1+x)##, expand everything, and throw out the ##x^3## term that you get since that only makes the rest of it smaller.
To elaborate on what @Office_Shredder suggests here:

Take:
##\displaystyle (1+x)^k\geq 1+kx+\frac{k(k-1)}{2} x^2##
and multiply both sides by ##(1+x)##.

Expand the right hand side.

• docnet
Oh no. I should have multiplied both sides by ##1+x## at the induction step but I did something weird like adding to one side.

The correct induction step:
Assume the statement is true for ##n=k##
$$(1+x)^k\geq 1+kx+\frac{k(k-1)}{2}x^2$$
Then for ##n=k+1##,
\begin{align}(1+x)^k(1+x)&\geq (1+kx+\frac{k(k-1)}{2}x^2)(1+x)\\
=&1+(k+1)x+\frac{k(k+1)}{2}x^2+\frac{k(k-1)}{2}x^3\end{align}
##x## is positive and ##k## is a positive integer greater than ##1##, so ##\frac{k(k-1)}{2}x^3>0##.
\begin{align} \Rightarrow (1+x)^{k+1}>&1+(k+1)x+\frac{k(k+1)}{2}x^2\end{align}
So the statement holds true for all values of ##n##.

• SammyS
##x## is positive and ##k## is a positive integer greater than ##1##, so ##\frac{k(k-1)}{2}x^3>0##.
There's a small error here. ##k \ge 1## and ##\frac{k(k-1)}{2}x^3 \ge 0##. So, we have equality for ##n = 1## and ##n = 2##. You need ##k = 1## to cover the first inductive step from ##k = 1## to ##k+1 = 2##.

• docnet
There's a small error here. ##k \ge 1## and ##\frac{k(k-1)}{2}x^3 \ge 0##. So, we have equality for ##n = 1## and ##n = 2##. You need ##k = 1## to cover the first inductive step from ##k = 1## to ##k+1 = 2##.
Oh okay. That makes sense. Thank you. I thought that showing the statement holds for the case ##n=1## in the first step of the proof means we only consider the integers ##k>1## in the second step. To be honest, I still do not fully understand how inductive proofs work. Although I have almost learned how to write simple inductive proofs, I do not understand why it should be a proof at all, and why it is structured the way it is.

Also, nothing ever gets by you @PeroK, does it?

Oh okay. That makes sense. Thank you. I thought that showing the statement holds for the case ##n=1## in the first step of the proof means we only consider the integers ##k>1## in the second step. To be honest, I still do not fully understand how inductive proofs work. Although I have almost learned how to write simple inductive proofs, I do not understand why it should be a proof at all, and why it is structured the way it is.
Suppose we show ##P(1)## and ##\forall k \ge 1: P(k) \Rightarrow P(k+1)##. Then we have ##\forall n \ge 1: P(n)##. That's what induction says.

To see this, let's call the inductive step ##I(k)##:
$$I(k) \equiv P(k) \ \Rightarrow P(k+1)$$Now, for example, suppose we want to show ##P(63)##:
$$P(1) \ \text{and} \ I(1) \ \Rightarrow P(2)$$ $$P(2) \ \text{and} \ I(2) \ \Rightarrow P(3)$$$$\dots$$$$P(62) \ \text{and} \ I(62) \ \Rightarrow P(63)$$And, in general, we can do that for any ##n##.

Also, suppose, you claim induction does not work. I.e. we have a case where ##P(1)## and ##\forall k \ge 1: I(k)##, and yet there is some ##n_0## where ##P(n_0)## fails. That's what it would mean for induction not to work. You check ##P(1)## and you prove ##I(k)##, for ##k \ge 1##, yet there is some ##n_0## where ##P(n_0)## is false.

Now, we definitely have ##I(n_0 - 1)##. Because we've proved the inductive step for all ##k \ge 1##. And, if we have ##P(n_0 -1)## then we have ##P(n_0)##. That's a contradiction to ##P(n_0)## being false. That means that ##P(n_0 -1)## must be false.

We can then argue in one of two ways. We could let ##n_0## be the least value of which ##P(n)## is false. And we immediately have a contradiction, because we've shown that ##P(n_0 -1)## is also false.

Or, we could work our way backwards one step at a time until we get ##P(2)## false and finally ##P(1)## false. Which is a contradiction, as we've checked ##P(1)##.

Therefore, induction works!

• docnet
Also, nothing ever gets by you @PeroK, does it?
I don't know about that. I generally check ##n = 2## if I can, as it stops me wasting time trying to prove induction of something that isn't true! I saw the equality for ##n = 2## and was, therefore, suspicious of your strict inequality.

It's a minor point!

• docnet
Suppose we show ##P(1)## and ##\forall k \ge 1: P(k) \Rightarrow P(k+1)##. Then we have ##\forall n \ge 1: P(n)##. That's what induction says.

To see this, let's call the inductive step ##I(k)##:
$$I(k) \equiv P(k) \ \Rightarrow P(k+1)$$Now, for example, suppose we want to show ##P(63)##:
$$P(1) \ \text{and} \ I(1) \ \Rightarrow P(2)$$ $$P(2) \ \text{and} \ I(2) \ \Rightarrow P(3)$$$$\dots$$$$P(62) \ \text{and} \ I(62) \ \Rightarrow P(63)$$And, in general, we can do that for any ##n##.

Also, suppose, you claim induction does not work. I.e. we have a case where ##P(1)## and ##\forall k \ge 1: I(k)##, and yet there is some ##n_0## where ##P(n_0)## fails. That's what it would mean for induction not to work. You check ##P(1)## and you prove ##I(k)##, for ##k \ge 1##, yet there is some ##n_0## where ##P(n_0)## is false.

Now, we definitely have ##I(n_0 - 1)##. Because we've proved the inductive step for all ##k \ge 1##. And, if we have ##P(n_0 -1)## then we have ##P(n_0)##. That's a contradiction to ##P(n_0)## being false. That means that ##P(n_0 -1)## must be false.

We can then argue in one of two ways. We could let ##n_0## be the least value of which ##P(n)## is false. And we immediately have a contradiction, because we've shown that ##P(n_0 -1)## is also false.

Or, we could work our way backwards one step at a time until we get ##P(2)## false and finally ##P(1)## false. Which is a contradiction, as we've checked ##P(1)##.

Therefore, induction works!
That is very cool! You wrote a proof that induction works. I have never seen that before.

Question: Does that method induction work for all values of ##n## up to a countable infinity, or only up to finite values of ##n##? Or is there a different procedure for countably infinite values of ##n##?

I don't know about that. I generally check ##n = 2## if I can, as it stops me wasting time trying to prove induction of something that isn't true! I saw the equality for ##n = 2## and was, therefore, suspicious of your strict inequality.

It's a minor point!
Maybe minor, but an important point nonetheless :)

• PeroK
Question: Does that method induction work for all values of ##n## up to a countable infinity, or only up to finite values of ##n##? Or is there a different procedure for countably infinite values of ##n##?
There is a critical, fundamental point here about the nature and properties of countably infinite sets: i.e. ##\mathbb N##.

If we say that a statement is true for all ##n \in \mathbb N##, then:

a) That is a statement about finite numbers. Every ##n## for which that statement is true is a finite positive integer.

b) The statement is true, collectively, for an infinite number of integers at one mathematical stroke.

To rephrase this idea: if a statement is true for every finite subset of ##\mathbb N##, then it is true for all ##\mathbb N##.

We can actually use the idea of contraposition now to prove that. The contraposition is:

If a statement is false for ##\mathbb N##, then it must be false for some finite subset of ##\mathbb N##.

And, of course, that holds, because if the statement is false, it must be false for some specific ##n \in \mathbb N## and hence false for any finite subset that includes ##n##.

Therefore: by showing that induction works for any finite value of ##n##, implies that induction works for the whole countably infinite set ##\mathbb N##.

Going beyond the integers, there is a thing called transfinite induction. But, in truth, I know very little about that:

https://en.wikipedia.org/wiki/Transfinite_induction

• docnet