Proof by Induction - Inequalities (1 Viewer)

[distinction]

Can anyone help me with the following: Proof my Mathematical Induction 2^k < 3^n for n≥1 (Where n is a positive integer), moreover I need general assistance with Induction of Inequalities as I can't really grasp how you can just sub in inequalities, and the general steps and approach.

 

[rolpsy]

okay I'll assume you mean prove 2ⁿ < 3ⁿ.

First note that you don't need induction to prove this – you can simply raise both sides of 2 < 3 to the power of n (as both sides are greater than zero & xⁿ is strictly increasing for x > 0).

However, using induction:

1. The base case is obvious as 2¹ < 3¹.

2. Let the induction hypothesis be 2^k < 3^k for some integer k.

3. Consider



Therefore the statement is true for all positive integers n.


Induction with inequalities can be difficult. I suppose it's just practise..
Become familiar with rules of inequalities and ways you can get the answer, e.g., in this example we needed to get a 3 from 2, so we used 2 < 3. You can do the same with things such as n < n + 1, n < 2n (n > 0), etc.
You might find it easier to prove LHS - RHS > 0 and conclude that LHS > RHS.

If you have any further questions feel free to ask.

 

[distinction]

okay I'll assume you mean prove 2ⁿ < 3ⁿ.

First note that you don't need induction to prove this – you can simply raise both sides of 2 < 3 to the power of n (as both sides are greater than zero & xⁿ is strictly increasing for x > 0).

However, using induction:

1. The base case is obvious as 2¹ < 3¹.

2. Let the induction hypothesis be 2^k < 3^k for some integer k.

3. Consider



Therefore the statement is true for all positive integers n.


Induction with inequalities can be difficult. I suppose it's just practise..
Become familiar with rules of inequalities and ways you can get the answer, e.g., in this example we needed to get a 3 from 2, so we used 2 < 3. You can do the same with things such as n < n + 1, n < 2n (n > 0), etc.
You might find it easier to prove LHS - RHS > 0 and conclude that LHS > RHS.

If you have any further questions feel free to ask.

Dont really understand the 3rd line, as to how you can just substitute 2 for 3

 

[rolpsy]

Dont really understand the 3rd line, as to how you can just substitute 2 for 3

okay so you're concerned about this step:



I want to emphasise the 'less than'; the 3rd line is less than the 2nd (not equal to), allowing us to 'replace' the 2.



hopefully that clears things up..

this sort of stuff is very important.
it is vital that you understand it

 

[distinction]

okay so you're concerned about this step:



I want to emphasise the 'less than'; the 3rd line is less than the 2nd (not equal to), allowing us to 'replace' the 2.



hopefully that clears things up..

this sort of stuff is very important.
it is vital that you understand it

Thanks well i tried another for n≥4

(Giving up on latex)

1) Basis Case:
2(4)+2 < 2^4 gives 10 < 16
Thus basis case holds true for n=4

2) Induction hyp where 2k+2<2^k where k is a +ve integer

3) 2^k+1 = 2^k x k
> (2k+2)2 (By induction hyp)
> 4k+4

 

[rolpsy]

It helps a lot for the 3rd step if you state what you wish to prove, in this case:



We then work the RHS (since it will be easier to apply the hypothesis)



Being able to notice these things takes practise.


Now, I'm going to be pedantic and highlight a mistake..

Thanks well i tried another for n≥4
3) 2^k+1 = 2^k x k
> (2k+2)2 (By induction hyp)
> 4k+4

Note that (2k+2)2 = 4k + 4.. the sign should be an =
This was the point I wanted to emphasise (be careful with the signs)

 

[distinction]

It helps a lot for the 3rd step if you state what you wish to prove, in this case:



We then work the RHS (since it will be easier to apply the hypothesis)



Being able to notice these things takes practise.


Now, I'm going to be pedantic and highlight a mistake..



Note that (2k+2)2 = 4k + 4.. the sign should be an =
This was the point I wanted to emphasise (be careful with the signs)

Thanks for the assistance, your layout kind of differs from my schools, but thanks regardless

 

[D94]

Prove 2ⁿ < 3ⁿ

Prove true for n=1: clearly 2¹ < 3¹

Assume true for n=k: 2^k < 3^k
This can be rewritten as 3^k - 2^k > 0 (this is our assumption which is > 0)

Prove true for n=k+1: 2^k+1 < 3^k+1

Now, to solve:
3^k+1 - 2^k+1
=3*3^k - 2*2^k
=3*3^k - 3*2^k + 2^k (this is just rewriting 2*2^k as - 3*2^k + 2^k)
=3(3^k - 2^k) + 2^k

Now, from our assumption, 3(3^k - 2^k) > 0 since 3*(assumption which is > 0) is > 0.
And 2^k is clearly > 0 for k > 0

Hence, 3(3^k - 2^k) + 2^k > 0
Therefore, 3^k+1 - 2^k+1 > 0

Therefore, 2^k < 3^k by proof of mathematical induction, k > 0.