I've got the following finite sum: $s_{n}=\sum\limits_{k=0}^{n}\binom{n}{k}^2p^k$ (esp. if $p$ is a function of $n$, like $p=\frac1{n}$), which can be rewritten as $s_{n}=\sum\limits_{k=0}^{n}\binom{n}{k}\sqrt p^k\binom{n}{k}\sqrt p^k$. Using the generating function approach (from Graham, Knuth and Patashnik) with each of the polynomials in the sum, I get the expression $(1+\sqrt p x)^{2n}$ and the coefficient at the n-th term $x$ turns out to be $\binom{2n}{n} \sqrt p^n$. But comparing this result to the computational value, it turns out to be incorrect. Where did I make a mistake? Are there certain limitations on the generating function method?


I believe you're using the convolution formula wrong. The convolution formula says that if $F(x)$ and $G(x)$ are the generating functions of $f_n$ and $g_n$, then $F(x) G(x)$ is the generating function of $\sum_{k=0}^n f_k g_{n-k}$. You appear to be taking $f_k = g_k = \binom{n}{k} \sqrt{p}^k$. Then the expression $(1 + \sqrt{p}x)^{2n}$ is the generating function for the convolution $$\sum_{k=0}^n \binom{n}{k} \sqrt{p}^k \binom{n}{n-k} \sqrt{p}^{n-k} = \sum_{k=0}^n \binom{n}{k}^2 \sqrt{p}^n,$$ which is not the sum you want.

Instead, let $f_k = \binom{n}{k} p^k$ and $g_k = \binom{n}{k}$. Now the convolution is the sum you want: $$\sum_{k=0}^n \binom{n}{k} p^k \binom{n}{n-k} = \sum_{k=0}^n \binom{n}{k}^2 p^k.$$ The generating function for $f_k$ is $(1+px)^n$, and the generating function for $g_k$ is $(1 + x)^n$, so your answer is the coefficient of $x^n$ in $(1+px)^n (1+x)^n$. However, I'm not sure what a closed form for that would be.

Your sum can be expressed in terms of Legendre polynomials $P_n(x)$, though. Use the known formula (see eq. 33 on the linked page) $$P_n(x) = \frac{1}{2^n} \sum_{k=0}^n \binom{n}{k}^2 (x-1)^{n-k} (x+1)^k.$$ If we let $x = \frac{1+p}{1-p}$, we have $$P_n\left(\frac{1+p}{1-p}\right) = \frac{1}{2^n} \sum_{k=0}^n \binom{n}{k}^2 \left(\frac{1+p}{1-p}-1\right)^{n-k} \left(\frac{1+p}{1-p}+1\right)^k $$ $$= \frac{1}{2^n} \sum_{k=0}^n \binom{n}{k}^2 \left(\frac{2p}{1-p}\right)^{n-k} \left(\frac{2}{1-p}\right)^k = \frac{1}{(1-p)^n} \sum_{k=0}^n \binom{n}{k}^2 p^{n-k}$$ $$ = \frac{1}{(1-p)^n} \sum_{k=0}^n \binom{n}{k}^2 p^k.$$

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

Disclaimer: The Legendre polynomial expression was the output from Mathematica when I asked it to evaluate the sum. I wasn't ready to put my trust in it until I proved it myself, though. :)

Added: The sum in question is Problem 5.101b in Graham, Knuth, and Patashnik's Concrete Mathematics (2nd edition). In the answers they give the Legendre polynomial expression I prove here and the recurrence relation (where $S_n(p)$ is the OP's sum)

$$(n+1)(p-1)^2 S_n(p) - (2n+3)(p+1)S_{n+1}(p) + (n+2)S_{n+2}(p) = 0.$$

They do not provide a closed form expression other than the Legendre polynomial formulation. Given how thorough the answers in Concrete Mathematics usually are, that makes me doubt strongly that one is known or would be easy to find.

  • $\begingroup$ thanks Mike, this makes sense $\endgroup$ – sigma.z.1980 Mar 20 '11 at 0:53

I don't have Mathematica with me, so let's see if I can get to Mike's answer only by exploiting hypergeometric identities...

Starting with

$$s_n=\sum_{k=0}^n \binom{n}{k}^2p^k$$

the usual binomial-to-Pochhammer conversion is easily applied, leading to

$$s_n=\sum_{k=0}^n \frac{((-n)_k)^2}{(k!)^2} p^k$$

