Proof by mathematical induction

[Zelda22]

I starting to learn about mathematical induction, and I'm not sure if my answers are correct. Please help.

Here is the question, my answers are in red. Thank you.


Complete the following proof by mathematical induction that, for all n in W such that n >= 2, 3 ^ n > 2 ^ (n + 1)

We proceed by mathematical induction and begin by establishing the base of the induction.

3^ 2 = 9 > 8 =2^ 2+1

We see that 3 ^ n > 2 ^ (n + 1) when n=2.

Moving on to the induction step, we suppose that m in W is such that m >= 2
and as our induction hypothesis, we take the assumption that 3^m > 2 ^ (m + 1)
Noting that 3m+is the product of one more 3 than 3 ^m+1 and that 2 ^ (m + 2) is the product of one more 2 than 2 ^ (m + 1)

We calculate as follows:
2 ^ (m + 1) + 1 = 2 * 2 ^ (m + 1);
= 2^ m+1 +2^ m+1
<3^ m +2^ m+1 by the induction hypothesis and additive monotonicity
<3 ^ m + 3 ^ (m + 1) by the induction hypothesis and additive monotonicity
< 3 ^ m + 3 ^ m + 3 ^ m by order in W since 3^ m is in N
= 3*3^ m
=3^ m+1

We have shown that 3 ^ 2 > 2 ^ (2 + 1) and that, for all m in W such that m >= 2, if * 3 ^ m > 2 ^ (m + 1)
then 3 ^ (m + 1) > 2 ^ (m + 1) + 1
We may therefore conclude by mathematical induction that, for all n in W such that n >= 2; 3 ^ n > 2 ^ (n + 1)

 

[JeffM]

qI starting to learn about mathematical induction, and I'm not sure if my answers are correct. Please help.

Here is the question, my answers are in red. Thank you.


Complete the following proof by mathematical induction that, for all n in W such that n >= 2, 3 ^ n > 2 ^ (n + 1)

We proceed by mathematical induction and begin by establishing the base of the induction.

3^ 2 = 9 > 8 =2^ 2+1

We see that 3 ^ n > 2 ^ (n + 1) when n=2.

Moving on to the induction step, we suppose that m in W is such that m >= 2
and as our induction hypothesis, we take the assumption that 3^m > 2 ^ (m + 1)
Noting that 3m+is the product of one more 3 than 3 ^m+1 and that 2 ^ (m + 2) is the product of one more 2 than 2 ^ (m + 1)

We calculate as follows:
2 ^ (m + 1) + 1 = 2 * 2 ^ (m + 1);
= 2^ m+1 +2^ m+1
<3^ m +2^ m+1 by the induction hypothesis and additive monotonicity
<3 ^ m + 3 ^ (m + 1) by the induction hypothesis and additive monotonicity
< 3 ^ m + 3 ^ m + 3 ^ m by order in W since 3^ m is in N
= 3*3^ m
=3^ m+1

We have shown that 3 ^ 2 > 2 ^ (2 + 1) and that, for all m in W such that m >= 2, if * 3 ^ m > 2 ^ (m + 1)
then 3 ^ (m + 1) > 2 ^ (m + 1) + 1
We may therefore conclude by mathematical induction that, for all n in W such that n >= 2; 3 ^ n > 2 ^ (n + 1)

I see several errors.

Yes, it is true that [imath]2^{(2+1)} = 8 < 9 = 3^2.[/imath]

Thus, it is obvious that there is at least one integer n such that n [imath]\ge[/imath] 2 and [imath]0 < 2^{(n+1)} < 3^n[/imath].

[math]\text {Let } m \text { be an arbitrary one of those integers.}\\ \therefore \ 0 < 2^{(m+1)} < 3^m. [/math]
You seem to be on the track up to here.

You then say 2^(m+1) + 1, which is obviously an odd number, is equal to
2^m + 1 + 2^m + 1 =
2 * 2^m + 2, which is clearly an even number. Even and odd numbers are never equal. The problem here (aside from forgetting PEMDAS) is that you want to see what happens when you add 1 to m rather than adding 1 just any old place. After this error you wander around in a fog.

