Finding a lower bound for sum of exponentials

Question

I'm trying to find a tight lower bound (i.e. some function of $n\in \mathbb{N}$) for $$f(n)=\sum_{j=0}^n {n\choose j}\exp\left(\frac{j(j-1)}{2}+\frac{(n-j)(n-j-1)}{2}-j(n-j)\right)$$

My attempt: Define

$$g(x):= \left(\frac{x(x-1)}{2}+\frac{(n-x)(n-x-1)}{2}-x(n-x)\right)$$

$g'(x)=0$ only if $x=n/2$ and $g''(n/2)>0$. So $g(x)\geq g(n/2)$ for all $x$. In particular $g(j)\geq g(n/2)$ for all $0\leq j\leq n$. Thus

\begin{equation} f(n) \geq \exp(g(n/2))\sum_{j=0}^n {n\choose j} = \exp(-n/2)2^n \end{equation}

which is a crude lower bound and am hoping to find a better lower bound. The reason the bound I have is not good is because I have found a lower bound for each exponential term in the definition of $f(n)$ i.e. $g(n/2)$ which is exponentially decreasing in $n$ whereas in the definition of $f(n)$, there is at least one exponential term that is exponentially increasing in $n$ (For example, when $j=0$, the exponential term is $\exp(n(n-1)/2)$). Any ideas?

Answer 1

If you simplify the argument of the exponential, $$f(n)=e^{-\frac n2}\, \sum_{j=0}^n\binom{n}{j}\, e^{\frac{1}{2} (n-2 j)^2} > e^{-\frac n2}\, \sum_{j=0}^{k<n}\binom{n}{j}\, e^{\frac{1}{2} (n-2 j)^2} $$

For example, with $k=2$ $$f(n)>e^{\frac{n(n-1)}{2}} \left(1+ne^{2-2 n}+\frac{n(n-1) }{2} e^{8-4 n} \right)=g(n)$$