Induction --> inequalities (1 Viewer)

[haboozin]

Prove this inequality by mathematical induction...


3ⁿ > n²
n >= 2 (and also for n = 0 and n = 1)



.... i suck at intequalities :'(
any other induction is super easy... just inequalities grrrr

 

[Jago]

Okay, here's my (incredibly bad) method for this q, if you have a better, neater method please tell me:

3ⁿ > n² (n >= 2)

prove true for n = 0

1 > 0. therefore true for n = 0

prove true for n = 1

3 > 1. therefore true for n = 1

(you wouldn't usually do the above but i'm just making it easier for myself later on, imo)

prove true for n = 2

9 > 4. therefore true for n = 2
now assume true for n = k


3^k > k² <------------------ a

prove true for n = k+1

now, from a

3^k > k²

3(3^k) > 3.k², that is:

3^(k+1) > 3k²

3^(k+1) > k² + 2k², here's where it gets retarded

3^(k+1) > k² + 2k + 1 (since 2k² > 2k + 1 for k >= 2)

3^(k+1) > (k+1)²

then you can conclude it.

 

[BlackJack]

If you want to justify 2k² > 2k + 1:

Consider 2k² - 2k - 1.
= (k-1)² + k² - 2.
Note (k-1)² >= 0 always, & k² - 2 > 0 for k >= 2
.'. 2k² - 2k - 1 > 0 for k >=2, (by above note)
.'. 2k² > 2k + 1.

btw, that would be the way they'd like you to do it, since they say the induction proof only works for k >= 2.

 

[rama_v]

.... i suck at intequalities :'(
any other induction is super easy... just inequalities grrrr

I used to hate inequalities as well....I soon realised the reason was I wasnt as proficient with indices as I should be - make sure you can maniplate them really well, do the exercises in the cambridge 2 unit book on indices (just before the exercise on logs) if you have to - it worked for me, these questions are really easy for me now

 

[Jago]

If you want to justify 2k² > 2k + 1:

Consider 2k² - 2k - 1.
= (k-1)² + k² - 2.
Note (k-1)² >= 0 always, & k² - 2 > 0 for k >= 2
.'. 2k² - 2k - 1 > 0 for k >=2, (by above note)
.'. 2k² > 2k + 1.

btw, that would be the way they'd like you to do it, since they say the induction proof only works for k >= 2.

ah thanks for that, it's less retarded now.

 

[MuffinMan]

man test n=2 first
cause ur q is n> or = to 2
so its 2,3,4,5,6,7,....... n
so instead of testing n=1 is true u test n=2 is true

 

[haboozin]

I used to hate inequalities as well....I soon realised the reason was I wasnt as proficient with indices as I should be - make sure you can maniplate them really well, do the exercises in the cambridge 2 unit book on indices (just before the exercise on logs) if you have to - it worked for me, these questions are really easy for me now

welll thats the text book i dont have

I have Maths in focus ext 1 , cambridge ext 1 book, cambridge 4unit, patel ext2, fitzpatrick ext2

no 2unit book, becides induction is a 3unit topic... why the hell is it in 2unit book....

 

[thunderdax]

I think what he means is learn the indice laws, from 2 unit, really well before doing this type of induction.

 

[paper cup]

well it seems you don't need my help any longer jason

 

[Jago]

do you have another method of solving?

 

[RyddeckerSMP]

Inequality induction, while being in the 3unit course, has never been tested in 3unit, and is usually seen as a 4unit question..... just thought you should know...

 

[MuffinMan]

cant count on that...

 

[Estel]

That's untrue.
It has been tested in 3u.

I can't be bothered getting my book of past papers out but it is most definitely in there. I think especially in the 80's.

 

[nick1048]

seeing as those this is the 'induction' section, can anyone have a crack at these questions?:

1) (x + y)^n > x^n + y^n

2) 12^n > 7^n + 5^n , for n>=2

3) x^n - 1 is divisible by x - 1

4) (1 + x)^n >= 1 + nx , x > 0

5) n^2 - 11n + 30 >= 0 , n >= 1

Sorry there are so many, I'm good with summation style and not bad with divisiblity, but these questions stump me. Thanks in advance for your assistance.

 

[Jago]

I have the book of past HSC papers all the way back to 1986, it is not in that book but just because it isn't in the HSC doesn't mean it can't be in the internal exams.

1. L.H.S.
= ( x + y )^n
= x^n + y^n + 2xy
= R.H.S. + 2xy

 

[Estel]

1) (x + y)^n > x^n + y^n

(x+y)^(k+1) - x^(k+1) - y^(k+1)
= (x+y)(x^k+y^k) - x^(k+1) - y^(k+1)... by assumption and the rest is elementary

2) 12^n > 7^n + 5^n , for n>=2

12^(k+1) - 7^(k+1) - 5^(k+1)
> 12.7^k + 12.5^k - 7.7^k - 5.5^k by assumption and the rest is obvious.

3) x^n - 1 is divisible by x - 1
x^(k+1) -1
= x.(x^k-1)+x-1
=x.(x-1)m + x-1 by assumption and it's easy...

4) (1 + x)^n >= 1 + nx , x > 0
(1+x)^(k+1) - 1 - (k+1)x
>= (1+x)(1+kx) - 1 - (k+1)x and you can figure the rest...

5) n^2 - 11n + 30 >= 0 , n >= 1
test n = 0, 1, 2, 3, 4, 5
prove by induction for n>=6

edit: my post reads quite patronisingly doesn't it

 

[FD3S-R]

can someone help with this:

2^n > n^2 for n>4

 

[Will Hunting]

Sure, but check my post on integration in this forum. I want somebody to confirm what I've written.

1. Prove for n = 5
LHS = 2^5 = 32
RHS = 5^2 = 25
Since LHS > RHS, true for n = 5

2. Assume true for n = k
i.e. 2^k > k^2

3. Prove for n = k + 1
i.e. 2^(k + 1) > (k + 1)^2
2^(k+1) > k^2 + 2k + 1 (Expanding)

2^(k + 1) = 2(2^k)

2(2^k) > 2k^2 (Since 2^k > k^2)

Now, you need to show that 2k^2 > k^2 + 2k + 1 to prove for n = k + 1
You do this by solving the inequality, k^2 - 2k - 1 <= 0 and showing that the solutions do not satisfy the condition, k > 4, k integral. This means that k^2 - 2k - 1 MUST > 0 (The result you're after).

k^2 - 2k - 1 <= 0 gives 1 - sqrt2 <= k <= 1 + sqrt2
Therefore, k^2 - 2k - 1 > 0 for k > 4, k integral
i.e. 2k^2 > k^2 + 2k + 1

2(2^k) > k^2 + 2k + 1 (Since k^2 - 2k - 1 <= 0 factorises for no integral k > 4)
2^(k + 1) > k^2 + 2k + 1

4. Since shown true for n = 5, and proven true for n = k + 1, assuming true for n = k, statement is true for all integral n > 4.