Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.


I'm modeling Genetic Algorithm(GA) with Markov chains and deriving the expression for the expectation of the first hittig time in the MC with 1 absorbing state and $l-1$ transient states. This results is an expression for a sum involving square of a binomial coefficient

Problem I need to find a closed expression for $$\sum_{k=0}^{l/2} \binom{l/2}{k}^2 p^{2k}$$

where $p$ is a function of $l$ and lies between 0 and 1.

So far I've found a closed expression for $$\sum_{k=0}^{n}k^2 \binom{n}{k}^2$$

Any suggestions are very much appreciated.

share|improve this question
I'm confused: why do you think there is hope to find a closed-form formula for your expression without knowing the exact dependence between p and l? –  Thierry Zell Jan 23 '11 at 1:48
@Thierry, if the binomial coefficient weren't squared, there would be the closed-form expression $(1+p^2)^{\ell/2}$, so maybe there's one here, too. –  Gerry Myerson Jan 23 '11 at 2:39
OK, let's say $p=\frac{1}{l}$ or $1-\frac{1}{l}$. Does this help. I mean I hope to find such formula as a closed form for arbitrary p. –  sigma_z_1980 Jan 23 '11 at 4:08
Using the notation $n=\ell/2$, your first sum is the coefficient of $x^n$ in the polynomial $(1+x)^n(1+p^2x)^n$. As such, it can be evaluated as the integral of a complex valued rational function on the unit circle of the complex plane. Not that his helps much... As regards the $_2F_1$ expression provided by Mathematica, I believe this function is the exact expansion along increasing powers of $p$ which is written in the original question. :-) –  Did Jan 23 '11 at 15:36
@sigma: Sorry I was not more explicit. Here is a way to get at the result. Gerry is right, one works in the space $\mathbb{R}[x]$ of the polynomials wih one indeterminate $x$. Let us forget the coefficient $p$ for a moment and note that ${n \choose k}^2={n \choose k}{n \choose n-k}$, that ${n \choose k}$ is the coefficient of $x^k$ in $P(x)=(1+x)^n$ and that ${n \choose n-k}$ is the coefficient of $x^{n-k}$ in $Q(x)=(1+x)^n$ (yes I know, $P(x)=Q(x)$ but just wait and you will see). (to be cont'd) –  Did Jan 24 '11 at 0:55

1 Answer 1

up vote 5 down vote accepted

According to Mathematica, your sum equals:

$(1-p^2)^{l/2} \mbox{LegendreP}\left(l/2, \frac{1+p^2}{1-p^2}\right),$


$\, _2F_1\left(-\frac{l}{2},-\frac{l}{2};1;p^2\right)$

The second sum is $n^2 \binom{2 n-2}{n-1}.$

Ain't technology grand...

EDIT The real question is: why do you want to know? The expressions I give above allow you to get asymptotics, get ODE satisfied by the functions, etc, etc. If you want an expression in terms of "elementary functions" (whatever that means in this case), with very high probability there are not any (this is less certain here because these are definite summmations). I strongly advise you to read Petkovsek and Zeilberger's "A=B."

share|improve this answer
I'd like to get a closed expression because this will provide more understanding of convergence of Evolutionary algorithms, as this probability is important to obtain an exact expression for the expectation of the 1st hitting time. –  sigma_z_1980 Jan 23 '11 at 21:29

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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