7
$\begingroup$

We know that $$ \sum_{k=0}^n \binom{n}{k} = 2^n\;\; \text{ and }\;\; \sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n} $$ hold for all $n\in \mathbb{N}_0$. Now I tried to find a similar expression for $$ \sum_{k=0}^n \binom{n}{k}^3 $$ but didn't get anywhere at all. What I found were only asymptotic estimates (see Sum of cubes of binomial coefficients or Asymptotics of $\sum_{k=0}^{n} {\binom n k}^a$).

Now is there a closed form for this sum or, what would be even better, for $\sum_{k=0}^n \binom{n}{k}^\alpha$ with any $\alpha \in \mathbb{N}_0$?

$\endgroup$
5
$\begingroup$

These numbers are called the Franel Numbers. It's proven in (Petkovšek, M., Wilf, H. and Zeilberger, D. (1996). A=B. Wellesley, MA: A K Peters. p. 160) that there is no closed form for these numbers, in terms of the sum of a fixed number of hypergeometric terms.

However, as @Robert_Israel points out, the expression could possibly be represented by different types of closed form.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ ... if "closed form" is defined as "the sum of a fixed number of hypergeometric terms". There could be other types of "closed form". $\endgroup$ – Robert Israel Nov 28 '18 at 18:24
  • $\begingroup$ @Robert Was just thinking that. Thanks for the suggestion. $\endgroup$ – Jam Nov 28 '18 at 18:26
1
$\begingroup$

The binomial coefficient for a given pair of $n \geq k \geq 0$ integers can be expressed in terms of a Pochhammer symbol as the following.

$$ \binom n k = \frac{(-1)^k(-n)_k} {k!}. $$

The expression is valid even if $n$ is an arbitrary real number.

Here we note two things.

  1. The Pochhammer symbol $(-n)_k$ is zero, if $n \geq 0$ and $k > -n$.
  2. The factorial $k!$ can be written as $(1)_k$.

Using these observations, we can express your sums in terms of a generalized hypergeometric function $_pF_q$ as the following. For the sum of the binomial coefficients, we have

$$ \sum_{k=0}^n \binom n k = \sum_{k=0}^n \frac{(-1)^k(-n)_k}{k!} = \sum_{k=0}^\infty (-n)_k{\frac{(-1)^k}{k!}} = {_1F_0}\left({{-n}\atop{-}}\middle|\,-1\right). $$ For the sum the square of the binomial coefficients, we have $$ \sum_{k=0}^n {\binom n k}^2 = \sum_{k=0}^n \left(\frac{(-1)^k(-n)_k}{k!}\right)^2 = \sum_{k=0}^\infty \frac{\left((-n)_k\right)^2}{k!} \cdot \frac{1}{k!} = {_2F_1}\left({{-n, -n}\atop{1}}\middle|\,1\right). $$ And for the sum of the cube of the binomial coefficients $-$ also known as Franel numbers $-$, we have $$ \sum_{k=0}^n {\binom n k}^3 = \sum_{k=0}^n \left(\frac{(-1)^k(-n)_k}{k!}\right)^3 = \sum_{k=0}^\infty \frac{\left((-n)_k\right)^3}{(k!)^2} \cdot \frac{(-1)^k}{k!} = {_3F_2}\left({{-n, -n, -n}\atop{1, 1}}\middle|\,-1\right). $$ In general, for a positive integer $r$, we have the binomial sum

$$ \begin{align*} \sum_{k=0}^n {\binom n k}^r &= \sum_{k=0}^n \left(\frac{(-1)^k(-n)_k}{k!}\right)^r = \sum_{k=0}^\infty \frac{\left((-n)_k\right)^r}{(k!)^{r-1}} \cdot \frac{(-1)^{rk}}{k!} \\ &= {_rF_{r-1}}\left({{-n, -n, \dots, -n}\atop{1, \dots, 1}}\middle|\,(-1)^r\right). \end{align*} $$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.