A very beautiful problem. First i will show that $\dbinom{n}{k}\geq \left (\frac{2n+1-k}{k+1} \right )^k$ for all $n\geq k$. Note that the above inequality is equivalent to $$n(n-1)(n-2)\dots (n-k+1)(k+1)^k \geq (2n+1-k)^k k!$$wich after we $\ln$ both sides is $$\ln(n)+\ln(n-1)+\dots+\ln(n-k+1)+k\ln(k+1) \geq k \ln(2n+1-k)+\ln(k!)$$Now , consider $f(x)=\ln(x)+\ln(x-1)+\dots+\ln (x-k+1)+k\ln(k+1) -k \ln(2x+1-k)-\ln(k!) $ , if we show that $f$ is increasing for $x \geq k >0$ we are done . We have $$f'(x)=\frac{1}{x}+\frac{1}{x-1}+\dots +\frac{1}{x-k+1}-\frac{2k}{2x+1-k}$$and from Cauchy Schwarz we have $$\frac{1}{x}+\frac{1}{x-1}+\dots +\frac{1}{x-k+1} \geq \frac{k^2}{kx-\frac{k(k-1)}{2}}=\frac{2k}{2x-k+1}$$therefore $f'(x)\geq 0$ for $x \geq k$ wich implies $f(x)\geq f(k)\geq 0$ and we have proven our inequality. From the binomial theorem we have $$(1+1)^n=\sum_{k=0}^{n} \dbinom{n}{k} \geq \sum_{k=0}^{n}\left(\frac{2n+1-k}{k+1}\right)^k$$$\blacksquare$ .

XbenX wrote: A very beautiful problem. First i will show that $\dbinom{n}{k}\geq \left (\frac{2n+1-k}{k+1} \right )^k$ for all $n\geq k$. Note that the above inequality is equivalent to $$n(n-1)(n-2)\dots (n-k+1)(k+1)^k \geq (2n+1-k)^k k!$$wich after we $\ln$ both sides is $$\ln(n)+\ln(n-1)+\dots+\ln(n-k+1)+k\ln(k+1) \geq k \ln(2n+1-k)+\ln(k!)$$Now , consider $f(x)=\ln(x)+\ln(x-1)+\dots+\ln (x-k+1)+k\ln(x+1) -k \ln(2x+1-k)-\ln(k!) $ , if we show that $f$ is increasing for $x \geq k >0$ we are done . We have $$f'(x)=\frac{1}{x}+\frac{1}{x-1}+\dots +\frac{1}{x-k+1}-\frac{2k}{2x+1-k}$$and from Cauchy Schwarz we have $$\frac{1}{x}+\frac{1}{x-1}+\dots +\frac{1}{x-k+1} \geq \frac{k^2}{kx-\frac{k(k-1)}{2}}=\frac{2k}{2x-k+1}$$therefore $f'(x)\geq 0$ for $x \geq k$ wich implies $f(x)\geq f(k)\geq 0$ and we have proven our inequality. From the binomial theorem we have $$(1+1)^n=\sum_{k=0}^{n} \dbinom{n}{k} \geq \sum_{k=0}^{n}\left(\frac{2n+1-k}{k+1}\right)^k$$$\blacksquare$ . Nice solution. In the official solution there is also another way to solve. But my solution I think is more elegant and it starts with the same idea to show the first inequality you mention, but it has a very good idea.

Here it is my solution: As in previous solution we prove $\binom{n}{k}\geq \left(\frac{2n+1-k}{k+1}\right)^k$ for all $k=0,1,...,n$ and then we finish in same way as in previous solution. For $k=0$ and $k=n$ it is pretty clear. Now we prove for $0<k<n$. Using Holder inequality we have $$\binom{n}{k}=\frac{n!}{k!\cdot (n-k)!}=\frac{n\cdot (n-1)\cdot...\cdot (n-k+1)}{k\cdot (k-1)\cdot ...\cdot 1}=\left(1+\frac{n-k}{k}\right)\cdot \left(1+\frac{n-k}{k-1}\right)\cdot...\cdot\left(1+\frac{n-k}{1}\right)\geq \left(1+\frac{n-k}{\sqrt[k]{k!}}\right)^k$$Hence that is enough to prove $1+\frac{n-k}{\sqrt[k]{k!}}\geq \frac{2n+1-k}{k+1}\Leftrightarrow \sqrt[k]{k!}\leq \frac{k+1}{2}$ Last inequality is true since from AM-GM we have $$\sqrt[k]{k!}\leq \frac{1+2+...+k}{k}=\frac{k+1}{2}$$Hence done.

Here is another solution. As in the previous solutions, we'll show that $\binom{n}{k} \ge \left(\frac{2n+1-k}{k+1}\right)^k$ for all $0 \le k \le n.$ From here, the inequality follows by summing over $k.$ Equivalently, we'll show that: $$\binom{n}{n-k} \ge \left(\frac{n+k+1}{n-k+1}\right)^{n-k}, \forall k = n, n-1, \cdots, 0.$$ Here, all we did is plug in $n-k$ instead of $k$. From the formula $\binom{n}{n-k} = \frac{nP(n-k)}{(n-k)!}$, we want: $$n(n-1) \cdots (k+1) (n-k+1)^{n-k} \ge (n-k)(n-k-1) \cdots 2 \cdot 1 \cdot (n+k+1)^{n-k}. \qquad (*)$$ The key ingredient is: $$\frac{(n-a)(k+1+a)}{(n+k+1)^2} \ge \frac{(n-k-a)(1+a)}{(n-k+1)^2}, \forall 0 \le a \le n-k-1. \qquad (1)$$ This can be seen by noting that the LHS can be written as $$1 - \left(\frac{n-a}{n+k+1} - \frac{k+1+a}{n+k+1}\right)^2$$and the RHS can be written as $$1 - \left(\frac{n-k-a}{n-k+1} - \frac{1+a}{n-k+1}\right)^2.$$Hence, $(1)$ easily follows from the fact that $\left(\frac{n-k-1-2a}{n+k+1}\right)^2 \le \left(\frac{n-k-1-2a}{n-k+1}\right)^2.$ From here, multiplying $(1)$ over $0 \le a \le n-k-1$ yields our desired estimate $(*)$, and so we're done. $\square$

........

dangerousliri wrote: Show that for every positive integer $n$ we have: $$\sum_{k=0}^{n}\left(\frac{2n+1-k}{k+1}\right)^k=\left(\frac{2n+1}{1}\right)^0+\left(\frac{2n}{2}\right)^1+...+\left(\frac{n+1}{n+1}\right)^n\leq 2^n$$Proposed by Dorlir Ahmeti, Albania A splendor