For $k=n-1$ or $k=1$, the first inequality becomes: $n^{n}<n(n+1)((n-1)^{n-1})$, or: $(1+\frac{1}{n-1})^{n-1}<n+1$. But LHS$<e<3\leq n$. The second inequality becomes: $n<\frac{n^{n}}{(n-1)^{n-1}}$, or: $1<(1+\frac{1}{n-1})^{n-1}$, evidenty true. Now return to the initial problem. For $n=3$, the inequality is true, since we proved it for $k=1, 2=3-1$. Consider the inequalities true for all $n,k$ such that $k<n\leq t-1$. We'll prove the inequality for $t$. Consider $k>1$. The second inequality becomes: $\frac{t!}{k!(t-k)!}<\frac{t^{t}}{k^{k}(t-k)^{t-k}} \Leftrightarrow$, $\frac{(t-1)!}{(k-1)!(t-k)!)}<\frac{t^{t-1}}{k^{k-1}(t-k)^{t-k}}$. By the induction hypothesis: $\frac{(t-1)!}{(k-1)!(t-k)!}<\frac{(t-1)^{t-1}}{(k-1)^{k-1}(t-k)^{t-k}}$. So it suffices to prove that: $\frac{(t-1)^{t-1}}{(k-1)^{k-1}(t-k)^{t-k}}<\frac{t^{t-1}}{k^{k-1}(t-k)^{t-k}}$, or: $(1+\frac{1}{k-1})^{k-1}<(1+\frac{1}{t-1})^{t-1}$. But the function $(1+\frac{1}{x})^{x}$ is increasing. Unfortunately, the first inequality doesn't result in a similar way

shobber wrote: Let $n,k$ be given positive integers with $n>k$. Prove that: \[ \frac{1}{n+1} \cdot \frac{n^n}{k^k (n-k)^{n-k}} < \frac{n!}{k! (n-k)!} < \frac{n^n}{k^k(n-k)^{n-k}} \] Lemma: Let $a$ and $b$ be any positive integers. For any integer $i$ between 0 and $a+b$, $\binom{a+b}{i} a^i b^{a+b-i} \leq \binom{a+b}{a} a^a b^b$, with equality not holding when $i=0$ or when $i = a+b.$ Proof: Let $f(i) = \binom{a+b}{i} a^i b^{a+b-i}$. We observe that $f(a) = \binom{a+b}{a} a^a b^b$. We will show that $\frac{f(i)}{f(i+1)} \geq 1$ whenever $i \geq a$ and that $\frac{f(i)}{f(i+1)} \leq 1$ whenever $i \leq a$. We have \[ \frac{f(i)}{f(i+1)} = \frac{\binom{a+b}{i} a^i b^{a+b-i}}{\binom{a+b}{i+1} a^{i+1} b^{a+b-i-1}} = \frac{\frac{(a+b)!}{i! (a+b-i)!}}{\frac{(a+b)!}{(i+1)! (a+b-i-1)!}} \cdot \frac{b}{a} = \frac{i}{a+b-i} \cdot \frac{b}{a}.\] If $i \geq a$, then \[ \frac{i}{a+b-i} \cdot \frac{b}{a} = \frac{1}{\frac{a+b}{i} - 1} \cdot \frac{b}{a} \geq \frac{1}{\frac{a+b}{a} - 1} \cdot \frac{b}{a} = 1, \] and if $i \leq a$, then \[ \frac{i}{a+b-i} \cdot \frac{b}{a} = \frac{1}{\frac{a+b}{i} - 1} \cdot \frac{b}{a} \leq \frac{1}{\frac{a+b}{a} - 1} \cdot \frac{b}{a} = 1,\] as desired. To show that $f(0) < f(a)$ or $f(a+b) < f(a)$, we suppose without loss of generality $a \geq b$. Then \[ \frac{f(a)}{f(0)} = \frac{a^a b^b \binom{a+b}{a}}{b^{a+b}} = \left(\frac{a}{b}\right)^a \binom{a+b}{a} > 1.\] Let $j = n-k$. We wish to show that \[ \frac{1}{j+k+1}{\cdot \frac{(j+k)^{j+k}}{j^j k^k} < \frac{(j+k)!}{j! k!} < \frac{(j+k)^{j+k}}{j^j k^k} }\] We have \[ (j+k)^{j+k} = \sum_{i=0}^{j+k} \binom{j+k}{i} j^i k^{j+k-i} \&> \binom{j+k}{j} j^j k^k \] which rearranges to \[ \frac{(j+k)!}{j! k!} < \frac{(j+k)^{j+k}}{j^j k^k}. \] In addition, by the lemma, we have \[ (j+k)^{j+k} = \sum_{i=0}^{j+k} \binom{j+k}{i} j^i k^{j+k-i} > \sum_{i=0}^{j+k} \binom{j+k}{j} j^j k^k = (j+k+1) \binom{j+k}{j} j^j k^k, \] which rearranges to \[ \frac{1}{j+k+1}{\cdot \frac{(j+k)^{j+k}}{j^j k^k} < \frac{(j+k)!}{j! k!}, }\] so we are done.

