Squared Binomial Coefficient – Combinatorial Analysis

Question

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?

Answer 1

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.