from which we easily obtain the hypergeometric form

$$s_n={}_2 F_1\left({{-n}\atop{}}{{}\atop{1}}{{-n}\atop{}}\mid p\right)$$

Okay, I hear some groaning that the Gaussian hypergeometric function is not much of a closed form, and I agree. So let's see if we can turn it into something more recognizable.

The trouble here is that the "nice" cases for Gaussian hypergeometric functions with nonpositive numerator parameters have only one of the two numerator parameters nonpositive; to turn it into that sort, we try the Pfaff transformation:

$$s_n=(1-p)^n {}_2 F_1\left({{-n}\atop{}}{{}\atop{1}}{{n+1}\atop{}}\mid \frac{p}{p-1}\right)$$

and now it looks like something familiar:

$$P_n(1-2z)={}_2 F_1\left({{-n}\atop{}}{{}\atop{1}}{{n+1}\atop{}}\mid z\right)$$

where $P_n(z)$ is the Legendre polynomial. (One way to establish this identity is to note that the second order differential equation for the Gaussian hypergeometric function can be turned into the differential equation for Legendre functions when the proper substitutions are done.) With that, we finally have

$$s_n=(1-p)^n P_n\left(1-2\frac{p}{p-1}\right)=(1-p)^n P_n\left(\frac{1+p}{1-p}\right)$$

and we're done.

  • $\begingroup$ thanks JM, yeah, this looks good. This probability arises in some Markov chains transition probabilities. The real hard stuff comes next-when you have to sum 'em up, multiply, etc $\endgroup$ – sigma.z.1980 May 11 '11 at 4:04
  • $\begingroup$ @sigma: On a more practical note, should you need to evaluate this sum for any $p\neq1$ and a number of consecutive values of $n$, you are now able to exploit the usual three-term recurrence for the Legendre polynomials. $\endgroup$ – J. M. is a poor mathematician May 11 '11 at 4:09
  • $\begingroup$ do you mean $P_{n}(z)+P_{n+1}(z)$? $\endgroup$ – sigma.z.1980 May 11 '11 at 7:24
  • $\begingroup$ @sigma: Yes, $P_n(z)$ is expressible in terms of $P_{n-1}(z)$ and $P_{n-2}(z)$. $\endgroup$ – J. M. is a poor mathematician May 11 '11 at 9:00
  • $\begingroup$ I'd be even more interested in something like $\frac{1}{P_{n}(z)}$ or even $\frac{1}{1-P_{n}(z)}$ and these do not seem to exist at all. Product of hypergeometric functions almost certainly doesn't, I've already aked this question elesewhere $\endgroup$ – sigma.z.1980 May 12 '11 at 8:59

The sum in question has also another ``closed form''. We have: \begin{eqnarray} \sum\limits_{k=0}^n (\binom{n}{k})^2 p^k &=& \int\limits_0^{2 \pi} \left( 1+ \sqrt{p} e^{\imath \phi}\right)^n\cdot \left(1+ \sqrt{p} e^{-\imath \phi} \right)^n \frac{d \phi}{2 \pi} \\ &=& \int\limits_0^{2 \pi} \left( \sqrt{p} (2 \cos(\frac{\phi}{2}) )^2 + (1- \sqrt{p})^2 \right)^n \\ &=& \sum\limits_{k=0}^n \binom{n}{k} (1- \sqrt{p})^{2n-2k} \cdot (\sqrt{p})^k \cdot \binom{2 k}{k} \\ &=& \left(1-\sqrt{p}\right)^{2 n} \, _2F_1\left(\frac{1}{2},-n;1;-\frac{4 \sqrt{p}}{\left(\sqrt{p}-1\right)^2}\right)\\ &=& \sum\limits_{k=0}^n \binom{n}{k} (1+p)^{n-2 k} p^k \binom{2 k}{k}\\ &=&(p+1)^n \, _2F_1\left(\frac{1-n}{2},-\frac{n}{2};1;\frac{4 p}{(p+1)^2}\right) \end{eqnarray} Critics will be giving out that the representations in terms of hypergeometric functions do not give much since they themselves are finite sums. Yet at least the last reperesntation is useful when $p=1$ then using the Gauss' formula we get $2^n \binom{n-1/2}{n/2}$ which by using the duplication formula for the Gamma function gives $\binom{2n}{n}$ as it should be .


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.