well, let k/n = p. Then, it is pretty easy to see that the claim is equivalent to showing that 1/(n+1) < (nCk)(p^k*(1-p)^(n-k) < 1 however, simply considering a binomial distribution with n trials, a probability of success p, we are nearly instantly done (a binomial distribution is maximized at the mean, np = k.)

Lets consider $n^n=(k+n-k)^n.$ The expansion of $n^n=\sum _{i=0}^n\binom{n}{i}k^k(n-k)^{n-k}.$ One of the term of the expansion is $n\binom{n}{i}k^k{(n-k)}^{n-k}$ which is strictly less than $n^n$. Dividing by $k^k\times (n-k)^{n-k}$ we get the second inequality. For the first inequality, we have to show that the highest term of the expansion of $n^n$ is $\binom{n}{k}k^k{(n-k)}^{n-k}$. For this let $T_r=\binom{n}{r}k^r{(n-k)}^{n-r}$ and $T_{r+1}=\binom{n}{r+1}k^{r+1}{(n-k)}^{n-r-1}$. Notice that $T_r>T_{r+1}$ for $r\geq k$ and smaller when $r<k$. Therefore we get $(n+1)\binom{n}{k}k^k{(n-k)}^{n-k}>n^n$. Dividing both side by $k^k\times (n-k)^{n-k}$ and rearranging we get our desired first inequality.

Abdullahil_Kafi wrote: Lets consider $n^n=(k+n-k)^n.$ The expansion of $n^n=\sum _{i=0}^n\binom{n}{i}k^k(n-k)^{n-k}.$ One of the term of the expansion is $n\binom{n}{i}k^k{(n-k)}^{n-k}$ which is strictly less than $n^n$. Dividing by $k^k\times (n-k)^{n-k}$ we get the second inequality. For the first inequality, we have to show that the highest term of the expansion of $n^n$ is $\binom{n}{k}k^k{(n-k)}^{n-k}$. For this let $T_r=\binom{n}{r}k^r{(n-k)}^{n-r}$ and $T_{r+1}=\binom{n}{r+1}k^k{(n-k)}^{n-r-1}$. Notice that $T_r>T_{r+1}$ for $r>m$ and smaller when $r<m$. Therefore we get $(n+1)\binom{n}{k}k^k{(n-k)}^{n-k}>n^n$. Dividing both side by $k^k\times (n-k)^{n-k}$ and rearranging we get our desired first inequality. can u explain how did you prove the first ineq it is unclear to me

TFIRSTMGMEDALIST wrote: can u explain how did you prove the first ineq it is unclear to me In any $n$ power binomial, there are exactly $n+1$ terms, and all the terms are not equal. Therefore if we sum the biggest term $n+1$ times then it is obviously strictly bigger than the original and hence done.

yes but before this how did you prove that the highest term of the expansion is ..... you didn't define m and there's a mistake in the expansion of n up to n

TFIRSTMGMEDALIST wrote: yes but before this how did you prove that the highest term of the expansion is ..... you didn't define m and there's a mistake in the expansion of n up to n Ok, $m$ is actually $k$ (I edited).

Using Stirling's approximation (the stronger version

being an exact bound rather than an asymptotic formula) we have: \begin{align*}\frac{n!}{k! (n-k)!}&>\frac{\sqrt {2\pi n}\left(\frac{n}{e}\right)^{n}e^{\frac{1}{12n+1}}}{\left(\sqrt {2\pi k}\left(\frac{k}{e}\right)^{k}e^{\frac{1}{12k}}\right)\cdot \left(\sqrt {2\pi (n-k)}\left(\frac{n-k}{e}\right)^{n-k}e^{\frac{1}{12(n-k)}}\right)} \\ &=\frac{n^{n}}{k^{k}(n-k)^{n-k}}\cdot \frac{\sqrt{n}}{\sqrt{k(n-k)}}\cdot\frac{1}{\sqrt{2 \pi}} \cdot e^{\frac{1}{12n+1}-\frac{1}{12k}-\frac{1}{12n-12k}}\\ &>\frac{n^{n}}{k^{k}(n-k)^{n-k}}\cdot \frac{\sqrt{n}}{\sqrt{k(n-k)}}\cdot\frac{1}{\sqrt{2 \pi}} \cdot e^{-1/6}\\ &>\frac{n^{n}}{k^{k}(n-k)^{n-k}}\cdot \frac{4}{n+1}\cdot \frac{1}{3}\\ &>\frac{n^{n}}{k^{k}(n-k)^{n-k}}\cdot \frac{1}{n+1}\\ \end{align*}where we've used the lower bound approximation for $n!$ and the upper bound for $k!$ and $(n-k)!$ as they're in the denominator. Also, to carry out the inequality we've used the following (far from strict) bounds: \[\frac{1}{12n+1}-\frac{1}{12k}-\frac{1}{12n-12k}>-\frac{1}{12k}-\frac{1}{12(n-k)}\geq-\frac{1}{12}-\frac{1}{12}=-\frac{1}{6}\]\[\frac{e^{-1/6}}{\sqrt{2 \pi}}=\frac{1}{\sqrt[6]{8\pi^3e}}>\frac{1}{3}\]\[\frac{n}{2}=\frac{k+(n-k)}{2}\geq \sqrt{k(n-k)}\Longrightarrow \frac{\sqrt{n}}{\sqrt{k(n-k)}}\geq\frac{\sqrt{n}}{n/2}=\frac{2}{\sqrt{n}}\geq \frac{2}{\frac{n+1}{2}}=\frac{4}{n+1}\]We prove the right-hand inequality in the same manner: \begin{align*}\frac{n!}{k! (n-k)!}&<\frac{\sqrt {2\pi n}\left(\frac{n}{e}\right)^{n}e^{\frac{1}{12n}}}{\left(\sqrt {2\pi k}\left(\frac{k}{e}\right)^{k}e^{\frac{1}{12k-1}}\right)\cdot \left(\sqrt {2\pi (n-k)}\left(\frac{n-k}{e}\right)^{n-k}e^{\frac{1}{12(n-k)+1}}\right)} \\ &=\frac{n^{n}}{k^{k}(n-k)^{n-k}}\cdot \frac{\sqrt{n}}{\sqrt{k(n-k)}}\cdot\frac{1}{\sqrt{2 \pi}} \cdot e^{\frac{1}{12n}-\frac{1}{12k+1}-\frac{1}{12n-12k+1}}\\ &<\frac{n^{n}}{k^{k}(n-k)^{n-k}}\cdot \frac{\sqrt{n}}{\sqrt{k(n-k)}}\cdot\frac{1}{\sqrt{2 \pi}} \cdot 1\\ &<\frac{n^{n}}{k^{k}(n-k)^{n-k}}\cdot \frac{\sqrt{n}}{\sqrt{n-1}}\cdot \frac{1}{2}\\ &<\frac{n^{n}}{k^{k}(n-k)^{n-k}}\\ \end{align*}where we've used the upper bound approximation for $n!$ and the lower bound for $k!$ and $(n-k)!$ as they're in the denominator. Also, to carry out the inequality we've used the following (far from strict) bounds:

\[\frac{1}{12n}-\frac{1}{12k+1}-\frac{1}{12n-12k+1}<\frac{1}{12n}-\frac{1}{12k+1}\leq \frac{1}{12n}-\frac{1}{12n-11}<0\]\[\frac{1}{\sqrt{2 \pi}}<\frac{1}{2}\]\[\frac{\sqrt{n}}{2\sqrt{k(n-k)}}=\frac{\sqrt{n}}{2\sqrt{\left(\frac{n}{2}\right)^2-\left(\frac{n}{2}-k\right)^2}}\leq \frac{\sqrt{n}}{2\sqrt{\left(\frac{n}{2}\right)^2-\left(\frac{n}{2}-1\right)^2}}=\frac{\sqrt{n}}{2\sqrt{n-1}}=\sqrt{\frac{n}{4n-4}}<1\]Remark

Any combinatorial solution?