2

So, I want to prove that $x^k$ is less than $k^x$ for any $x > k$. $x$ and $k$ are both integers.

My first approach was an induction over $k$, given that the numbers are integers. I also considered the facts that given a certain $k$, $x^k$ grows slower than $k^x$ from a certain number (the limit of the division of both functions proves it). And of course both functions are always increasing. But I don't seem to be able to pull this through.

EDIT: Of course I want to prove this for any $x$ and $k$ bigger than a certain number (I think it's $k$ = 3 and $x$ > $k$ but I'm not sure)

Setzer22
  • 237
  • 1
    There are some exceptions, such as $3^2$ and $2^3$. Perhaps you should make a list of obvious exceptions first. Certainly, you don't want $k=1$ either. – user121173 Jan 14 '14 at 11:25
  • Are you sure? When $x=2,k=1$, $2^1\gt 1^2$. – mathlove Jan 14 '14 at 11:25
  • Oh, of course, I just missed the part that x and k should be bigger than a given number. I'm editing it, thank you! – Setzer22 Jan 14 '14 at 11:28

4 Answers4

2

Hint: The relevant case is $x>k>1$. Note that $\log_kx>1$ and \begin{align} x^k< k^x \Longleftrightarrow & \log_k(x^k)<\log_k(k^x) \\ \Longleftrightarrow & k\log_kx<x \log_k(k) \\ \Longleftrightarrow & \frac{k}{x} <\frac{\log_k(k)}{\log_k(x)}=\frac{1}{\log_k(x)}<1 \\ \end{align}

Elias Costa
  • 14,658
2

Notice for any $x \ge k \ge 3$, we have

$$\frac{(x+1)^k}{k^{x+1}}\bigg/\frac{x^k}{k^x} = \frac{(1+\frac{1}{x})^k}{k} \le \frac{(1+\frac{1}{k})^k}{k} \le \frac{e}{k} < 1$$

This implies for any $x > k$,

$$\frac{x^k}{k^x} \le \left(\frac{e}{k}\right) \frac{(x-1)^k}{k^{x-1}} \le \left(\frac{e}{k}\right)^2 \frac{(x-2)^k}{k^{x-2}} \le \cdots < \left(\frac{e}{k}\right)^{x-k} \frac{k^k}{k^k} = \left(\frac{e}{k}\right)^{x-k}< 1$$

and hence $x^k < k^x$.

achille hui
  • 122,701
  • This is great, I get most of it, I just don't understand why you can say at the first line that (1 + 1/k)^k < e. I'm testing with numbers on my calculator and the intuition I have is that lim(1+1/k)^k when k->infinity is the number e. Am i right? – Setzer22 Jan 14 '14 at 13:37
  • @Setzer22 One definition of $e$ is the value of the power series $\sum_{k=0}^{\infty} \frac{1}{k!}$. If you expand $(1+\frac{1}{k})^k$ by binomial theorem, you will notice it is smaller than the first $k^{th}$ term of the power series. This implies $(1+\frac{1}{k})^k < e$ for any positive integer $k$. BTW, $\lim_{k\to\infty}( 1+\frac{1}{k})^k$ does equal to $e$. – achille hui Jan 14 '14 at 13:47
  • Ok, I mark this as the answer because it has been the most clear proof to me (as well as elegant). Sorry I can't upvote (I lack reputation as I'm new to the website...). – Setzer22 Jan 14 '14 at 14:01
0

What I think you want to prove is that a polynomial quantity is smaller than an exponential quantity. This is intro computer science. Have a look at

http://en.wikipedia.org/wiki/Big_O_notation

and

Working with the ~ (tilde) notation (asymptotic analysis)

Community
  • 1
Syd Kerckhove
  • 705
  • Well, that's assymptotically bigger, and yes, I had the computer science approach in mind. But I'm not good enough with proving that k^x > x^k for any given k, with a big enough x, when x tends to bigger and bigger values, this is of course a matter of asymptomatic growth and it's already obvious. But I'm not talking about an x as big as I want, I want to see the extreme case of k being just smaller than x (even if it's slightly smaller, like x = k+1), I want to determine from which certain k this is true. If is there such number. – Setzer22 Jan 14 '14 at 12:25
0

Graphing f(x)= x^(1/x) shows that it appears to reach a max value at about 2.7183 and decreases after that. The derivative of f(x)=x^(1/x) is rather complicated [x^{1/x}][1/x^2](1-ln x) Set it equal to zero. The parts in brackets will never be exactly zero for x > 0. The last factor, set equal to zero is 1-ln x = 0 which gives you x = e. The curve has one maximum value at x = e. After that it is a decreasing curve approaching 1 as an asymptote. Since it is decreasing after x = e, this proves the statement x^(1/x) < k^(1/k) for x > k > e. This proves x^k < k^x.

MathBob
  • 169