Prove that $\sum_{k=0}^{n}\binom{n}{k}^p =2n^{p-3}\sum_{k=0}^{n-1}\binom{n-1}{k}^p\frac{3n-2k-2}{(k+1)^{p-2}}$.

binomial-coefficientssummation

If $n\ge1$ is any positive integer and $p$ is any integer, then
\begin{align*}
\sum_{k=0}^{n}\binom{n}{k}^p
=6\sum_{k=0}^{n-1}\binom{n}{k+1}^{p-2}\binom{n-1}{k}^{2}-&4\sum_{k=0}^{n-1}\binom{n}{k+1}^{p-3}\binom{n-1}{k}^{3}\tag{1}
\end{align*}

While studying Franel's numbers, i stumbled upon (1). However, i can only prove cases $p=1$ and $p=2$. \

CASE p=1
From (1), if $p=1$, we have
\begin{align*}
\sum_{k=0}^{n}\binom{n}{k}
=6\sum_{k=0}^{n-1}\binom{n}{k+1}^{-1}\binom{n-1}{k}^{2}-&4\sum_{k=0}^{n-1}\binom{n}{k+1}^{-2}\binom{n-1}{k}^{3}
\end{align*}

\begin{align*}
\sum_{k=0}^{n}\binom{n}{k}
=6\sum_{k=0}^{n-1}\frac{\binom{n-1}{k}}{\binom{n}{k+1}}\binom{n-1}{k}-&4\sum_{k=0}^{n-1}\left(\frac{\binom{n-1}{k}}{\binom{n}{k+1}}\right)^2\binom{n-1}{k}
\end{align*}

note that
$$\frac{\binom{n-1}{k}}{\binom{n}{k+1}}=\frac{k+1}{n}$$
So,
\begin{align*}
\sum_{k=0}^{n}\binom{n}{k}
=6\sum_{k=0}^{n-1}\left(\frac{k+1}{n}\right)\binom{n-1}{k}-&4\sum_{k=0}^{n-1}\left(\frac{k+1}{n}\right)^2\binom{n-1}{k}
\end{align*}

\begin{align*}
\sum_{k=0}^{n}\binom{n}{k}
=\frac{6}{n}\sum_{k=0}^{n-1}\binom{n-1}{k}(k+1)-&\frac{4}{n^2}\sum_{k=0}^{n-1}\binom{n-1}{k}(k+1)^2
\end{align*}

\begin{align*}
\sum_{k=0}^{n}\binom{n}{k}
=&\frac{6}{n}\left(\sum_{k=0}^{n-1}\binom{n-1}{k}k+\sum_{k=0}^{n-1}\binom{n-1}{k}\right)-\frac{4}{n^2}\left(\sum_{k=0}^{n-1}\binom{n-1}{k}k^2+2\sum_{k=0}^{n-1}\binom{n-1}{k}k+\sum_{k=0}^{n-1}\binom{n-1}{k}\right)
\end{align*}

We know that
$$\sum_{k=0}^{n-1}\binom{n-1}{k} =\frac{2^n}{2}$$
and
$$\sum_{k=0}^{n-1}\binom{n-1}{k}k =\frac{(n-1)2^{n}}{4}$$
and
$$\sum_{k=0}^{n-1}\binom{n-1}{k}k^2 =\frac{n(n-1)2^{n}}{8}$$

So,
$$\sum_{k=0}^{n}\binom{n}{k}
=\frac{6}{n}\left(\frac{(n-1)2^{n}}{4}+\frac{2^n}{2}\right)-\frac{4}{n^2}\left(\frac{n(n-1)2^{n}}{8}+2\frac{(n-1)2^{n}}{4}+\frac{2^n}{2}\right)$$

\begin{align*}
\sum_{k=0}^{n}\binom{n}{k}=&2^n\left(\frac{3}{n}\left(\frac{(n-1)}{2}+1\right)-\frac{2}{n^2}\left(\frac{n(n-1)}{4}+n\right)\right)
\end{align*}

$$\sum_{k=0}^{n}\binom{n}{k}=2^n\left(\frac{3(n+1)}{2n}-\frac{n+3}{2n}\right)$$
$$\sum_{k=0}^{n}\binom{n}{k}=2^n$$

CASE p=2
From (1), if $p=2$, we have

