# 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!

• What are the "relevant $j$"? Mar 13 '21 at 17:31
• All such that you can you can interpret the binomial coefficient as the number of subsets. So the lower index is not greater than the upper, and not negative. If the binomial coefficient returns 0 if these conditions do not hold, you can sum all of these from 0 to n Mar 13 '21 at 17:33

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".

• Really? I was asked for a closed form, but this might then be "closed enough". Thanks! Mar 13 '21 at 18:04

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.

• Oh well, this might then be "closed enough" as an answer. By the way, if the $n$-th term in the sequence is $r_n$, then $r_n = [x^n](1 + x + x^2)^n$, if that helps. Thanks for your answer! Mar 13 '21 at 18:14
• I'm sorry, I only read the elements of the sequence, I didn't mean to state the obvious, that these were the central trinomial coefficients. Mar 13 '21 at 18:27

For $$k\ge1$$, let $$s_k$$ and $$S_k$$ be two sequences independent of $$n$$ such that $$n\ge k\ge1$$. Then $$$$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.$$$$

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

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.