# Proof through Induction with Inequality

1. Oct 23, 2007

### MitsuZero

1. The problem statement, all variables and given/known data

Original Problem Text:
http://img264.imageshack.us/img264/5882/problem3pn7.th.gif [Broken]

Prove that, if n $$\in$$ $$N$$ and n $$\geq$$ 2, then 2^(n^2) > n^(n).

2. Relevant equations

Some Hints:
*** (n-1)^(n-1) * 2^(n-1) = (2n - 2)^(n-1)
*** If n >= 2 then (2n - 2) >= n.
*** If n >= 1 then 2^(n) >= n.

3. The attempt at a solution

Using Induction:

For the base step, suppose that n = 2. This implies that 2^(2^2) = 16, and 2^(2)= 4, and 16 > 4, so the base step is proven true.
Suppose that n>2, and that the theorem has been proven for all smaller values of n.

Then we compute:
2^(n^2) > n^n
2^(n-1)^2 > (n-1)^(n-1)
***Multiply both sides by 2^(n-1)***
2^(n-1)^2 * 2^(n-1) > (n-1)^(n-1) * 2^(n-1)
2^(n-1)^2 * 2^(n-1) = 2^(n^2 - n) = 2^(n(n-1))
2^(n(n-1)) > (2n -2)^(n-1)
***Now here's the screwy part - I took the (n-1) root across the inequality. I have my doubts about the mathematical legality of such an operation. ***
2^(n) > 2n - 2
2n -2 $$\geq$$ n (since n $$\geq$$ 2)
2^(n) > n
2^(n^2) > n^(2)

Does this proof make any sense at all? Does it even remotely resemble a proof? I should point out that I'm using (n-1) in place of (n+1) because that's the way my professor did it.

Thanks a lot for any help!

Last edited by a moderator: May 3, 2017
2. Oct 23, 2007

### EnumaElish

I'd try to use all hints they gave; they are usually given for a reason.

3. Oct 23, 2007

### MitsuZero

I believe I used just about all the hints my professor gave. Though whether I used them correctly is questionable.

For the first hint I multiplied both sides by 2^(n-1) in order to fit the form he gave -- i.e.
2^(n-1)^2 * 2^(n-1) > (n-1)^(n-1) * 2^(n-1)

For the second hint, I got rid of the (n-1) power on both sides (which itself is a questionable move), which gave the form:
2^(n) > 2n - 2

And finally, for the third hint, I related 2n - 2 > n to 2^(n) > 2n -2 > n.

Thanks again.

4. Oct 24, 2007

### EnumaElish

You are starting with the correct premise but not ending up with 2^(n^2) > n^(n)

5. Oct 24, 2007

### NeoDevin

It seems that we can do this without induction, using only the third hint since ...

$$2^{n^2} = 2^{n\times n} = (2^n)^n$$

It also seems to work for the case $n = 1$