Prove by induction the inequality

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

 

[Office_Shredder]

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.

 

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

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

 

[SammyS]

...

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.
$\displaystyle \quad \quad (1+x)^k\cdot (1+x)\geq 1+(k+1)x+\frac{k(k-1)}{2} x^2$

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.

 

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

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

 

[PeroK]

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

 

[docnet]

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

 

[PeroK]

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!

 

[PeroK]

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$?

 

[docnet]

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