induction logn<n?

Question

This is getting on my nerves- prove n>logn for all natural numbers by induction. I can do this, but you have to have log((n+1)/n)<1 which is generally true, but has to be verified for a particular base of logarithm. Anyone got a nice elegant proof of this?

Answer 1

log(1) = 0 <1
So true for n = 1

Assume true for n = k
ie logk < k

Then (k + 1) = (k) + 1
> log k + 1
= logk + log(base)
= log(base*k)
> log(k + 1) (base*k > k + 1 → base > (k + 1)/k = 1 + 1/k)

Therefore if true for n = k then true for n = k + 1

Well its true for n = 1 and therefore true for n = 2, 3, 4 .... all natural numbers n.

Answer 2

log(n) [log n]^2 < n^2
[log n]^2 < n^2 + 2n + 1 = (n+1)^2



Do something with squaring the log n < n and adding and subtracting enough to make a perfect square with the right side being (n+1)^2, play around thusly and you might get something...

Answer 3

f(n) = n
g(n) = logn

f(1) > g(1) .

f'(n) > g'(n) for all n >= 1

( f' ,g' the derivative )

thus f(n) > g(n).

todelidokie