\begin{align*}
4\sum_{k=0}^{n-1}\binom{n}{k+1}^{-1}\binom{n-1}{k}^{3}
=&6\sum_{k=0}^{n-1}\binom{n-1}{k}^2-\sum_{k=0}^{n}\binom{n}{k}^2
\end{align*}

\begin{align*}
\sum_{k=0}^{n-1}\frac{\binom{n-1}{k}}{\binom{n}{k+1}}\binom{n-1}{k}^{2}
=&\frac{3}{2}\sum_{k=0}^{n-1}\binom{n-1}{k}^2-\frac{1}{4}\sum_{k=0}^{n}\binom{n}{k}^2
\end{align*}

\begin{align*}
\sum_{k=0}^{n-1}\frac{k+1}{n}\binom{n-1}{k}^{2}
=&\frac{3}{2}\sum_{k=0}^{n-1}\binom{n-1}{k}^2-\frac{1}{4}\sum_{k=0}^{n}\binom{n}{k}^2
\end{align*}

\begin{align*}
\frac{1}{n}\sum_{k=0}^{n-1}\binom{n-1}{k}^{2}(k+1)
=&\frac{3}{2}\sum_{k=0}^{n-1}\binom{n-1}{k}^2-\frac{1}{4}\sum_{k=0}^{n}\binom{n}{k}^2
\end{align*}

We know that
$$\sum_{k=0}^{n}\binom{n}{k}^{2} =\binom{2n}{n}=\frac{2(2n-1)(2n-2)!}{n(n-1)!^2}$$
and
$$\sum_{k=0}^{n-1}\binom{n-1}{k}^{2} =\binom{2n-2}{n-1}=\frac{(2n-2)!}{(n-1)!^2}$$
So,
\begin{align*}
\frac{1}{n}\sum_{k=0}^{n-1}\binom{n-1}{k}^{2}(k+1)
=&\frac{3(2n-2)!}{2(n-1)!^2}-\frac{2(2n-1)(2n-2)!}{4n(n-1)!^2}
\end{align*}

\begin{align*}
\sum_{k=0}^{n-1}\binom{n-1}{k}^{2}(k+1)
=&\frac{3n(2n-2)!}{2(n-1)!^2}-\frac{(2n-1)(2n-2)!}{2(n-1)!^2}
\end{align*}

\begin{align*}
\sum_{k=0}^{n-1}\binom{n-1}{k}^{2}(k+1)
=&\frac{(2n-2)!}{2(n-1)!}(n+1)
\end{align*}

\begin{align*}
\sum_{k=0}^{n-1}\binom{n-1}{k}^{2}k+\sum_{k=0}^{n-1}\binom{n-1}{k}^{2}
=&\frac{(2n-2)!}{2(n-1)!}(n+1)
\end{align*}

\begin{align*}
\sum_{k=0}^{n-1}\binom{n-1}{k}^{2}k+\frac{(2n-2)!}{(n-1)!}
=&\frac{(2n-2)!}{2(n-1)!}(n+1)
\end{align*}

\begin{align*}
\sum_{k=0}^{n-1}\binom{n-1}{k}^{2}k
=&\frac{(2n-2)!}{2(n-1)!}(n+1)-\frac{(2n-2)!}{(n-1)!}
\end{align*}

\begin{equation}
\sum_{k=0}^{n-1}\binom{n-1}{k}^{2}k
=\frac{(2n-2)!}{2(n-1)!}(n-1)\tag{2}
\end{equation}

From (2), let

$$S=\sum_{k=0}^{n-1}\binom{n-1}{k}^{2}k$$

So,
\begin{align*}
S=&\binom{n-1}{0}^20+\binom{n-1}{1}^21+\binom{n-2}{2}^22+\cdots+\binom{n-1}{n-1}^2(n-1).
\end{align*}

$$2S=\left[\binom{n-1}{0}^2 0+\binom{n-1}{1}^2 1+\binom{n-2}{2}^2 2+\cdots+\binom{n-1}{n-1}^2(n-1)\right]+\left[\binom{n-1}{n-1}^2(n-1)+\binom{n-1}{n-2}^2(n-2)+\binom{n-1}{n-3}^2(n-3)+\cdots+\binom{n-1}{0}^2 0\right]$$
Since $\binom{n-1}{k}^2=\binom{n-1}{n-k-1}^2$, we have
$$2S=\binom{n-1}{0}^2(n-1)+\binom{n-1}{1}^2(n-1)+\binom{n-2}{2}^2(n-1)+\cdots+\binom{n-1}{n-1}^2(n-1)$$

