[RESOLVED] I need to prove something.

[CornedBee]

This is a school assignment, so all the people that don't like to help at such problems are warned.

I have to use complete deduction to prove that
3n + 2^n < 3^n
is true for every n >= 3.

I can prove that it is true for n0 = 3 (surprise), then I tried to prove that the difference:
(3ni + 2^ni) - (3ni-1 + 2^ni-1) < (3^ni) - (3^ni-1)

I end up with
18 + (3*2^ni) < 4*3^ni
but I can't get the n down from the powers. I can't use logarithm because of the addition.

Anyone knows how to solve this, or knows a completly different better solution? It has to use deduction though.

[bugzpodder]

well i ended up with something different.

i get:

3+2^k<2*3^k

which is true for all k>3

[CornedBee]

But how do I prove that? It's just a reformulation of the original problem, right?

[sql_lall]

You have proved:
3n + 2^n < 3^n (by putting n = 3)

Now all you have to show is:
3(n+1) + 2^(n+1) < 3^(n+1) (where n >3)
OR:

3n + 3 +2^(n+1) < 3^n * 3

_____3n + 2^n < 3^n (shown for n = 3)
____________3<3^n (always true when n >3)
______2^(n+1) < 3^n (always true when n >3)
--------------------------------------
3n+3 + 2^(n+1) < 3^n *3


(i'm not exactly sure about this, but it may be right. ALso, this is induction, not deduction, but i am guessing they are similar??)

[krtxmrtz]

If you assume that,

3ⁿ > 2ⁿ + 3n

holds up to n, then if you can prove it for n+1, you will have proved it for any positive integer (>3).

Multiply both sides of the above inequality by 3:

3ⁿ⁺¹ > 3( 2ⁿ ) + 3(3n) > 2( 2ⁿ ) + 3(3n) = 2ⁿ⁺¹ + 9n > 2ⁿ⁺¹ + 3(n +1)

and there you go!

The last step follows from the fact that 9n > 3(n+1) or equivalently 3n > n+1 for all n >=1.

[CornedBee]

sql: Yes, I meant induction, I just used the wrong word.

Thanks to you all, I understand none of your proofs, mainly because I don't quite get how they are written. Thanks anyway, by now I've solved the problem by other means.

krt: How did you get those numbers up?

[krtxmrtz]

Originally posted by CornedBee
krt: How did you get those numbers up?

If you mean the superindices, use the "[sup]" tag.

[CornedBee]

^Thanks

[DiGiTaIErRoR]

n could = 2.2

[krtxmrtz]

2.2 is not an integer. (Even so, for n=2.2 the inequality is still true!)

[CornedBee]

Gotta prove it for integers. But it's now long resolved, thanks anyway.