[math]0 < 2^{(m + 1)} < 3^m \implies 0 < 2 * 2^{(m+1)} < 2 * 3^m. [/math]
Do you buy that?

[math]\text {But } 0 < 2 * 2^{(m+1)} < 2 * 3^m \implies 0 < 2 * 2^{(m+1)} < 3 * 3^m \implies\\ 2^{\{(m+1)+1\}} < 3^{(m+1)}.[/math]
And this is what we want to show: the pattern replicates. So if it is true for m = 2 ( and it is), then it is true for m = 3, which makes it true for m = 4, and so on forever.

Clearer now?

 

[Zelda22]

I see several errors.

Yes, it is true that [imath]2^{(2+1)} = 8 < 9 = 3^2.[/imath]

Thus, it is obvious that there is at least one integer n such that n [imath]\ge[/imath] 2 and [imath]0 < 2^{(n+1)} < 3^n[/imath].

[math]\text {Let } m \text { be an arbitrary one of those integers.}\\ \therefore \ 0 < 2^{(m+1)} < 3^m. [/math]
You seem to be on the track up to here.

You then say 2^(m+1) + 1, which is obviously an odd number, is equal to
2^m + 1 + 2^m + 1 =
2 * 2^m + 2, which is clearly an even number. Even and odd numbers are never equal. The problem here (aside from forgetting PEMDAS) is that you want to see what happens when you add 1 to m rather than adding 1 just any old place. After this error you wander around in a fog.

[math]0 < 2^{(m + 1)} < 3^m \implies 0 < 2 * 2^{(m+1)} < 2 * 3^m. [/math]
Do you buy that?

[math]\text {But } 0 < 2 * 2^{(m+1)} < 2 * 3^m \implies 0 < 2 * 2^{(m+1)} < 3 * 3^m \implies\\ 2^{\{(m+1)+1\}} < 3^{(m+1)}.[/math]
And this is what we want to show: the pattern replicates. So if it is true for m = 2 ( and it is), then it is true for m = 3, which makes it true for m = 4, and so on forever.

Clearer now?

so what will be the correct answer?

 

[Zelda22]

so what will be the correct answer?

I'm confused

2^(m+1)+1 = 2 . 2^m+1 (for m=2)
2^(2+1) +1 = 2* 2^ 2+1
2^ 4 = 2* 2^3
16 = 2* 8
16=16

then I have

2^(m+1)+1 < 3^m + 2^m+1 (for m=2)
16<17

2^(m+1)+1 < 3^m +2^m +2^m
16< 3^2 + 2^2 + 2^2
16< 9 + 4 + 4
16<17

What would be your answers for the blanks?

 

[Dr.Peterson]

I'm confused

2^((m+1)+1) = 2 . 2^(m+1) (for m=2)
2^((2+1) +1) = 2* 2^(2+1)
2^ 4 = 2* 2^3
16 = 2* 8
16=16

then I have

2^((m+1)+1) < 3^m + 2^(m+1) (for m=2)
16<17

2^((m+1)+1) < 3^m +2^m +2^m
16< 3^2 + 2^2 + 2^2
16< 9 + 4 + 4
16<17

What would be your answers for the blanks?

First, please use parentheses as needed, so we can read what you write correctly. I have added them above.

But did you look carefully through your work to find errors? Look here:

​

Fix that error, and change whatever else might have to be changed as a result.

 

[JeffM]

Please review PEMDAS.

2^(m+1) + 1 means [imath]2^{(m+1)} + 1 \ne 2 * 2^{(m+1)}[/imath].

(m+1) and m are EXPONENTS. You want to add 1 to the exponents.

[math]2^{\{(m+1)+ 1\}} = 2 * 2^{(m+1)} < 2 * 3^m.[/math]
That is the key step. What justifies it?

That reduces to

