[mutei]

prove by induction that n! > 2^n for n>3

[melanie.albury]

Hi,

Proof by induction works in 2 steps.

First you must show that the expression is true for the initial value, which in your case is n = 4 (since n > 3).

Secondly, assume that the expression is true for n = k, then try to prove it is true for n = k + 1.

So for your problem:

Prove that n! > 2^n for all n > 3.

1. check for n = 4:
4! = 24 > 16 = 2^4 so this is OK.

2. assume true for n = k
i.e.. Assume that k! > 2^k.
Now we want to prove that it is true for k+1
i.e.. Want to prove (k+1)! > 2^(k+1)

(k+1)! = (k+1) * k! > (k+1) * 2^k (since we have assumed k! > 2^k)

Now k+1 > 4 (since k>3) so k+1 > 2
so (k+1) * 2^k > 2 * 2^k = 2^(k+1)

Put this altogether to get (k+1)! > 2^(k+1) which is what we wanted to prove.

so 1 & 2 are true, hence by the principles of mathematical induction n! > 2^n for all n>3.

Hope this helps. If there's anything you don't understand let me know. Usually questions like this have that little trick at the end, it just takes a little bit of fiddling around with algebra.

;D

[kruthi]

Hi ,

Could you Please prove me this solution


Determine by induction all the positive integers valuesof n for which n^3>2^n .prove your claim by mathematical induction.

Could you Please help me ASAP

[CroCivic91]

Let's make a table of values:

 n | n^3 | 2^n
---------------
 1 |  1  |  2
 2 |  8  |  4
 3 | 27  |  8
 4 | 64  |  16
 5 | 125 |  32

In that table we see that n^3 should be > 2^n for every n which is > 1

Let's prove it by induction:
Is it true for 2?
2^3 = 8 > 4 = 2^2
It is.

Presume that n^3 > 2^n for all whole numbers <= n

Now let's see what is the deal with (n+1)^3 and 2^(n+1)
(n+1)^3 = n^3 + 3 > 2^n + 3 (because n^3 > 2^n)
(n+1)^3 > 2^n + 3 > 2^n + 2 (because 3 > 2)
(n+1)^3 > 2^n + 2 = 2^(n+1)

So, we have proved that if n^3 > 2^n for some n, then (n+1)^3 > 2^(n+1), and since n^3 > 2^n for n=2, then, by the principle of mathematical induction, it is true for every whole number n which is larger than or equal to 2.

[dmatos]

Your math is a bit off, even if your method is correct:

(n+1)^3 = n^3 + 3n^2 + 3n + 1
Also, 2^(n+1) = 2*2^n, not 2^n + 2

There is also an upper bound on this inequality. I believe you have to show it is true for positive integers between 2 and 9 inclusive (10^3 = 1000, 2^10 = 1024).

I think the best way to go about this is to enumerate for all values of n up to 10, then postulate that it is not true for n>=10, and prove this by induction. To prove this, you must in fact prove the converse, i.e. that for n>=10, 2^n > n^3. The first step is simple, show that it is true for n=10. Then assume it's true for all k<=n, show that it's true for k=n+1:

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

How does this compare to 2*n^3? Take the cube root of both:

cubert(2)*n compared to n+1
(cubert(2)-1)*n copared to 1
n compared to 1/(cubert(2)-1)
n compared to approx 3.8473

This means that if n> 3.8473, 2n^3 > (n+1)^3
therefore, for n>= 10:
2^(n+1) = 2*2^n > 2n^3 (inductive assumption)
> (n+1)^3, or:
2^(n+1) > (n+1)^3

We've now proved that 2^n > n^3 for n>= 10 by induction.

Tah-dah!

[CroCivic91]

Oh my God, my math really does suck.

Geez, where was I looking? I'll stop giving answers here for a while, because I'm quite ashamed right now :o

[heris]

let a>=2 prove that the sequence
x1= a^(1/2)
and