Closed form for binomial coefficient sum

Question

As part of a proof in finite group theory, I'm looking for a closed form for the expression

$$\sum_{i=j+1}^{n} \binom{\binom{i}{j}}{2}.$$

Any help — especially with reference or proof — would be appreciated. In the group theory context, there is strong evidence that the overall result is correct, but having a closed form here would be the most obvious way to construct a proof.

I don't know if a closed form exists, but computation of special cases suggests the sum is equal to

$$\frac{(n-j)(n-(j-1))\dotsm(n-1)n(n+1)p_j(n)}{(2j+1)!}$$

where $p_j(n)$ is a polynomial with integer coefficients of degree $j-1$. In fact, the leading coefficient of $p_j$ appears to be $\binom{2j-1}{j-1}$. In general $p_j$ is not irreducible.

I really just need to know that factor of $(n+1)$ is present, but to prove that by induction on $n$ it seems I would need a precise formula for $p_j$. Since I can compute $p_j$ for given $j$, I know this formula is correct for $j=1$, $2$, $3$, and $4$.

Answer 1

A closed form is \begin{equation*} \sum_{i=j+1}^{n} \binom{\binom{i}{j}}{2} =\sum_{k=1}^j \frac{1}{2}\binom{j}{k}\binom{j+k}{k}\binom{n+1}{j+k+1}.\tag{1}\label{474985_1} \end{equation*} For fixed $j$ this is indeed a closed form; for example, for $j=3$ it gives \begin{equation*} \sum_{i=4}^n \binom{\binom{i}{3}}{2}=6\binom{n+1}{5}+15\binom{n+1}{6}+10\binom{n+1}{7}. \end{equation*} Also, each term in \eqref{474985_1}, as a polynomial in $n$, is divisible by $(n+1)n(n-1)\dots (n-j)$.

First note that we may start the sum on the left side of \eqref{474985_1} at $i=0$ instead of $i=j+1$. Then by the well-known identity $\sum_{i=0}^n \binom{i}{k} = \binom{n+1}{k+1}$, \eqref{474985_1} will follow from \begin{equation*} \binom{\binom nj}{2} = \sum_{k=1}^j \frac12\binom jk \binom{j+k}{k}\binom{n}{j+k}. \tag{2}\label{474985_2} \end{equation*}

To prove \eqref{474985_2} we have $\binom{j+k}{k}\binom{n}{j+k} = \binom{n}{j}\binom{n-j}{n-j-k}$, so \begin{align*} \sum_{k=1}^j \frac12\binom jk \binom{j+k}{k}\binom{n}{j+k} &=\frac12\binom{n}{j}\sum_{k=1}^j \binom {j}{k}\binom{n-j}{n-j-k} \\ &=\frac12\binom{n}{j}\biggl[\sum_{k=0}^j \binom {j}{k}\binom{n-j}{n-j-k} -1\biggr] \\ &=\frac12\binom{n}{j}\left[\binom{n}{n-j} -1\right]=\binom{\binom nj}{2} \end{align*} by Vandermonde's theorem.

Answer 2

Equation \eqref{474985_1} from Ira Gessel's nice answer can be summed using Mathematica 14, and the result can be simplified to \begin{align} \sum_{i=j+1}^{n} \binom{\binom{i}{j}}{2} &=\sum_{k=1}^j \frac{1}{2}\binom{j}{k}\binom{j+k}{k}\binom{n+1}{j+k+1}\\ &=\frac 1 2 \binom{n+1}{j+1}\left[\binom{n}{j} -1+\frac{j(n-j)}{j+2} \,{}_3F_2 \left(\begin{matrix} 1-j,1-(n-j),j+2\\2,j+3 \end{matrix};1 \right)\right]. \end{align}

Answer 3

$$\sum_{i=j+1}^n {i \choose j}$$ has a simple closed form.

It appears that $$ \sum_{i=j+1}^n {i \choose j}^2 = \lim_{x \to 1-} \left(\left( j+1 \right) ^{2}{x}^{j+1} {\mbox{$_3$F$_2$}(1,j+2,j+2;\,2,2;\,x)}- {n+1\choose j} ^{2}{x}^{n+1}{\mbox{$_3$F$_2$}(1,2+n,2+n;\,2+n-j,2+n-j;\,x)} \right)$$

Answer 4

It is not hard to show that the factor $n+1$ is present.

Theorem. Let $p(i)$ be a polynomial. Then there exists a polynomial $P(n)$ such that for $i\ge0$ we have $\sum_{i=0}^n p(i)= P(n)$, and $P(n)$ is divisible by $n+1$.

Proof. The existence of the polynomial $P(n)$ is well known. To show that $P(n)$ is divisible by $n+1$ it suffices to show that $P(-1) = 0$. But $$P(n) = -p(-1) +\sum_{i=-1}^n p(i),$$ and this formula is valid for $n\ge-1$. Thus $P(-1) = -p(-1) +p(-1) =0$.

A slightly different point of view makes this result seem more obvious. Let $p$ be a polynomial. Then by finite differences or otherwise there is a unique polynomial $Q$ such that $Q(i+1)-Q(i)=p(i)$ for all $i$ (all we need is $i\ge0$) and $Q(0) = 0$. By induction, we have $\sum_{i=0}^{n-1} p(i) = Q(n)$ for all $n\ge0$, where, as usual, $\sum_{i=0}^{-1}$ is 0 by definition. Since $Q(0) =0$, $Q(n)$ is divisible by $n$, so $\sum_{i=0}^n p(i) = Q(n+1)$ is divisible by $n+1$.

Another (slightly more complicated, but self-contained) way to prove the theorem is to note that it holds for the basis of polynomials $p(i) = \binom{i}{k}$, since $\sum_{i=0}^n \binom{i}{k}=\binom{n+1}{k+1}$, which is divisible by $n+1$.

Answer 5

Mathematica says:

$$ \frac{1}{2} \left(\frac{\frac{\Gamma (-j-1) \Gamma (-j) \binom{n+1}{j} \Gamma (-j+n+2)}{\Gamma (-j+n+1)}+\Gamma (-2 j-1)}{\Gamma (-j)^2}-\binom{n+1}{j}^2 \, _3F_2(1,n+2,n+2;-j+n+2,-j+n+2;1)\right) $$ I am not quite sure what to make of the Gammas with negative integer arguments, but there you have it.