Mixing
Induction Proof Verification via Binomial Theorem
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
I am studying from a text with an overview of discrete mathematics in the beginning. The problem in question is to prove by induction that
$(1+x)^k+1$ $geq$ $1+nx$ for all naturals, where $x > 1$
I proved this by induction in a similar vein as the solution in the back of the book. The following 'proof' in this post was my first attempt, but I was unsure about its validity. Specifically in the induction step (proving that $n+1$ is true) I am afraid that I am making the assumption that it is true before showing that it is true.
Proof
As a base case, take $n=1$. In this case the inequality holds. Now suppose this is true up to the $k$th natural number. We will now show that this is true for $k+1$.
$(1+x)^k+1$ $geq$ $(1+(1+k)x)$
By the binomial theorem the left and right side give
$x^0$ +
$k+1choose 1x$ + ... + $x^k+1$ $geq$ $1+x(k+1)$.
After evaluating the left hand side we obtain
$1$ +
$(k+1)x$ + ... + $x^k+1$ $geq$ $1+(k+1)x$ .
Subtract the right hand side from the first two terms on the left and we have
$k+1choose 2x^2$ + ... + $x^k+1$ $geq$ $0$ .
Because the left hand side is the sum of positive terms* it is certainly greater than or equal to zero.
QED
*I suppose this is only true if for $x>-1$ where $x$ is a natural. Should x be a negative real number less than zero but greater than negative one this would not hold. Thoughts?
An evaluation of whether or not this is otherwise a valid proof by induction would be greatly appreciated. I'd be grateful to hear any other criticisms of my mathematical writing in general.
Edit: thanks to all who proved this in the comments. I actually did it that way as well. The real reason for the post was because I knew I was making a logical error in how I tried to prove via the binomial theorem.
induction
asked Jul 28 at 20:48
TYBG
235
add a comment |Â
up vote
3
down vote
favorite
I am studying from a text with an overview of discrete mathematics in the beginning. The problem in question is to prove by induction that
$(1+x)^k+1$ $geq$ $1+nx$ for all naturals, where $x > 1$
I proved this by induction in a similar vein as the solution in the back of the book. The following 'proof' in this post was my first attempt, but I was unsure about its validity. Specifically in the induction step (proving that $n+1$ is true) I am afraid that I am making the assumption that it is true before showing that it is true.
Proof
As a base case, take $n=1$. In this case the inequality holds. Now suppose this is true up to the $k$th natural number. We will now show that this is true for $k+1$.
$(1+x)^k+1$ $geq$ $(1+(1+k)x)$
By the binomial theorem the left and right side give
$x^0$ +
$k+1choose 1x$ + ... + $x^k+1$ $geq$ $1+x(k+1)$.
After evaluating the left hand side we obtain
$1$ +
$(k+1)x$ + ... + $x^k+1$ $geq$ $1+(k+1)x$ .
Subtract the right hand side from the first two terms on the left and we have
$k+1choose 2x^2$ + ... + $x^k+1$ $geq$ $0$ .
Because the left hand side is the sum of positive terms* it is certainly greater than or equal to zero.
QED
*I suppose this is only true if for $x>-1$ where $x$ is a natural. Should x be a negative real number less than zero but greater than negative one this would not hold. Thoughts?
An evaluation of whether or not this is otherwise a valid proof by induction would be greatly appreciated. I'd be grateful to hear any other criticisms of my mathematical writing in general.
Edit: thanks to all who proved this in the comments. I actually did it that way as well. The real reason for the post was because I knew I was making a logical error in how I tried to prove via the binomial theorem.
induction
asked Jul 28 at 20:48
TYBG
235
1
Are you doing the induction on $n$ or on $k$? Also is the question exactly like that? You sure it isn't with both $n$ or $k$? I don't think that holds for every $n$ for a fixed $k$... Assuming $k = n$ there is a mistake on the induction step: You were supposed to also write $k+1$ on the place of $k$ on the left-hand side...
– karlabos
Jul 28 at 20:53
1
You should correct the statement in your text according to the indication given. Note also that $x$ is a real number and that the inequality holds for $x ge-1$. Refer to en.m.wikipedia.org/wiki/Bernoulli%27s_inequality for any other information.
– gimusi
Jul 28 at 22:15
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
I am studying from a text with an overview of discrete mathematics in the beginning. The problem in question is to prove by induction that
$(1+x)^k+1$ $geq$ $1+nx$ for all naturals, where $x > 1$
I proved this by induction in a similar vein as the solution in the back of the book. The following 'proof' in this post was my first attempt, but I was unsure about its validity. Specifically in the induction step (proving that $n+1$ is true) I am afraid that I am making the assumption that it is true before showing that it is true.
Proof
As a base case, take $n=1$. In this case the inequality holds. Now suppose this is true up to the $k$th natural number. We will now show that this is true for $k+1$.
$(1+x)^k+1$ $geq$ $(1+(1+k)x)$
By the binomial theorem the left and right side give
$x^0$ +
$k+1choose 1x$ + ... + $x^k+1$ $geq$ $1+x(k+1)$.
After evaluating the left hand side we obtain
$1$ +
$(k+1)x$ + ... + $x^k+1$ $geq$ $1+(k+1)x$ .
Subtract the right hand side from the first two terms on the left and we have
$k+1choose 2x^2$ + ... + $x^k+1$ $geq$ $0$ .
Because the left hand side is the sum of positive terms* it is certainly greater than or equal to zero.
QED
*I suppose this is only true if for $x>-1$ where $x$ is a natural. Should x be a negative real number less than zero but greater than negative one this would not hold. Thoughts?
An evaluation of whether or not this is otherwise a valid proof by induction would be greatly appreciated. I'd be grateful to hear any other criticisms of my mathematical writing in general.
Edit: thanks to all who proved this in the comments. I actually did it that way as well. The real reason for the post was because I knew I was making a logical error in how I tried to prove via the binomial theorem.
induction
asked Jul 28 at 20:48
TYBG
235
I am studying from a text with an overview of discrete mathematics in the beginning. The problem in question is to prove by induction that
$(1+x)^k+1$ $geq$ $1+nx$ for all naturals, where $x > 1$
I proved this by induction in a similar vein as the solution in the back of the book. The following 'proof' in this post was my first attempt, but I was unsure about its validity. Specifically in the induction step (proving that $n+1$ is true) I am afraid that I am making the assumption that it is true before showing that it is true.
Proof
As a base case, take $n=1$. In this case the inequality holds. Now suppose this is true up to the $k$th natural number. We will now show that this is true for $k+1$.
$(1+x)^k+1$ $geq$ $(1+(1+k)x)$
By the binomial theorem the left and right side give
$x^0$ +
$k+1choose 1x$ + ... + $x^k+1$ $geq$ $1+x(k+1)$.
After evaluating the left hand side we obtain
$1$ +
$(k+1)x$ + ... + $x^k+1$ $geq$ $1+(k+1)x$ .
Subtract the right hand side from the first two terms on the left and we have
$k+1choose 2x^2$ + ... + $x^k+1$ $geq$ $0$ .
Because the left hand side is the sum of positive terms* it is certainly greater than or equal to zero.
QED
*I suppose this is only true if for $x>-1$ where $x$ is a natural. Should x be a negative real number less than zero but greater than negative one this would not hold. Thoughts?
An evaluation of whether or not this is otherwise a valid proof by induction would be greatly appreciated. I'd be grateful to hear any other criticisms of my mathematical writing in general.
Edit: thanks to all who proved this in the comments. I actually did it that way as well. The real reason for the post was because I knew I was making a logical error in how I tried to prove via the binomial theorem.
induction
asked Jul 28 at 20:48
TYBG
235
edited Aug 4 at 21:13
asked Jul 28 at 20:48
TYBG
235
asked Jul 28 at 20:48
TYBG
235
asked Jul 28 at 20:48
TYBG
235
235
1
Are you doing the induction on $n$ or on $k$? Also is the question exactly like that? You sure it isn't with both $n$ or $k$? I don't think that holds for every $n$ for a fixed $k$... Assuming $k = n$ there is a mistake on the induction step: You were supposed to also write $k+1$ on the place of $k$ on the left-hand side...
– karlabos
Jul 28 at 20:53
1
You should correct the statement in your text according to the indication given. Note also that $x$ is a real number and that the inequality holds for $x ge-1$. Refer to en.m.wikipedia.org/wiki/Bernoulli%27s_inequality for any other information.
– gimusi
Jul 28 at 22:15
add a comment |Â
1
Are you doing the induction on $n$ or on $k$? Also is the question exactly like that? You sure it isn't with both $n$ or $k$? I don't think that holds for every $n$ for a fixed $k$... Assuming $k = n$ there is a mistake on the induction step: You were supposed to also write $k+1$ on the place of $k$ on the left-hand side...
– karlabos
Jul 28 at 20:53
1
You should correct the statement in your text according to the indication given. Note also that $x$ is a real number and that the inequality holds for $x ge-1$. Refer to en.m.wikipedia.org/wiki/Bernoulli%27s_inequality for any other information.
– gimusi
Jul 28 at 22:15
1
1
Are you doing the induction on $n$ or on $k$? Also is the question exactly like that? You sure it isn't with both $n$ or $k$? I don't think that holds for every $n$ for a fixed $k$... Assuming $k = n$ there is a mistake on the induction step: You were supposed to also write $k+1$ on the place of $k$ on the left-hand side...
– karlabos
Jul 28 at 20:53
Are you doing the induction on $n$ or on $k$? Also is the question exactly like that? You sure it isn't with both $n$ or $k$? I don't think that holds for every $n$ for a fixed $k$... Assuming $k = n$ there is a mistake on the induction step: You were supposed to also write $k+1$ on the place of $k$ on the left-hand side...
– karlabos
Jul 28 at 20:53
1
1
You should correct the statement in your text according to the indication given. Note also that $x$ is a real number and that the inequality holds for $x ge-1$. Refer to en.m.wikipedia.org/wiki/Bernoulli%27s_inequality for any other information.
– gimusi
Jul 28 at 22:15
You should correct the statement in your text according to the indication given. Note also that $x$ is a real number and that the inequality holds for $x ge-1$. Refer to en.m.wikipedia.org/wiki/Bernoulli%27s_inequality for any other information.
– gimusi
Jul 28 at 22:15
add a comment |Â
4 Answers
4
active
oldest
votes
up vote
2
down vote
accepted
As mentioned above, you do not use your induction hypothesis, so you are not really doing a proof by induction. However, there is a more serious (although very common) problem with the way you have structured your proof. Your concern about assuming the claim you are trying to prove is spot on. In your very first line of math you start with what it is you are trying to show and work from there toward something you know to be true in the last line, but this is not in general a valid form of reasoning.
If the statement you start out with is false, you may (through a series of algebraic manipulations) arrive at a true statement, so you cannot use this method to determine whether the statement you started with was true. Take this as a simple example: $-1 = 1implies(-1)^2 = 1^2implies1=1$. The fact that the last line is true does not allow me to conclude that the first line was true (it's obviously not!). If all of your steps are "reversible" (unlike squaring) you can do this, but it is still best practice to avoid arguing this way in all circumstances. In general, you want to start from one side of what you want to prove and work toward the other (in a proof by induction, this is where you will need to use the inductive hypothesis.
E.g. in this problem: Suppose the $(1+x)^k geq 1+kx$ for $x>1$ for some natural number $k$. Consider $(1+x)^k+1$. By rules of exponents, we can write $(1+x)^k+1 = (1+x)(1+x)^k$. By the induction hypothesis, we know that $(1+x)^k geq 1+kx$, and since $(1+x)$ is positive for $x>1$, we can say $(1+x)(1+x)^k geq (1+x)(1+kx)$.
I'll let you take it from there!
answered Jul 28 at 21:24
Taylor M
1564
Thank you! and all the others that answered. The second paragraph was what I was looking for; I had a feeling it was the same mistake that I had made on a discrete math problem set. I will definitely keep the -1 = 1 example in the back of my mind to prevent future logical mistakes when doing proofs.
– TYBG
Aug 4 at 21:12
add a comment |Â
up vote
3
down vote
The statement should be
- $(1+x)^kgeq 1+kx$ for all naturals, where $x > 1$
this is the Bernoulli inequality and it is valid for any $xge-1$ (in the link you may find all the information about other cases).
No your proof is not to by induction since to prove you are not using any induction hypothesis but another result (the binomial theorem).
answered Jul 28 at 20:54
gimusi
64.7k73482
add a comment |Â
up vote
2
down vote
By using the principle of induction you want to show somehow that the case $n=k+1$ follows the correctness of the case $n=k$. So you need to use the hypotesis somewhere. In this case the induction hypotesis would be
$$(1+x)^k~geq~1+kx$$
And like you mentioned this holds for $n=1$. Now just start with this and multiply both sides by $(1+x)$ and continue as it follows
$$beginalign
(1+x)^k~&geq~1+kx\
(1+x)^k(1+x)~&geq~(1+kx)(1+x)\
(1+x)^k+1~&geq~1+kx+x+kx^2\
(1+x)^k+1~&geq~1+(k+1)x+kx^2\
endalign$$
Now we only to take care of the extra term $kx^2$. By assuming that $k>0$, which is true by the fact that we are using the mathematical induction where we are only dealing with $kinmathbbN$, we can use the inequality
$$a^2~>~0~~textand so~~kcdot x^2~>~kcdot 0~,~kx^2~>~0$$
which holds for any number except $0$. So we can proceed by
$$beginalign
1+(k+1)x+kx^2~&geq~1+(k+1)x
endalign$$
which leads to
$$beginalign
(1+x)^k+1~geq~1+(k+1)x+kx^2~geq~1+(k+1)x
endalign$$
and by the transitivity of inequalities we arrive at
$$(1+x)^k+1~geq~1+(k+1)x$$
The advantage of this proof that you are only forced to use one other inequality, the one about the square of a number, and not something more complicated like the Binomial Theorem.
answered Jul 28 at 21:14
mrtaurho
703118
add a comment |Â
up vote
0
down vote
You needn't invoke the Binomial theorem, and your proof is not inductive.
The induction hypothesis is
$$(1+x)^nge 1+nx$$
and you need to show that this implies
$$(1+x)^n+1ge 1+(n+1)x.$$
Indeed,
$$(1+x)^n+1=(1+x)^n(1+x)ge^1 (1+nx)(1+x)ge^2 1+x+nx=1+(n+1)x.$$
$^1$ by the induction hypothesis.
$^2$ because we drop the term $x^2$.
As the statement is true for $n=1$, it is true for all $n$.
answered Jul 28 at 21:35
Yves Daoust
110k665203
Maybe it is also useful to add to the note (1) that it is here we are assuming that $xge-1$ in order to have a correct inequality.
– gimusi
Jul 28 at 22:06
@gimusi: the problem statement says $x>1$, which is stronger than $xge-1$.
– Yves Daoust
Jul 28 at 22:07
Yes okay, but since you presented a complete proof, my suggestion is to add this important point which can be not simple to be appreciated by a student facing for the first time such kind of proof.
– gimusi
Jul 28 at 22:12
@gimusi: no, I am sticking to the problem as stated. I don't want to clutter the answer with distracting details.
– Yves Daoust
Jul 28 at 22:15
As you like, it was only a suggestion to improve your good answer.
– gimusi
Jul 28 at 22:16
add a comment |Â
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
As mentioned above, you do not use your induction hypothesis, so you are not really doing a proof by induction. However, there is a more serious (although very common) problem with the way you have structured your proof. Your concern about assuming the claim you are trying to prove is spot on. In your very first line of math you start with what it is you are trying to show and work from there toward something you know to be true in the last line, but this is not in general a valid form of reasoning.
If the statement you start out with is false, you may (through a series of algebraic manipulations) arrive at a true statement, so you cannot use this method to determine whether the statement you started with was true. Take this as a simple example: $-1 = 1implies(-1)^2 = 1^2implies1=1$. The fact that the last line is true does not allow me to conclude that the first line was true (it's obviously not!). If all of your steps are "reversible" (unlike squaring) you can do this, but it is still best practice to avoid arguing this way in all circumstances. In general, you want to start from one side of what you want to prove and work toward the other (in a proof by induction, this is where you will need to use the inductive hypothesis.
E.g. in this problem: Suppose the $(1+x)^k geq 1+kx$ for $x>1$ for some natural number $k$. Consider $(1+x)^k+1$. By rules of exponents, we can write $(1+x)^k+1 = (1+x)(1+x)^k$. By the induction hypothesis, we know that $(1+x)^k geq 1+kx$, and since $(1+x)$ is positive for $x>1$, we can say $(1+x)(1+x)^k geq (1+x)(1+kx)$.
I'll let you take it from there!
answered Jul 28 at 21:24
Taylor M
1564
Thank you! and all the others that answered. The second paragraph was what I was looking for; I had a feeling it was the same mistake that I had made on a discrete math problem set. I will definitely keep the -1 = 1 example in the back of my mind to prevent future logical mistakes when doing proofs.
– TYBG
Aug 4 at 21:12
add a comment |Â
up vote
2
down vote
accepted
As mentioned above, you do not use your induction hypothesis, so you are not really doing a proof by induction. However, there is a more serious (although very common) problem with the way you have structured your proof. Your concern about assuming the claim you are trying to prove is spot on. In your very first line of math you start with what it is you are trying to show and work from there toward something you know to be true in the last line, but this is not in general a valid form of reasoning.
If the statement you start out with is false, you may (through a series of algebraic manipulations) arrive at a true statement, so you cannot use this method to determine whether the statement you started with was true. Take this as a simple example: $-1 = 1implies(-1)^2 = 1^2implies1=1$. The fact that the last line is true does not allow me to conclude that the first line was true (it's obviously not!). If all of your steps are "reversible" (unlike squaring) you can do this, but it is still best practice to avoid arguing this way in all circumstances. In general, you want to start from one side of what you want to prove and work toward the other (in a proof by induction, this is where you will need to use the inductive hypothesis.
E.g. in this problem: Suppose the $(1+x)^k geq 1+kx$ for $x>1$ for some natural number $k$. Consider $(1+x)^k+1$. By rules of exponents, we can write $(1+x)^k+1 = (1+x)(1+x)^k$. By the induction hypothesis, we know that $(1+x)^k geq 1+kx$, and since $(1+x)$ is positive for $x>1$, we can say $(1+x)(1+x)^k geq (1+x)(1+kx)$.
I'll let you take it from there!
answered Jul 28 at 21:24
Taylor M
1564
Thank you! and all the others that answered. The second paragraph was what I was looking for; I had a feeling it was the same mistake that I had made on a discrete math problem set. I will definitely keep the -1 = 1 example in the back of my mind to prevent future logical mistakes when doing proofs.
– TYBG
Aug 4 at 21:12
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
As mentioned above, you do not use your induction hypothesis, so you are not really doing a proof by induction. However, there is a more serious (although very common) problem with the way you have structured your proof. Your concern about assuming the claim you are trying to prove is spot on. In your very first line of math you start with what it is you are trying to show and work from there toward something you know to be true in the last line, but this is not in general a valid form of reasoning.
If the statement you start out with is false, you may (through a series of algebraic manipulations) arrive at a true statement, so you cannot use this method to determine whether the statement you started with was true. Take this as a simple example: $-1 = 1implies(-1)^2 = 1^2implies1=1$. The fact that the last line is true does not allow me to conclude that the first line was true (it's obviously not!). If all of your steps are "reversible" (unlike squaring) you can do this, but it is still best practice to avoid arguing this way in all circumstances. In general, you want to start from one side of what you want to prove and work toward the other (in a proof by induction, this is where you will need to use the inductive hypothesis.
E.g. in this problem: Suppose the $(1+x)^k geq 1+kx$ for $x>1$ for some natural number $k$. Consider $(1+x)^k+1$. By rules of exponents, we can write $(1+x)^k+1 = (1+x)(1+x)^k$. By the induction hypothesis, we know that $(1+x)^k geq 1+kx$, and since $(1+x)$ is positive for $x>1$, we can say $(1+x)(1+x)^k geq (1+x)(1+kx)$.
I'll let you take it from there!
answered Jul 28 at 21:24
Taylor M
1564
As mentioned above, you do not use your induction hypothesis, so you are not really doing a proof by induction. However, there is a more serious (although very common) problem with the way you have structured your proof. Your concern about assuming the claim you are trying to prove is spot on. In your very first line of math you start with what it is you are trying to show and work from there toward something you know to be true in the last line, but this is not in general a valid form of reasoning.
If the statement you start out with is false, you may (through a series of algebraic manipulations) arrive at a true statement, so you cannot use this method to determine whether the statement you started with was true. Take this as a simple example: $-1 = 1implies(-1)^2 = 1^2implies1=1$. The fact that the last line is true does not allow me to conclude that the first line was true (it's obviously not!). If all of your steps are "reversible" (unlike squaring) you can do this, but it is still best practice to avoid arguing this way in all circumstances. In general, you want to start from one side of what you want to prove and work toward the other (in a proof by induction, this is where you will need to use the inductive hypothesis.
E.g. in this problem: Suppose the $(1+x)^k geq 1+kx$ for $x>1$ for some natural number $k$. Consider $(1+x)^k+1$. By rules of exponents, we can write $(1+x)^k+1 = (1+x)(1+x)^k$. By the induction hypothesis, we know that $(1+x)^k geq 1+kx$, and since $(1+x)$ is positive for $x>1$, we can say $(1+x)(1+x)^k geq (1+x)(1+kx)$.
I'll let you take it from there!
answered Jul 28 at 21:24
Taylor M
1564
answered Jul 28 at 21:24
Taylor M
1564
answered Jul 28 at 21:24
Taylor M
1564
answered Jul 28 at 21:24
Taylor M
1564
1564
Thank you! and all the others that answered. The second paragraph was what I was looking for; I had a feeling it was the same mistake that I had made on a discrete math problem set. I will definitely keep the -1 = 1 example in the back of my mind to prevent future logical mistakes when doing proofs.
– TYBG
Aug 4 at 21:12
add a comment |Â
Thank you! and all the others that answered. The second paragraph was what I was looking for; I had a feeling it was the same mistake that I had made on a discrete math problem set. I will definitely keep the -1 = 1 example in the back of my mind to prevent future logical mistakes when doing proofs.
– TYBG
Aug 4 at 21:12
Thank you! and all the others that answered. The second paragraph was what I was looking for; I had a feeling it was the same mistake that I had made on a discrete math problem set. I will definitely keep the -1 = 1 example in the back of my mind to prevent future logical mistakes when doing proofs.
– TYBG
Aug 4 at 21:12
Thank you! and all the others that answered. The second paragraph was what I was looking for; I had a feeling it was the same mistake that I had made on a discrete math problem set. I will definitely keep the -1 = 1 example in the back of my mind to prevent future logical mistakes when doing proofs.
– TYBG
Aug 4 at 21:12
add a comment |Â
up vote
3
down vote
The statement should be
- $(1+x)^kgeq 1+kx$ for all naturals, where $x > 1$
this is the Bernoulli inequality and it is valid for any $xge-1$ (in the link you may find all the information about other cases).
No your proof is not to by induction since to prove you are not using any induction hypothesis but another result (the binomial theorem).
answered Jul 28 at 20:54
gimusi
64.7k73482
add a comment |Â
up vote
3
down vote
The statement should be
- $(1+x)^kgeq 1+kx$ for all naturals, where $x > 1$
this is the Bernoulli inequality and it is valid for any $xge-1$ (in the link you may find all the information about other cases).
No your proof is not to by induction since to prove you are not using any induction hypothesis but another result (the binomial theorem).
answered Jul 28 at 20:54
gimusi
64.7k73482
add a comment |Â
up vote
3
down vote
up vote
3
down vote
The statement should be
- $(1+x)^kgeq 1+kx$ for all naturals, where $x > 1$
this is the Bernoulli inequality and it is valid for any $xge-1$ (in the link you may find all the information about other cases).
No your proof is not to by induction since to prove you are not using any induction hypothesis but another result (the binomial theorem).
answered Jul 28 at 20:54
gimusi
64.7k73482
The statement should be
- $(1+x)^kgeq 1+kx$ for all naturals, where $x > 1$
this is the Bernoulli inequality and it is valid for any $xge-1$ (in the link you may find all the information about other cases).
No your proof is not to by induction since to prove you are not using any induction hypothesis but another result (the binomial theorem).
answered Jul 28 at 20:54
gimusi
64.7k73482
edited Jul 28 at 21:26
answered Jul 28 at 20:54
gimusi
64.7k73482
answered Jul 28 at 20:54
gimusi
64.7k73482
answered Jul 28 at 20:54
gimusi
64.7k73482
64.7k73482
add a comment |Â
add a comment |Â
up vote
2
down vote
By using the principle of induction you want to show somehow that the case $n=k+1$ follows the correctness of the case $n=k$. So you need to use the hypotesis somewhere. In this case the induction hypotesis would be
$$(1+x)^k~geq~1+kx$$
And like you mentioned this holds for $n=1$. Now just start with this and multiply both sides by $(1+x)$ and continue as it follows
$$beginalign
(1+x)^k~&geq~1+kx\
(1+x)^k(1+x)~&geq~(1+kx)(1+x)\
(1+x)^k+1~&geq~1+kx+x+kx^2\
(1+x)^k+1~&geq~1+(k+1)x+kx^2\
endalign$$
Now we only to take care of the extra term $kx^2$. By assuming that $k>0$, which is true by the fact that we are using the mathematical induction where we are only dealing with $kinmathbbN$, we can use the inequality
$$a^2~>~0~~textand so~~kcdot x^2~>~kcdot 0~,~kx^2~>~0$$
which holds for any number except $0$. So we can proceed by
$$beginalign
1+(k+1)x+kx^2~&geq~1+(k+1)x
endalign$$
which leads to
$$beginalign
(1+x)^k+1~geq~1+(k+1)x+kx^2~geq~1+(k+1)x
endalign$$
and by the transitivity of inequalities we arrive at
$$(1+x)^k+1~geq~1+(k+1)x$$
The advantage of this proof that you are only forced to use one other inequality, the one about the square of a number, and not something more complicated like the Binomial Theorem.
answered Jul 28 at 21:14
mrtaurho
703118
add a comment |Â
up vote
2
down vote
By using the principle of induction you want to show somehow that the case $n=k+1$ follows the correctness of the case $n=k$. So you need to use the hypotesis somewhere. In this case the induction hypotesis would be
$$(1+x)^k~geq~1+kx$$
And like you mentioned this holds for $n=1$. Now just start with this and multiply both sides by $(1+x)$ and continue as it follows
$$beginalign
(1+x)^k~&geq~1+kx\
(1+x)^k(1+x)~&geq~(1+kx)(1+x)\
(1+x)^k+1~&geq~1+kx+x+kx^2\
(1+x)^k+1~&geq~1+(k+1)x+kx^2\
endalign$$
Now we only to take care of the extra term $kx^2$. By assuming that $k>0$, which is true by the fact that we are using the mathematical induction where we are only dealing with $kinmathbbN$, we can use the inequality
$$a^2~>~0~~textand so~~kcdot x^2~>~kcdot 0~,~kx^2~>~0$$
which holds for any number except $0$. So we can proceed by
$$beginalign
1+(k+1)x+kx^2~&geq~1+(k+1)x
endalign$$
which leads to
$$beginalign
(1+x)^k+1~geq~1+(k+1)x+kx^2~geq~1+(k+1)x
endalign$$
and by the transitivity of inequalities we arrive at
$$(1+x)^k+1~geq~1+(k+1)x$$
The advantage of this proof that you are only forced to use one other inequality, the one about the square of a number, and not something more complicated like the Binomial Theorem.
answered Jul 28 at 21:14
mrtaurho
703118
add a comment |Â
up vote
2
down vote
up vote
2
down vote
By using the principle of induction you want to show somehow that the case $n=k+1$ follows the correctness of the case $n=k$. So you need to use the hypotesis somewhere. In this case the induction hypotesis would be
$$(1+x)^k~geq~1+kx$$
And like you mentioned this holds for $n=1$. Now just start with this and multiply both sides by $(1+x)$ and continue as it follows
$$beginalign
(1+x)^k~&geq~1+kx\
(1+x)^k(1+x)~&geq~(1+kx)(1+x)\
(1+x)^k+1~&geq~1+kx+x+kx^2\
(1+x)^k+1~&geq~1+(k+1)x+kx^2\
endalign$$
Now we only to take care of the extra term $kx^2$. By assuming that $k>0$, which is true by the fact that we are using the mathematical induction where we are only dealing with $kinmathbbN$, we can use the inequality
$$a^2~>~0~~textand so~~kcdot x^2~>~kcdot 0~,~kx^2~>~0$$
which holds for any number except $0$. So we can proceed by
$$beginalign
1+(k+1)x+kx^2~&geq~1+(k+1)x
endalign$$
which leads to
$$beginalign
(1+x)^k+1~geq~1+(k+1)x+kx^2~geq~1+(k+1)x
endalign$$
and by the transitivity of inequalities we arrive at
$$(1+x)^k+1~geq~1+(k+1)x$$
The advantage of this proof that you are only forced to use one other inequality, the one about the square of a number, and not something more complicated like the Binomial Theorem.
answered Jul 28 at 21:14
mrtaurho
703118
By using the principle of induction you want to show somehow that the case $n=k+1$ follows the correctness of the case $n=k$. So you need to use the hypotesis somewhere. In this case the induction hypotesis would be
$$(1+x)^k~geq~1+kx$$
And like you mentioned this holds for $n=1$. Now just start with this and multiply both sides by $(1+x)$ and continue as it follows
$$beginalign
(1+x)^k~&geq~1+kx\
(1+x)^k(1+x)~&geq~(1+kx)(1+x)\
(1+x)^k+1~&geq~1+kx+x+kx^2\
(1+x)^k+1~&geq~1+(k+1)x+kx^2\
endalign$$
Now we only to take care of the extra term $kx^2$. By assuming that $k>0$, which is true by the fact that we are using the mathematical induction where we are only dealing with $kinmathbbN$, we can use the inequality
$$a^2~>~0~~textand so~~kcdot x^2~>~kcdot 0~,~kx^2~>~0$$
which holds for any number except $0$. So we can proceed by
$$beginalign
1+(k+1)x+kx^2~&geq~1+(k+1)x
endalign$$
which leads to
$$beginalign
(1+x)^k+1~geq~1+(k+1)x+kx^2~geq~1+(k+1)x
endalign$$
and by the transitivity of inequalities we arrive at
$$(1+x)^k+1~geq~1+(k+1)x$$
The advantage of this proof that you are only forced to use one other inequality, the one about the square of a number, and not something more complicated like the Binomial Theorem.
answered Jul 28 at 21:14
mrtaurho
703118
edited Jul 28 at 21:42
answered Jul 28 at 21:14
mrtaurho
703118
answered Jul 28 at 21:14
mrtaurho
703118
answered Jul 28 at 21:14
mrtaurho
703118
703118
add a comment |Â
add a comment |Â
up vote
0
down vote
You needn't invoke the Binomial theorem, and your proof is not inductive.
The induction hypothesis is
$$(1+x)^nge 1+nx$$
and you need to show that this implies
$$(1+x)^n+1ge 1+(n+1)x.$$
Indeed,
$$(1+x)^n+1=(1+x)^n(1+x)ge^1 (1+nx)(1+x)ge^2 1+x+nx=1+(n+1)x.$$
$^1$ by the induction hypothesis.
$^2$ because we drop the term $x^2$.
As the statement is true for $n=1$, it is true for all $n$.
answered Jul 28 at 21:35
Yves Daoust
110k665203
Maybe it is also useful to add to the note (1) that it is here we are assuming that $xge-1$ in order to have a correct inequality.
– gimusi
Jul 28 at 22:06
@gimusi: the problem statement says $x>1$, which is stronger than $xge-1$.
– Yves Daoust
Jul 28 at 22:07
Yes okay, but since you presented a complete proof, my suggestion is to add this important point which can be not simple to be appreciated by a student facing for the first time such kind of proof.
– gimusi
Jul 28 at 22:12
@gimusi: no, I am sticking to the problem as stated. I don't want to clutter the answer with distracting details.
– Yves Daoust
Jul 28 at 22:15
As you like, it was only a suggestion to improve your good answer.
– gimusi
Jul 28 at 22:16
add a comment |Â
up vote
0
down vote
You needn't invoke the Binomial theorem, and your proof is not inductive.
The induction hypothesis is
$$(1+x)^nge 1+nx$$
and you need to show that this implies
$$(1+x)^n+1ge 1+(n+1)x.$$
Indeed,
$$(1+x)^n+1=(1+x)^n(1+x)ge^1 (1+nx)(1+x)ge^2 1+x+nx=1+(n+1)x.$$
$^1$ by the induction hypothesis.
$^2$ because we drop the term $x^2$.
As the statement is true for $n=1$, it is true for all $n$.
answered Jul 28 at 21:35
Yves Daoust
110k665203
Maybe it is also useful to add to the note (1) that it is here we are assuming that $xge-1$ in order to have a correct inequality.
– gimusi
Jul 28 at 22:06
@gimusi: the problem statement says $x>1$, which is stronger than $xge-1$.
– Yves Daoust
Jul 28 at 22:07
Yes okay, but since you presented a complete proof, my suggestion is to add this important point which can be not simple to be appreciated by a student facing for the first time such kind of proof.
– gimusi
Jul 28 at 22:12
@gimusi: no, I am sticking to the problem as stated. I don't want to clutter the answer with distracting details.
– Yves Daoust
Jul 28 at 22:15
As you like, it was only a suggestion to improve your good answer.
– gimusi
Jul 28 at 22:16
add a comment |Â
up vote
0
down vote
up vote
0
down vote
You needn't invoke the Binomial theorem, and your proof is not inductive.
The induction hypothesis is
$$(1+x)^nge 1+nx$$
and you need to show that this implies
$$(1+x)^n+1ge 1+(n+1)x.$$
Indeed,
$$(1+x)^n+1=(1+x)^n(1+x)ge^1 (1+nx)(1+x)ge^2 1+x+nx=1+(n+1)x.$$
$^1$ by the induction hypothesis.
$^2$ because we drop the term $x^2$.
As the statement is true for $n=1$, it is true for all $n$.
answered Jul 28 at 21:35
Yves Daoust
110k665203
You needn't invoke the Binomial theorem, and your proof is not inductive.
The induction hypothesis is
$$(1+x)^nge 1+nx$$
and you need to show that this implies
$$(1+x)^n+1ge 1+(n+1)x.$$
Indeed,
$$(1+x)^n+1=(1+x)^n(1+x)ge^1 (1+nx)(1+x)ge^2 1+x+nx=1+(n+1)x.$$
$^1$ by the induction hypothesis.
$^2$ because we drop the term $x^2$.
As the statement is true for $n=1$, it is true for all $n$.
answered Jul 28 at 21:35
Yves Daoust
110k665203
edited Jul 28 at 21:41
answered Jul 28 at 21:35
Yves Daoust
110k665203
answered Jul 28 at 21:35
Yves Daoust
110k665203
answered Jul 28 at 21:35
Yves Daoust
110k665203
110k665203
Maybe it is also useful to add to the note (1) that it is here we are assuming that $xge-1$ in order to have a correct inequality.
– gimusi
Jul 28 at 22:06
@gimusi: the problem statement says $x>1$, which is stronger than $xge-1$.
– Yves Daoust
Jul 28 at 22:07
Yes okay, but since you presented a complete proof, my suggestion is to add this important point which can be not simple to be appreciated by a student facing for the first time such kind of proof.
– gimusi
Jul 28 at 22:12
@gimusi: no, I am sticking to the problem as stated. I don't want to clutter the answer with distracting details.
– Yves Daoust
Jul 28 at 22:15
As you like, it was only a suggestion to improve your good answer.
– gimusi
Jul 28 at 22:16
add a comment |Â
Maybe it is also useful to add to the note (1) that it is here we are assuming that $xge-1$ in order to have a correct inequality.
– gimusi
Jul 28 at 22:06
@gimusi: the problem statement says $x>1$, which is stronger than $xge-1$.
– Yves Daoust
Jul 28 at 22:07
Yes okay, but since you presented a complete proof, my suggestion is to add this important point which can be not simple to be appreciated by a student facing for the first time such kind of proof.
– gimusi
Jul 28 at 22:12
@gimusi: no, I am sticking to the problem as stated. I don't want to clutter the answer with distracting details.
– Yves Daoust
Jul 28 at 22:15
As you like, it was only a suggestion to improve your good answer.
– gimusi
Jul 28 at 22:16
Maybe it is also useful to add to the note (1) that it is here we are assuming that $xge-1$ in order to have a correct inequality.
– gimusi
Jul 28 at 22:06
Maybe it is also useful to add to the note (1) that it is here we are assuming that $xge-1$ in order to have a correct inequality.
– gimusi
Jul 28 at 22:06
@gimusi: the problem statement says $x>1$, which is stronger than $xge-1$.
– Yves Daoust
Jul 28 at 22:07
@gimusi: the problem statement says $x>1$, which is stronger than $xge-1$.
– Yves Daoust
Jul 28 at 22:07
Yes okay, but since you presented a complete proof, my suggestion is to add this important point which can be not simple to be appreciated by a student facing for the first time such kind of proof.
– gimusi
Jul 28 at 22:12
Yes okay, but since you presented a complete proof, my suggestion is to add this important point which can be not simple to be appreciated by a student facing for the first time such kind of proof.
– gimusi
Jul 28 at 22:12
@gimusi: no, I am sticking to the problem as stated. I don't want to clutter the answer with distracting details.
– Yves Daoust
Jul 28 at 22:15
@gimusi: no, I am sticking to the problem as stated. I don't want to clutter the answer with distracting details.
– Yves Daoust
Jul 28 at 22:15
As you like, it was only a suggestion to improve your good answer.
– gimusi
Jul 28 at 22:16
As you like, it was only a suggestion to improve your good answer.
– gimusi
Jul 28 at 22:16
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2865562%2finduction-proof-verification-via-binomial-theorem%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
Are you doing the induction on $n$ or on $k$? Also is the question exactly like that? You sure it isn't with both $n$ or $k$? I don't think that holds for every $n$ for a fixed $k$... Assuming $k = n$ there is a mistake on the induction step: You were supposed to also write $k+1$ on the place of $k$ on the left-hand side...
– karlabos
Jul 28 at 20:53
1
You should correct the statement in your text according to the indication given. Note also that $x$ is a real number and that the inequality holds for $x ge-1$. Refer to en.m.wikipedia.org/wiki/Bernoulli%27s_inequality for any other information.
– gimusi
Jul 28 at 22:15