5
$\begingroup$

I aim to show that $$(n+1)^n<n^{(n+1)}$$ for all $n \geq 3$. I tried induction, but it didn't work. What should I do?

$\endgroup$
9
$\begingroup$

Assume for contradiction that at some point we have $$ (n-1)^n>n^{n-1},\text{ but } (n+1)^n\geq n^{n+1} $$ and multiply the two inequalities.

$\endgroup$
  • $\begingroup$ I couldn't get the trick. We obtain $(n^2-1)^n > n^{2n}$. Why in development of $ (n^2-1)^n$ the parcel $\sum_{k=1}^n(^n_k)(-1)^k(x^2)^{n-k}$ have to be negative? $\endgroup$ – Filburt Jan 14 '16 at 17:32
  • $\begingroup$ You're thinking along too complicated lines. The inequality we get is $(n^2-1)^n>(n^2)^n$. If you still can't see it, take $n$-th root. $\endgroup$ – Arthur Jan 14 '16 at 17:35
  • $\begingroup$ Omg, you're right. This is I really nice one! $\endgroup$ – Filburt Jan 14 '16 at 17:38
  • $\begingroup$ @FernandoVieraCostaJúnior If you want to show it your way with the binomial coefficients, it is also not very difficult to show that in the alternating sum $\sum_{k=1}^n \binom nk (-1)^{k}(n^2)^{n-k}$, every negative term is larger (in absolute value) than the positive term that comes after it. $\endgroup$ – Arthur Jan 15 '16 at 6:36
  • 1
    $\begingroup$ Your way is much better! $\endgroup$ – Filburt Jan 15 '16 at 13:06
3
$\begingroup$

For the record, we can still do it by induction, it's just not as pleasant as other induction questions and the other proofs on this page.

Let's start with the LHS of the $n+1$ case. We're going to 'force in' the $n$ case, so we can use the induction hypothesis.

$$ \begin{align} (n+2)^{n+1} & = {(n+2)^{n+1}(n+1)^n \over (n+1)^n} \\ \\ & < {(n+2)^{n+1}n^{n+1} \over (n+1)^n} & \text{(induction hypothesis)} \end{align} $$

Now we work backwards from what we want to show to finish the induction step. We want:

$$\begin{align} {(n+2)^{n+1}n^{n+1} \over (n+1)^n} &< (n+1)^{n+2} \\\\ \iff (n+2)^{n+1}n^{n+1} &< (n+1)^{2n+2} \\\\ \iff [n(n+2)]^{n+1} &< [(n+1)^2]^{n+1} \\\\ \iff n(n+2) &< (n+1)^2 \end{align}$$

And this is true for all $n$ (simply expand it out). Hence we're done once we note it's true for $n=3$.

Alternatively if we know that $\lim_{n \to \infty} (1+1/n)^n = e < 3$, and that $(1+1/n)^n$ is increasing, we can observe that the inequality is true by dividing by $n^n$. But these facts require more work than a direct proof.

$\endgroup$
2
$\begingroup$

For $n\geq 3, n\in\mathbb{N}$ we have $\binom{n}{2}=\frac{n(n-1)}{2}<n^2$ and so $(n+1)^n=\sum_{k=0}^n \binom{n}{k}n^{n-k}=1+\sum_{k=0}^{n-1} \binom{n}{k}n^{n-k}< 1+\sum_{k=0}^{n-1} n^kn^{n-k}=1+n\cdot n^n=1+n^{n+1}$ So we only need to show $n^{n+1}\neq (n+1)^n$. This is clear because one and only one of the numbers is odd.

$\endgroup$
  • 1
    $\begingroup$ Nice one. Thanks. =D $\endgroup$ – Filburt Jan 14 '16 at 17:34
1
$\begingroup$

Hint Since $\log$ is an increasing function, taking the logarithm of both sides and rearranging gives that inequality is equivalent to $$\frac{\log n}{n} < \frac{\log (n + 1)}{n + 1}.$$ So, it suffices to show that the function $$x \mapsto \frac{\log x}{x}$$ is (strictly) decreasing on the interval $[3, \infty)$, which is a straightforward exercise using the First Derivative Test.

$\endgroup$
  • $\begingroup$ For now, I can't use these results. But this is a nice one. $\endgroup$ – Filburt Jan 14 '16 at 17:36
  • $\begingroup$ It would be useful if you included a little more context, e.g., the material in the section of the course for which this problem was assigned, so that potential answerers can give appropriate hints. $\endgroup$ – Travis Jan 14 '16 at 17:45
1
$\begingroup$

Hint: rewrite as $n>\sqrt[n+1]{(n+1)^n}$ and try to use AM-GM inequality.

Further hint: $(n+1)^n=(n+1)^{n-1}\sqrt{n+1}^2$.

Further hint (per request): AM-GM gives us $$\sqrt[n+1]{(n+1)^n}=\sqrt{(n+1)\dots(n+1)\sqrt{n+1}\sqrt{n+1}}<\frac{(n+1)+\dots+(n+1)+\sqrt{n+1}+\sqrt{n+1}}{n+1}=\frac{(n-1)(n+1)+2\sqrt{n+1}}{n+1}$$

$\endgroup$
  • $\begingroup$ I couldn't get. One more hint? $\endgroup$ – Filburt Jan 14 '16 at 17:35
1
$\begingroup$

Hint: The function $x \mapsto x^{1/x}$ has a single critical point at $x=e$ and is decreasing for $x \gt e$.

$\endgroup$
0
$\begingroup$

$(n+1)^n<n^{(n+1)} \iff n\ln (n+1)<(n+1)\ln n\iff \ln (1+\frac 1n)^n<\ln n$.

The LHS tends to 1 and the RHS tends to $\infty$.

For $n=2$ one has LHS$\approx 0.8109$ and RHS$\approx 06931$ so LHS>RHS but for $n\ge 3$ the inequality is verified increasingly in each of the two sides.

$\endgroup$
  • $\begingroup$ Both RHS and LHS of the last inequality are increasing, so it's not immediate that if the inequality holds for $n=3$, then it will work for $n>3$. $\endgroup$ – Wojowu Jan 14 '16 at 17:41
  • $\begingroup$ Not when LHS is bounded by $1$! $\endgroup$ – Piquito Jan 15 '16 at 13:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.