# Induction Proof, Apostol Calc Vol I, I.4.4.7

• Jonathanlikesmath
In summary, the proof uses the principle of mathematical induction to show that the inequality ##(1+x)^n > 1 + nx + nx^2## is true for all ##x \ge 3## and all integers ##n \ge 3##. The proof begins by setting ##n=3## and showing that the inequality is true for ##x \ge 3##. Then, it assumes that the inequality is true for some integer ##k \ge 3## and uses this assumption to show that it is also true for ##k+1##. This is done by expanding ##(1+x)^{k+1}## and

#### Jonathanlikesmath

Homework Statement
Let ##n_1## be the smallest positive integer ##n## for which the inequality ##(1+x)^n > 1 + nx + nx^2 ## is true for all ##x >0##. Compute ##n_1##, and prove that the inequality is true for all integers ## n \ge n_1##.
Relevant Equations
N/A
For calculating ##n_1## I had no problems as ##n_1 = 3##.

PF: Show ##(1+x)^n > 1 + nx + nx^2 ## is true for all ##x \ge 3##.

Let ##n = 3, (1+x)^3 > 3x^2 + 3x + 1 ##

##x^3 +3x^2 +3x + 3 > 3x^2 + 3x + 1 ## is true.

Assume ## n = k ## such that ##(1+x)^k > 1+kx + kx^2, k \ge 3## is true.

We want to show ## n = k + 1, n \ge 3 ## is true.

##(1+x)^{k + 1} > 1 + (k+1)x + (k+1)x^2##

##(1+x)^k(1+x) > kx^2 +x^2 + kx + x + 1##

##(1+x)^k(1+x) > (kx^2 +kx + 1) + x^2 + x ##

After a couple hours of algebra I came back to this spot above and think I am in the right place, because I noticed I have my assumption from the inductive step as part of the equation. However, I am unsure of how to show the product on the LHS is greater than the sum on the RHS.

Additionally, I worked to the following:

##(1+x)^k > \frac{kx^2 + kx + 1}{(1+x)} + x ##

Which makes me feel even better about the claim, but again under of how to show that LHS > RHS. I really fill like this is the spot, more than above as I have made the RHS of my inductive step smaller, while I am only add x to its total.

I went back through the previous problems to see if I proved something that would help solve this problem but I am not seeing anything.

Additionally, there is an issue that I believe just for new users. For MathJax to work you have to log out once you confirm your account and then log back in otherwise MathJax will not work. I spent way too long trying to get it to work and searching for help, there was a post which stated the fix. This should be added to the LaTex Guide!

Jonathan

Delta2
Jonathanlikesmath said:
Homework Statement:: Let ##n_1## be the smallest positive integer ##n## for which the inequality ##(1+x)^n > 1 + nx + nx^2 ## is true for all ##x >0##. Compute ##n_1##, and prove that the inequality is true for all integers ## n \ge n_1##.
Relevant Equations:: N/A

For calculating ##n_1## I had no problems as ##n_1 = 3##.

PF: Show ##(1+x)^n > 1 + nx + nx^2 ## is true for all ##x \ge 3##.
... for all ##x>0## and ##n\geq 3.##
Jonathanlikesmath said:
Let ##n = 3, (1+x)^3 > 3x^2 + 3x + 1 ##

##x^3 +3x^2 +3x + 3 > 3x^2 + 3x + 1 ## is true.

Assume ## n = k ## such that ##(1+x)^k > 1+kx + kx^2, k \ge 3## is true.

We want to show ## n = k + 1, n \ge 3 ## is true.
So far so good.
Jonathanlikesmath said:
##(1+x)^{k + 1} > 1 + (k+1)x + (k+1)x^2##
From here on it is problematic. You cannot work with what you want to show! It has to be at the end of the proof, not at the beginning.

The structure of the proof should be
\begin{align*}
(1+x)^{k + 1}&=(1+x)^k\cdot (1+x) >_{i.h.} (1+kx+kx^2) \cdot (1+x)\\
&\ge \; \ldots\\
&\ge \; \ldots\\
&\ge 1+(k+1)x+(k+1)x^2
\end{align*}

and you should fill the gaps. Do not forget that ##k\geq 3## and ##x>0.##

Jonathanlikesmath said:
##(1+x)^k(1+x) > kx^2 +x^2 + kx + x + 1##

##(1+x)^k(1+x) > (kx^2 +kx + 1) + x^2 + x ##

After a couple hours of algebra I came back to this spot above and think I am in the right place, because I noticed I have my assumption from the inductive step as part of the equation. However, I am unsure of how to show the product on the LHS is greater than the sum on the RHS.

Additionally, I worked to the following:

##(1+x)^k > \frac{kx^2 + kx + 1}{(1+x)} + x ##

Which makes me feel even better about the claim, but again under of how to show that LHS > RHS. I really fill like this is the spot, more than above as I have made the RHS of my inductive step smaller, while I am only add x to its total.

I went back through the previous problems to see if I proved something that would help solve this problem but I am not seeing anything.

