Induction question with logarithms

[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 I am having problems solving for k, since i have it on both sides. I just need someone to gimme a slight push :)

 

[HallsofIvy]

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

So...

2^k > k^2 /log base 2

You mean take the logarithm, base 2, of both sides?

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

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

Generally speaking, equations that involve the unknown number both "inside" and "outside" a transcendental function, such as log₂(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 2¹> 1²?

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

 

[epenguin]

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) 2ⁿ >= n² 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.

 

[Petkovsky]

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

 

[HallsofIvy]

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