We know that $$\sum_{i=0}^{n}\binom{n}{i}=2^n$$ and that $$\sum_{i=0}^{n}\binom{n}{i}^2= \binom{2n}{n}$$ what about $$\sum_{i=0}^{n}\binom{n}{i}^3$$ ?
5
-
4$\begingroup$ There is no "closed form" for this similar to the other two cases, but the sequence defined by it satisfies a three-term linear recurrence with polynomial coefficients. See oeis.org/A000172 . $\endgroup$– Michael StollCommented Feb 20, 2015 at 18:47
-
11$\begingroup$ Somewhat remarkably, $\sum_{i=0}^n (-1)^i \left({n \atop i}\right)^{\!3}$ does have a known closed form (which is rather tricky to derive). $\endgroup$– Noam D. ElkiesCommented Feb 20, 2015 at 19:25
-
$\begingroup$ @NoamD.Elkies which is...? $\endgroup$– მამუკა ჯიბლაძეCommented Feb 20, 2015 at 21:39
-
5$\begingroup$ @მამუკაჯიბლაძე $$12\,{\frac {\sin \left( \pi \, \left( n+1 \right)/2 \right) \Gamma \left( 3\,n/2 \right) }{ \left( \Gamma \left( n/2 \right) \right) ^{3}{n}^{2}}} $$ $\endgroup$– Robert IsraelCommented Feb 20, 2015 at 22:14
-
9$\begingroup$ @მამუკაჯიბლაძე $0$ is $n$ is odd, otherwise $(-1)^{n/2} \binom{3n/2}{n/2,n/2,n/2}$. This is known as "Dixon's identity", and can be generalized as $\sum_{k=-a}^a(-1)^k{a+b\choose a+k} {b+c\choose b+k}{c+a\choose c+k} = \frac{(a+b+c)!}{a!b!c!}$. Although the original proofs were quite technical, there are at least 2 combinatorial proofs by Foata (see www-irma.u-strasbg.fr/~foata/paper/ProbComb.pdf, page 37 and tube.sfu-kras.ru/video/396?playlist=397 at 39:30). The shortest proofs are still the algebraic ones, for example by MachMahon's master theorem or Dyson's conjecture. $\endgroup$– Ofir GorodetskyCommented Feb 20, 2015 at 22:19
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
7
This sort of summation can be done using Gosper-type algorithms, see the A=B book by Petkovšek, Wilf and Zeilberger. The algorithms are built into Mathematica, so if you run
Table[k -> Sum[Binomial[n, i]^k, {i, 0, n}], {k, 0, 5}] // TableForm
you get
\begin{align*} 0&\to n+1 \\ 1&\to 2^n \\ 2&\to \binom{2 n}{n} \\ 3&\to \, _3F_2(-n,-n,-n;1,1;-1) \\ 4&\to \, _4F_3(-n,-n,-n,-n;1,1,1;1) \\ 5&\to \, _5F_4(-n,-n,-n,-n,-n;1,1,1,1;-1) \\ \end{align*}
The hypergeometric functions $_kF_m$ appearing in the result are documented under the name HypergeometricPFQ in Mathematica. Since these are just rephrasing the original sum, the algorithm is telling us that there is no closed-form solution expressible as a rational function.
answered Feb 20, 2015 at 18:58
-
4$\begingroup$ Actually these ${}_kF_m$ representations are pretty close to direct transcriptions of the summation, i.e. by definition $$ {}_3F_2(-n,-n,-n;1,1;-1) = \sum_{k=0}^\infty \dfrac{(-1)^k}{k!} \dfrac{\text{pochhammer}(-n,k)^3}{\text{pochhammer}(1,k)^2}$$ and the term for $k$ turns out to be ${n \choose k}^3$ for $0 \le k \le n$, $0$ for $k > n$. $\endgroup$ Commented Feb 20, 2015 at 19:25
-
12$\begingroup$ I am not sure this is a good example for the power of that algorithm, since I think (but might be wrong) really nothing much happens here and this is a renaming basically. $\endgroup$– user9072Commented Feb 20, 2015 at 19:26
-
$\begingroup$ In Mathematica, the command FullSimplify[Sum[Binomial[n, i]^3, {i, 0, n}]] returns HypergeometricPFQ[{-n, -n, -n}, {1, 1}, -1] $\endgroup$– StoppleCommented Feb 20, 2015 at 20:39
-
1$\begingroup$ The algorithm is telling you that there is no closed form in terms of rational functions. Of course, the hypergeometric functions are just a dressing -- but so is the binomial symbol for $k = 2$. $\endgroup$ Commented Feb 20, 2015 at 20:43
-
$\begingroup$ If this was your point may I propose a different phrasing of the first sentence 'This sort of summation can be done [...]' suggests (to me) some actual success. By analogy, it is relevant information when Risch' algorthm does not produce an antiderivative for a function, yet to say this integeration can be done using Risch' algorthm seems misleading to me in such a case. $\endgroup$– user9072Commented Feb 21, 2015 at 14:40
$\begingroup$
$\endgroup$
These are called the Franel Numbers
As Michael noted, see oeis.org/A000172 for a summary of known facts and references...
answered Feb 20, 2015 at 23:34