Welcome to MathOverflow

Question

4

1

Background

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.

edited Jan 23 2011 at 1:11

Yemon Choi
8,437●1●19●44

asked Jan 23 2011 at 0:55

sigma_z_1980
185●1●7

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 2011 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 2011 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 2011 at 4:08

1

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. :-) – Didier Piau Jan 23 2011 at 15:36

1

@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) – Didier Piau Jan 24 2011 at 0:55

show 14 more comments

Igor Rivin · Accepted Answer · 2011-01-23 18:17:50Z UTC

According to Mathematica, your sum equals:

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

or

$\, _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."

Square of Binomial Coefficient

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.