Finding closed form for $\sum_{j = \lceil n/2 \rceil}^n \binom{n}{j} \binom{j}{n-j}$ I'm having some trouble finding a closed formula for this quantity:
\begin{align*}
\sum_{j} \binom{n}{j}\binom{j}{n-j}
\end{align*}
I know that this size is equal to
\begin{align*}
\sum_{j} \binom{n}{j}\binom{n-j}{j}
\end{align*}
And also
\begin{align*}
\sum_j \binom{n}{2j}\binom{2j}{j}
\end{align*}
All these sums are over all allowed $j$, that is, so the lower index in the binomial coefficient is not greater than the upper, and is not negative. Can someone help me? Thanks :)
Edit: It seems like people agree that there might not be a simple closed form for this sum.
Edit: Apparently, this sum is the n-th term in the sequence of central trinomial coefficients, which do not have a closed form that are on my level. I did not know that at the time. Thanks for your answers!
 A: Mathematica says (for Jean Marie's version):
$$\binom{n}{\frac{n}{2}} \,
   _2F_1\left(-\frac{n}{2},-\frac{n}{2};\frac{1}{2};\frac{1}{4}\right)$$
If this is really the best that can be done, then there is no "closed form".
A: Some simple manipulation shows that the answer is this sequence, which doesn't seem to have a nice closed formula.
The "simplest" formula indeed involves hypergeometric functions. See reference in the linked page.
A: For $k\ge1$, let $s_k$ and $S_k$ be two sequences independent of $n$ such that $n\ge k\ge1$. Then
\begin{equation}
s_n=\sum_{k=1}^{n}\binom{k}{n-k}S_k
\quad\text{if and only if}\quad
(-1)^nnS_n=\sum_{k=1}^{n}\binom{2n-k-1}{n-1}(-1)^kks_k.
\end{equation}
This inversion theorem was obtained in the paper
Feng Qi, Qing Zou, and Bai-Ni Guo, The inverse of a triangular matrix and several identities of the Catalan numbers, Applicable Analysis and Discrete Mathematics 13 (2019), no. 2, 518--541; available online at https://doi.org/10.2298/AADM190118018Q.
The well-known binomial inversion theorem reads that
\begin{equation}
g(n)=\sum_{\ell=0}^n\binom{n}{\ell}(-1)^\ell f(\ell) \Longleftrightarrow
f(n)=\sum_{\ell=0}^n\binom{n}{\ell}(-1)^\ell g(\ell).
\end{equation}
Are these two inversion theorems useful?
By the way, I also asked a similar question: What is the general formula of the sum $\sum_{k=0}^{n}(-1)^{k} \binom{n}{k}\binom{k/2}{m}$ for $m,n\in\mathbb{N}$?. Wish somebody gives an answer to my question. Thank you very much.
