The key thing you need is that for n >= 3 the sequence of (n^1/n) is decreasing. You can get that pretty easily without logs.
Look at two consecutive terms: n^(1/n) and (n+1)^[1/(n+1)]. The ratio of the first to the second -- we want to prove that this is >1 -- is n^(1/n) / (n+1)^[1/(n+1)]. This is bigger than 1 iff its n(n+1)th power is; that is, iff n^(n+1) / (n+1)^n > 1. We can write this as n (n/(n+1))^n; so what we need is that (n/(n+1))^n > 1/n.
(Handwavily: we know that the LHS is about 1/e, so for n>=3 this should be good. But we want a proof and we're trying to do it without nontrivial analytic machinery.)
Actually, I prefer to write this as ((n+1)/n)^n < n, or (1+1/n)^n < n. Expand this with the binomial theorem: we get sum {0<=k<=n} of (n choose k) n^-k. And we have (n choose k) = n(n-1)...(n-k+1) / k! < n^k/k! so this is strictly less than sum {0<=k<=n} of 1/k!. And for k>0 we easily have k! >= 2^(k-1) so this sum is no bigger than 1 + 1 + 1/2 + 1/4 + 1/8 + etc. = 3.
So, the function on integers n -> n^1/n is decreasing for n >= 3. Now the proof goes through as before.
(Maybe there's a more thoroughly number-theory-ish way to do it by looking at prime factorizations, but when I try it that way it always seems to end up rather a mess.)
[EDITED to add:] But elsewhere in the discussion users bustermellotron and diffeomorphism give (very similar) neat number-theory-ish proofs, either of which is definitely a better proof than the one using the calculations above.
Look at two consecutive terms: n^(1/n) and (n+1)^[1/(n+1)]. The ratio of the first to the second -- we want to prove that this is >1 -- is n^(1/n) / (n+1)^[1/(n+1)]. This is bigger than 1 iff its n(n+1)th power is; that is, iff n^(n+1) / (n+1)^n > 1. We can write this as n (n/(n+1))^n; so what we need is that (n/(n+1))^n > 1/n.
(Handwavily: we know that the LHS is about 1/e, so for n>=3 this should be good. But we want a proof and we're trying to do it without nontrivial analytic machinery.)
Actually, I prefer to write this as ((n+1)/n)^n < n, or (1+1/n)^n < n. Expand this with the binomial theorem: we get sum {0<=k<=n} of (n choose k) n^-k. And we have (n choose k) = n(n-1)...(n-k+1) / k! < n^k/k! so this is strictly less than sum {0<=k<=n} of 1/k!. And for k>0 we easily have k! >= 2^(k-1) so this sum is no bigger than 1 + 1 + 1/2 + 1/4 + 1/8 + etc. = 3.
So, the function on integers n -> n^1/n is decreasing for n >= 3. Now the proof goes through as before.
(Maybe there's a more thoroughly number-theory-ish way to do it by looking at prime factorizations, but when I try it that way it always seems to end up rather a mess.)
[EDITED to add:] But elsewhere in the discussion users bustermellotron and diffeomorphism give (very similar) neat number-theory-ish proofs, either of which is definitely a better proof than the one using the calculations above.