Additionally, there is an issue that I believe just for new users. For MathJax to work you have to log out once you confirm your account and then log back in otherwise MathJax will not work. I spent way too long trying to get it to work and searching for help, there was a post which stated the fix. This should be added to the LaTex Guide!

Jonathan

I have been doing my induction proofs incorrect and I think I figured this one out so I will post all for critique.

PF: Show ## (1+x)^n > 1 + nx + nx^2 \text{ is true for all } x \ge 0, n \in \mathbb{Z} \text{ and} \ge 3##.

## \text{Let } n = 3: (1+x)^3 > 1 + 3x + 3x^2##

##x^3 + 3x^2 + 3x + 1 > 1+ 3x + 2x^2 ## is true.

Let ## n = k ## such that ##(1+x)^k > 1 + kx + kx^2## is true for ## x \ge 0 \text{ and } n \ge 3##.

We want to show ## n = k + 1##.

##(1+x)^{k+1} = (1+x)^k(x+1) > (1 + kx + kx^2)(x+1)##

## (1+x)^{k+1} > 1 + kx + kx^2 + x + kx^2 + kx^3##

## (1+x)^{k+1} > 1 + kx + x + 2kx^2 + kx^3 ##

## (1+x)^{k+1} > 1 +x(k+1) + x^2(2k + kx) > 1 + x(k+1) + x^2(k+1) ##

Therefore, ## (1+x)^{k+1} > 1+x(k+1) + x^2(k + 1) ##

By P.M.I. ##(1+x)^n > 1 + nx + nx^2 \text{ is true for all } x \ge 0, n \in \mathbb{Z} \text{ and} \ge 3##.

Q.E.D.

Jonathanlikesmath said:
I have been doing my induction proofs incorrect and I think I figured this one out so I will post all for critique.

PF: Show ## (1+x)^n > 1 + nx + nx^2 \text{ is true for all } x \ge 0, n \in \mathbb{Z} \text{ and} \ge 3##.

## \text{Let } n = 3: (1+x)^3 > 1 + 3x + 3x^2##

##x^3 + 3x^2 + 3x + 1 > 1+ 3x + 2x^2 ## is true.

Let ## n = k ## such that ##(1+x)^k > 1 + kx + kx^2## is true for ## x \ge 0 \text{ and } n \ge 3##.

We want to show ## n = k + 1##.

##(1+x)^{k+1} = (1+x)^k(x+1) > (1 + kx + kx^2)(x+1)##

## (1+x)^{k+1} > 1 + kx + kx^2 + x + kx^2 + kx^3##

## (1+x)^{k+1} > 1 + kx + x + 2kx^2 + kx^3 ##

## (1+x)^{k+1} > 1 +x(k+1) + x^2(2k + kx) > 1 + x(k+1) + x^2(k+1) ##

Therefore, ## (1+x)^{k+1} > 1+x(k+1) + x^2(k + 1) ##

By P.M.I. ##(1+x)^n > 1 + nx + nx^2 \text{ is true for all } x \ge 0, n \in \mathbb{Z} \text{ and} \ge 3##.

Q.E.D.
Looks good.

Can you tell the inequality that uses ##k\geq 3?##

Jonathanlikesmath
Yes, I found ##n_1 = 3## by brute force, thankfully it was small. I am not sure of a clever way to find it if the value was larger or the inequality more complex.

Jonathanlikesmath said:
Yes, I found ##n_1 = 3## by brute force, thankfully it was small. I am not sure of a clever way to find it if the value was larger or the inequality more complex.
No. This was not what I meant. You showed a sequence of inequalities:
##(1+x)^{k+1}>(1+kx+kx^2)(1+x) \geq \ldots \geq (1+(k+1)x+(k+1)x^2)##
Which of those uses ##k\geq 3## or ##k>1## to be exact?

What I wanted to say is the following: You (correctly) used ##x^2(2k+kx)>x^2(k+1).##

This is true, but it uses a few facts that might not be seen:
1. ##x^2 >0##
This is true since squares are always positive, or because ##x>0.##
2. ##kx >0##
This can only be bounded by ##0## from below since ##x>0## can be arbitrarily small.
3. ##2k > k+1##
This is equivalent to ##k>1## which is true since ##k\geq n_1=3>1.##

Last edited:
fresh_42 said:
No. This was not what I meant. You showed a sequence of inequalities:
##(1+x)^{k+1}>(1+kx+kx^2)(1+x) \geq \ldots \geq (1+(k+1)x+(k+1)x^2)##
Which of those uses ##k\geq 3## or ##k>1## to be exact?

What I wanted to say is the following: You (correctly) used ##x^2(2k+kx)>x^2(k+1).##

This is true, but it uses a few facts that might not be seen:
1. ##x^2 >0##
This is true since squares are always positive, or because ##x>0.##
2. ##kx >0##
This can only be bounded by ##0## from below since ##x>0## can be arbitrarily small.
3. ##2k > k+1##
This is equivalent to ##k>1## which is true since ##k\geq n_1=3>1.##
Ok, so with those three facts, not only are you proving the inequality holds but also using the constraints of the initial problem. I would have never figured out what you meant, unless you showed me that or asked me to prove that the inequality holds. Thanks!

fresh_42