Prove by induction the inequality

In summary: Also, nothing ever gets by you @PeroK, does it?I try my best to catch any errors or misunderstandings! As for understanding inductive proofs, it can be a bit difficult to grasp at first. Essentially, you are using the fact that a statement holds for one case to show that it holds for the next case, and then repeating that process until you have shown that it holds for all cases. This works because if you can show that a statement holds for the base case (in this problem, ##n=1##) and then that if it holds for ##n=k##, it also holds for ##n=k+1## (the inductive step), then it must hold for all positive integers ##n
  • #1
docnet
Gold Member
775
456
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.
 
Physics news on Phys.org
  • #2
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.
 
  • Like
Likes hutchphd and SammyS
  • #3
Office_Shredder said:
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:
  • #4
docnet said:
...

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.
 
  • Like
Likes docnet
  • #5
Office_Shredder said:
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.
 
  • Like
Likes docnet
  • #6
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##.
 
  • Like
Likes SammyS
  • #7
docnet said:
##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##.
 
  • Informative
Likes docnet
  • #8
PeroK said:
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.
 
  • #9
Also, nothing ever gets by you @PeroK, does it?
 
  • #10
docnet said:
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!
 
  • Informative
Likes docnet
  • #11
docnet said:
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!
 
  • Informative
Likes docnet
  • #12
PeroK said:
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##?
 
  • #13
PeroK said:
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 :)
 
  • Like
Likes PeroK
  • #14
docnet said:
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
 
  • Informative
Likes docnet

Related to Prove by induction the inequality

1. What is induction and how does it work in mathematical proofs?

Induction is a mathematical proof technique used to establish the truth of a statement for an infinite or large set of numbers or objects. It works by proving the statement for a base case, usually the smallest number or object, and then showing that if the statement holds for some number or object, it also holds for the next number or object in the sequence.

2. How is induction used to prove inequalities?

In induction, we first prove the base case, which is usually the smallest number or object in the sequence. Then, we assume that the statement holds for some number or object. Using this assumption, we then prove that the statement also holds for the next number or object in the sequence. This process is repeated until we can prove that the statement holds for all numbers or objects in the sequence, which proves the inequality.

3. What are the steps involved in proving an inequality by induction?

The steps involved in proving an inequality by induction are:

  1. Prove the base case, usually the smallest number or object in the sequence.
  2. Assume that the statement holds for some number or object.
  3. Use this assumption to prove that the statement also holds for the next number or object in the sequence.
  4. Repeat this process until you can prove that the statement holds for all numbers or objects in the sequence.
  5. Conclude that the inequality is true for all numbers or objects in the sequence.

4. What are some common mistakes to avoid when using induction to prove an inequality?

Some common mistakes to avoid when using induction to prove an inequality are:

  • Not proving the base case.
  • Assuming that the statement holds for all numbers or objects in the sequence without proving it.
  • Using the wrong assumption when proving the statement for the next number or object in the sequence.
  • Not repeating the process until the statement is proven for all numbers or objects in the sequence.
  • Concluding that the statement is true for all numbers or objects in the sequence without proper proof.

5. Can induction be used to prove all inequalities?

No, induction can only be used to prove certain types of inequalities. It is most commonly used for inequalities involving integers, such as sums, products, or powers of integers. It may also be used for certain types of inequalities involving real numbers, but it is not applicable to all types of inequalities.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
10
Views
399
  • Precalculus Mathematics Homework Help
Replies
1
Views
1K
  • Precalculus Mathematics Homework Help
Replies
11
Views
245
  • Precalculus Mathematics Homework Help
Replies
11
Views
429
  • Precalculus Mathematics Homework Help
Replies
6
Views
1K
  • Precalculus Mathematics Homework Help
Replies
13
Views
1K
  • Precalculus Mathematics Homework Help
Replies
1
Views
1K
  • Precalculus Mathematics Homework Help
Replies
3
Views
2K
  • Precalculus Mathematics Homework Help
Replies
7
Views
887
  • Precalculus Mathematics Homework Help
Replies
4
Views
1K
Back
Top