# Finding a lower bound for sum of exponentials

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?

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
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)$$