[math]2^{\{(m+1)+1} < 2 * 3^m \implies 2^{\{(m+1)+1\}} < 3 * 3^m.[/math]
What justifies that?

[math]\therefore \ 2^{\{(m+1)+1\}} < 3^{(m+1)}.[/math]
You are done.

Here is a tip for doing proofs by induction.

Once you write down your so-called induction hypothesis, IMMEDIATELY write down what the corresponding statement would look like on a separate scrap of paper. That is the conclusion you are trying to reach. So using m, you start with

[math]m \text { is an integer such that } m \ge 2 \text { and } 2^{(m+1)} < 3^m.[/math]
The corresponding statement for m + 1 is

[math]2^{\{(m+1)+1\}} < 3^{(m+1)}.[/math]
Now you know where you want to end up.

 

[pka]

You have correctly done the base case.
Now start with the assumption: for [imath]m>2[/imath] it is true that [imath]3^m>2^{m+1}[/imath].
Based that, look at [imath]3^{m+1}[/imath]. See [imath]3^{m+1}=3\cdot 3^m>3\cdot 2^{m+1}>2\cdot 2^{m+1}=2^{(m+1)+1}[/imath]
That proves the case for [imath]m+1[/imath].


[imath][/imath][imath][/imath][imath][/imath]

 

[Zelda22]

First, please use parentheses as needed, so we can read what you write correctly. I have added them above.

But did you look carefully through your work to find errors? Look here:

View attachment 32785​

Fix that error, and change whatever else might have to be changed as a result.

< 3^m +2^(m+1) by the induction hypothesis and additive monotonicity
< 3^m + 2^m + 2^m) by the induction hypothesis and additive monotonicity
< 3^m + 3^m + 3^m by order in W since 3^ m is in N
= 3*3^m
=3^ (m+1)

Like this?

 

[Dr.Peterson]

< 3^m +2^(m+1) ............... by the induction hypothesis and additive monotonicity
< 3^m + 2^m + 2^m ....... by the induction hypothesis and additive monotonicity
< 3^m + 3^m + 3^m ........ by order in W since 3^ m is in N
= 3*3^m
=3^ (m+1)

Like this?

I don't think that's what they intend; the step from the first line to the second doesn't use either the induction hypothesis or "additive monotonicity".

I think the intended second line would be "< 3^m + 3^m". Do you see how both reasons stated apply now?

In the third line, they have used the fact they call "order in W", by adding a natural number 3^m, which increases the value.

It can be tricky to fill in blanks in an already-written proof (which is why what others are doing is not very helpful to you, even though they may have very good ideas!) You're trying to guess exactly what someone else has in mind, based on hints, rather than just do it in a valid (and maybe even better) way. I rather dislike this sort of assignment for that reason. On the other hand, this does force you to think carefully about what the "reasons" mean.

 

[Zelda22]

I don't think that's what they intend; the step from the first line to the second doesn't use either the induction hypothesis or "additive monotonicity".

I think the intended second line would be "< 3^m + 3^m". Do you see how both reasons stated apply now?
"
In the third line, they have used the fact they call "order in W", by adding a natural number 3^m, which increases the value.

It can be tricky to fill in blanks in an already-written proof (which is why what others are doing is not very helpful to you, even though they may have very good ideas!) You're trying to guess exactly what someone else has in mind, based on hints, rather than just do it in a valid (and maybe even better) way. I rather dislike this sort of assignment for that reason. On the other hand, this does force you to think carefully about what the "reasons" mean.

Thank you!

second line would be "< 3^m + 3^m". Do you see how both reasons stated apply now?

Could you explain it to me, please?
is since that 3^m > 2 ^ (m + 1), I can replace 2^(m+1) with 3^m?

2 ^((m + 1) + 1) = 2 * 2 ^ (m + 1);
= 2^ m+1 +2^ m+1

< 3^m +2^(m+1) ............... by the induction hypothesis and additive monotonicity
< 3^m + 3^m ....... by the induction hypothesis and additive monotonicity
< 3^m + 3^m + 3^m ........ by order in W since 3^ m is in N
= 3*3^m
=3^ (m+1)

does the rest look ok to you?

 

[Dr.Peterson]

Could you explain it to me, please?
is since that 3^m > 2 ^ (m + 1), I can replace 2^(m+1) with 3^m?

Not strictly "replace", but yes:

= 2^(m+1) +2^(m+1)

< 3^m +2^(m+1)

because the induction hypothesis says that 2^(m+1) < 3^m, and additive monotonicity says that we can add 2^(m+1) to both sides.

< 3^m +2^(m+1)
< 3^m + 3^m

for exactly the same reason, but this time adding 3^m to both sides.