\begin{align*}
2S=&(n-1)\left[\binom{n-1}{0}^2+\binom{n-1}{1}^2+\binom{n-2}{2}^2+\cdots+\binom{n-1}{n-1}^2\right]
\end{align*}

$$2S=(n-1)\frac{(2n-2)!}{(n-1)!}$$
$$S=(n-1)\frac{(2n-2)!}{2(n-1)!}$$

Proving other cases of $p$ is currently elusive but i was able to get without proof that

\begin{align*}
\sum_{k=0}^{n}\binom{n}{k}^4 = 5\sum_{k=0}^{n}\binom{n}{k+1}^2\binom{n-1}{k}^2-&\frac{4n-1}{n}\sum_{k=0}^{n-1}{\binom{n-1}{k}}^4
\end{align*}

\begin{align*}
\sum_{k=0}^{n}\binom{n}{k}^4 = 20\sum_{k=0}^{n}\binom{n}{k+1}\binom{n-1}{k}^3-&6\frac{4n-1}{n}\sum_{k=0}^{n-1}{\binom{n-1}{k}}^4
\end{align*}

Also, i suspect that $p$ is true for any real number but i don't have any fact to back that up except for a few numerical examples that i carried out so, i am not taking that much seriously.

UPDATE
After a little manipulation, (1) can be reduced to;
$$\sum_{k=0}^{n}\binom{n}{k}^p
=2n^{p-3}\sum_{k=0}^{n-1}\binom{n-1}{k}^p\frac{3n-2k-2}{(k+1)^{p-2}}$$

Any help on other cases of positive integer $p$ or possibly a counter example will be appreciated.

Best Answer

The right-hand side of the claimed identity can be written as \begin{align*} &\color{blue}{2n^{p-3}\sum_{k=0}^{n-1}\binom{n-1}{k}^p\frac{3n-2k-2}{(k+1)^{p-2}}}\\ &\qquad\quad=2n^{p-3}\sum_{k=1}^n\binom{n-1}{k-1}^p\frac{3n-2k}{k^{p-2}}\tag{1}\\ &\qquad\quad=\frac{2}{n^3}\sum_{k=1}^n\binom{n}{k}^p(3n-2k)k^2\tag{2}\\ &\qquad\quad\,\,\color{blue}{=\sum_{k=0}^n\binom{n}{k}^p\left(\frac{6k^2}{n^2}-\frac{4k^3}{n^3}\right)}\tag{3} \end{align*}

Comment:

  • In (1) we shift the index to start with $k=1$.

  • In (2) we use the binomial identity $\binom{p}{q}=\frac{p}{q}\binom{p-1}{q-1}$.

Using (3) OPs claimed identity can be written as \begin{align*} \color{blue}{\sum_{k=0}^n\binom{n}{k}^p\left(1-\frac{6k^2}{n^2}+\frac{4k^3}{n^3}\right)=0 \qquad n\in\mathbb{N}, p\in\mathbb{C}}\tag{4} \end{align*}

Changing the order of summation $k\to n-k$ in (4) we obtain \begin{align*} &\color{blue}{\sum_{k=0}^n\binom{n}{k}^p\left(1-\frac{6k^2}{n^2}+\frac{4k^3}{n^3}\right)}\\ &\qquad=\sum_{k=0}^n\binom{n}{k}^p\left(1-\frac{6(n-k)^2}{n^2}+\frac{4(n-k)^3}{n^3}\right)\\ &\qquad=\sum_{k=0}^n\binom{n}{k}^p\left(1-\frac{6n^2-12nk+6k^2}{n^2}\right.\\ &\qquad\qquad\qquad\qquad\qquad\left. +\frac{4n^3-12n^2k+12nk^2-4k^3}{n^3}\right)\\ &\qquad\,\,\color{blue}{=-\sum_{k=0}^n\binom{n}{k}^p\left(1-\frac{6k^2}{n^2}+\frac{4k^3}{n^3}\right)} \end{align*} and the claim (4) follows.

Note: With respect to comments the identity (4) can be generalised to identities of the form \begin{align*} \sum_{k=0}^n f\left(\binom{n}{k}\right) g(k)=0 \end{align*} where $f,g$ are functions with $g(k)=-g(n-k),0\leq k\leq n$.