Exponential bound for $k + \ln (^nC_k)$

Question

I need an exponential upper bound for the above expression. Experimentally, I am getting a bound of $1.5 n$ but am unable to derive it.

$k<n$ in this case.

Answer 1

First we try to maximize $f(n,k)=k+\ln \binom{n}{k}$ for any n. After, we afford a $k_0=g(n)$ and substitute it in the equation of $f(n,k)$ as $f(n,g(n))$ and then we bound $f(n,g(n))$. First note that all calculations are concrete so for extermization we need to first difference instead of first derivation. For a constant $n$ we have:$$\delta(n,k)=f(n,k)-f(n,k-1)\\=k+\ln \binom{n}{k}-(k-1)+\ln \binom{n}{k-1}\\=1+\ln (\dfrac{n!}{k!(n-k)!}\dfrac{(k-1)!(n-k+1)!}{n!})\\=1+\ln \frac{n-k+1}{k}$$For maximizing $f(n,k)$ we must have $\delta(n,k)=0$ and solve it with respect to $k$ given $n$. From here we obtain:$$\hat k=\dfrac{e}{e+1}(n+1)$$since $k_0$ should be integer we have:$$k_0=\lfloor \hat k\rfloor=\lfloor \dfrac{e}{e+1}(n+1) \rfloor$$From here we can observe that both $k$ and $k_0$ are quasi-linear with respect to n and increase to $\infty$ strictly when $n\to\infty$. Therefore we can approximate $n!$ , $k!$ and $(n-k)!$ using Stirling's formula. Also in limit and approximation we substitute $\hat k$ instead of $k_0$ since $\lim_{n\to\infty}\dfrac{k_0}{\hat k}=1$. Therefore:$$f(n,k_0)=k_0+\ln \binom{n}{k_0}=k_0+\ln\dfrac{n!}{k_0!(n-k_0)!}$$which is equivalent to the functions below in $n\to\infty$: $$f(n,k_0)\sim \hat k+\ln\dfrac{n!}{\hat k!(n-\hat k)!}\sim \hat k+\ln\dfrac{(\dfrac{n}{e})^n}{(\dfrac{\hat k}{e})^{\hat k}(\dfrac{n-\hat k}{e})^{n-\hat k}}=\hat k +\ln (\dfrac{n}{\hat k})^{\hat k}(\dfrac{n}{n-\hat k})^{n-\hat k}$$ First we try to find the asymptotic behavior of $(\dfrac{n}{\hat k})^{\hat k}(\dfrac{n}{n-\hat k})^{n-\hat k}$. Since we have $\lim_{n\to\infty}\dfrac{k}{n}=\dfrac{e}{e+1}$ let $p=\dfrac{k}{n}$ therefore $$(\dfrac{n}{\hat k})^{\hat k}(\dfrac{n}{n-\hat k})^{n-\hat k}=((\dfrac{1}{p})^{p}(\dfrac{1}{1-p})^{1-p})^n\sim ((\dfrac{e+1}{e})^{\dfrac{e}{e+1}}(e+1)^\dfrac{1}{e+1})^n$$finally by substitution we obtain:$$f(n,k_0(n))\sim n(\frac{e}{e+1}+\ln[(\dfrac{e+1}{e})^{\dfrac{e}{e+1}}(e+1)^\dfrac{1}{e+1}])\approx 1.3133n$$