Induction question with logarithms

1. Sep 27, 2008

Petkovsky

I have to prove that 2^n > n^2 for every n>=5

So...

2^k > k^2 /log base 2

log2(2^k) > log2(k^2)
k*log2(2) > 2*log2(k)
k/2 > log2(k)

So i'm stuck here and im having problems solving for k, since i have it on both sides. I just need someone to gimme a slight push :)

2. Sep 27, 2008

HallsofIvy

Staff Emeritus
Re: Induction/logs

You mean take the logarithm, base 2, of both sides?
Generally speaking, equations that involve the unknown number both "inside" and "outside" a transcendental function, such as log2(x), cannot be solved algebraically. Even if you did "solve for k" how would that help you? You don't know that "2^k> k^2" to begin with. If you were doing an induction, and I see no sign of that here, you would be concerned with 2^(k+1)> (k+1)^2. I can see no good reason for introducing a logarithm.

To remind you of how induction works, you first prove that the statement is true for n= 1: is 21> 12?

If it is then you can assume that 2k> k2 for some k and try to prove that 2k+1> (k+1)2. Certainly 2k+1= 2(2k) so 2k+1> 2k2. How does that compare with (k+1)2= k2+ 2k+ 1? Can prove that k2> 2k+1? That is the same as k2- 2k> 1, k2-2k+ 1= (k-1)2> 2. Obviously, you will have to deal with the fact that this last inequality is not true for k= 1 or 2!

3. Sep 27, 2008

epenguin

Re: Induction/logs

I recommend - forget about the logs. Too clever almost.

And you have not started your proof like an induction proof anyway.

The first steps of an induction proof is always the same and almost writes itself, so on the model of any example you have seen, write out explicitly on the model of induction proofs you must have seen

'If (for some n>=5 but you can even leave that out at least for the moment) 2n >= n2 then that will be true for the next n if ...

( I am saying it informally)

and see what you can do with that.

Edit. I think while I was posting HOI has shownwhat I meant.

Except I would not start by proving it for n=1 as you are asked for n>=5, and in fact it is not true for n=3.

Last edited: Sep 27, 2008
4. Sep 28, 2008

Petkovsky

Re: Induction/logs

I had to do it myself actually, but thank you for solving it anyway.

5. Sep 28, 2008

HallsofIvy

Staff Emeritus
Re: Induction/logs

Good, it is far better for you to have done it yourself.