Value of $\displaystyle \frac{p}{q}$ in binomial expression.

Question

If $\displaystyle p=\sum^{r}_{k=0}\binom{n}{2k}\binom{n-2k}{r-k}$ and $\displaystyle q=\sum^{n}_{k=r}\binom{n}{k}\binom{2k}{2r}\bigg(\frac{3}{4}\bigg)^{n-k}\bigg(\frac{1}{2}\bigg)^{2k-2r}$ , where $n\geq 2r$.

Then value of $\displaystyle \frac{p}{q}$

First I am try to simplify $p$ and $q$

$\displaystyle p=\sum^{r}_{k=0}\frac{n!}{2k!\cdot (n-2k)!}\times \frac{(n-2k)!}{(r-k)!\cdot (n-k-r)!}=\sum^{r}_{k=0}\frac{n!}{(2k)!\cdot (r-k)!\cdot (n-r-k)!}$

But I have seems that there is no closed form for $p$

And $\displaystyle q=\sum^{n}_{k=r}\frac{n!}{k!\cdot (n-k)!}\cdot \frac{(2k)!}{(2r)!\cdot (2k-2r)!}\bigg(\frac{3}{4}\bigg)^{n-k}\bigg(\frac{1}{2}\bigg)^{2k-2r}$

I did not understand how can I simplify $p$ and $q$ seems that something tricky in simplifying $p$ and $q$

Please have a look on that problem

Answer 1

It's just the same old Snake Oil method. Multiply through by $x^r$, sum over $r$, exchange the order of summation, find the closed form, extract the coefficient at $x^r$ or compare the generating functions, and then do whatever you want with the resulting $p$ and $q$. In fact, I will rename them $p_r$ and $q_r$ to mark their dependence on $r$.

In other words, $$ \begin{split} \sum_{r=0}^{\infty}{p_rx^r} &=\sum_{r=0}^{\infty}\sum_{k=0}^{r}\binom{n}{2k}\binom{n-2k}{r-k}x^r\\ &=\sum_{0\le k\le r}\binom{n}{2k}\binom{n-2k}{r-k}x^r\\ &=\sum_{k=0}^{\infty}\sum_{r=k}^{\infty}\binom{n}{2k}\binom{n-2k}{r-k}x^r\\ &=\sum_{k=0}^{\infty}\sum_{r=0}^{\infty}\binom{n}{2k}\binom{n-2k}{r}x^{r+k}\\ &=\sum_{k=0}^{\infty}\binom{n}{2k}x^k\left(\sum_{r=0}^{\infty}\binom{n-2k}{r}x^r\right)\\ &=\sum_{k=0}^{\infty}\binom{n}{2k}x^k(1+x)^{n-2k}\\ &=(1+x)^n\sum_{k=0}^{\infty}\binom{n}{2k}\left(\frac{\sqrt{x}}{1+x}\right)^{2k} \end{split} $$ Now $$ \sum_{k=0}^{\infty}\binom{n}{2k}t^{2k}=\frac{1}{2}\left(\sum_{k=0}^{\infty}\binom{n}{k}t^k+\sum_{k=0}^{\infty}\binom{n}{k}(-t)^k\right)=\frac{1}{2}\left((1+t)^n+(1-t)^n\right), $$ so the sum above is $$ \begin{split} \sum_{r=0}^{\infty}{p_rx^r}&=\frac{1}{2}(1+x)^n\left(\left(1+\frac{\sqrt{x}}{1+x}\right)^n+\left(1-\frac{\sqrt{x}}{1+x}\right)^n\right)\\ &=\frac{\left(1+\sqrt{x}+x\right)^n+\left(1-\sqrt{x}+x\right)^n}{2}. \end{split} $$ Similarly, $$ \begin{split} \sum_{r=0}^{\infty}q_rx^r &=\sum_{r=0}^{\infty}\sum_{k=r}^{n}\binom{n}{k}\binom{2k}{2r}\left(\frac{3}{4}\right)^{n-k}\left(\frac{1}{2}\right)^{2k-2r}x^r\\ &=\sum_{r=0}^{\infty}\sum_{k=0}^{n-r}\binom{n}{k}\binom{2n-2k}{2r}\left(\frac{3}{4}\right)^{k}\left(\frac{1}{2}\right)^{2n-2r-2k}x^r\\ &=\sum_{r=0}^{\infty}\sum_{k=0}^{n-r}\binom{n}{k}\binom{2n-2k}{2r}\left(\frac{3}{4}\right)^{k}\left(\frac{1}{4}\right)^{n-r-k}x^r\\ &=\sum_{k=0}^{n}\sum_{r=0}^{n-k}\binom{n}{k}\left(\frac{3}{4}\right)^{k}\left(\frac{1}{4}\right)^{n-k}\binom{2n-2k}{2r}4^rx^r\\ &=\frac{1}{4^n}\sum_{k=0}^{n}\binom{n}{k}3^k\left(\sum_{r=0}^{n-k}\binom{2n-2k}{2r}\left(2\sqrt{x}\right)^{2r}\right)\\ &=\frac{1}{2\cdot4^n}\sum_{k=0}^{n}\binom{n}{k}3^k\left((1+2\sqrt{x})^{2n-2k}+(1-2\sqrt{x})^{2n-2k}\right)\\ &=\frac{1}{2\cdot4^n}\left(\left(3+(1+2\sqrt{x})^2\right)^n+\left(3+(1-2\sqrt{x})^2\right)^n\right)\\ &=\frac{1}{2\cdot4^n}\left(\left(4+4\sqrt{x}+4x\right)^n+\left(4-4\sqrt{x}+4x\right)^n\right)\\ &=\frac{\left(1+\sqrt{x}+x\right)^n+\left(1-\sqrt{x}+x\right)^n}{2}. \end{split} $$

Thus, the generating functions of the sequences $(p_r)$ and $(q_r)$ are equal for any $n$, so $p_r=q_r$ for any $n$ and $r$, and thus their ratio is $1$ whenever they are nonzero.

The triangular array of values of $p(n,r)=q(n,r)$ for $0\le r\le n$ is the OEIS sequence A056241.

Answer 2

We will show that using Egorychev method

$$\sum_{k=0}^r {n\choose 2k} {n-2k\choose r-k} = \sum_{k=r}^n {n\choose k} {2k\choose 2r} \left(\frac{3}{4}\right)^{n-k} \left(\frac{1}{2}\right)^{2k-2r}.$$

Computation for LHS

We get for LHS

$$\sum_{k=0}^r {n\choose n-2k} {n-2k\choose r-k} \\ = [z^n] (1+z)^n [w^r] (1+w)^n \sum_{k\ge 0} z^{2k} \frac{w^k}{(1+w)^{2k}}.$$

Here we have extended to infinity due to the coefficient extractor in $w$. We obtain

$$[z^n] (1+z)^n [w^r] (1+w)^n \frac{1}{1-z^2 w/(1+w)^2} \\ = [z^n] (1+z)^n [w^r] (1+w)^{n+2} \frac{1}{(1+w)^2-wz^2} \\ = [z^n] (1+z)^n [w^{2r}] (1+w^2)^{n+2} \frac{1}{(1+w^2)^2-w^2z^2} \\ = [z^n] (1+z)^n [w^{2r}] (1+w^2)^{n+2} \frac{1}{1+wz+w^2}\frac{1}{1-wz+w^2} \\ = - [z^n] (1+z)^n [w^{2r+2}] (1+w^2)^{n+2} \frac{1}{z+(1+w^2)/w}\frac{1}{z-(1+w^2)/w}.$$

The contribution from $z$ is

$$\;\underset{z}{\mathrm{res}}\; \frac{1}{z^{n+1}} (1+z)^n \frac{1}{z+(1+w^2)/w}\frac{1}{z-(1+w^2)/w}.$$

Here the residue at infinity is zero so we may use minus the residues at $z=\pm (1+w^2)/w.$ We get first

$$[w^{2r+2}] (1+w^2)^{n+2} (-1)^{n+1} \frac{w^{n+1}}{(1+w^2)^{n+1}} \frac{(-1+w-w^2)^n}{w^n} \frac{1}{-2(1+w^2)/w} \\ = \frac{1}{2} [w^{2r}] (w^2-w+1)^n = \frac{1}{2} (-1)^{2r} [w^{2r}] (w^2-w+1)^n \\ = \frac{1}{2} [w^{2r}] (w^2+w+1)^n.$$

and second

$$[w^{2r+2}] (1+w^2)^{n+2} \frac{w^{n+1}}{(1+w^2)^{n+1}} \frac{(w^2+w+1)^n}{w^n} \frac{1}{2(1+w^2)/w} \\ = \frac{1}{2} [w^{2r}] (w^2+w+1)^n.$$

Collecting everything,

$$[w^{2r}] (w^2+w+1)^n.$$

Computation for RHS

We have for RHS

$$\left(\frac{3}{4}\right)^n \left(\frac{1}{2}\right)^{-2r} \sum_{k=r}^n {n\choose n-k} {2k\choose 2r} \left(\frac{4}{3}\right)^k \left(\frac{1}{2}\right)^{2k} \\ = \left(\frac{3}{4}\right)^n \left(\frac{1}{2}\right)^{-2r} [z^n] (1+z)^n [w^{2r}] \sum_{k=r}^n z^k (1+w)^{2k} \left(\frac{1}{3}\right)^k$$

We may lower $k$ to zero owing to the coefficient extractor in $w$ and raise to infinity due to the extractor in $z$ to get

$$\left(\frac{3}{4}\right)^n \left(\frac{1}{2}\right)^{-2r} [z^n] (1+z)^n [w^{2r}] \frac{1}{1-z(1+w)^2/3} \\ = 3^n 2^{2r-2n} [z^n] (1+z)^n [w^{2r}] \frac{1}{1-z(1+w)^2/3} \\ = 2^{2r-2n} [z^n] (1+3z)^n [w^{2r}] \frac{1}{1-z(1+w)^2} \\ = - 2^{2r-2n} [z^n] (1+3z)^n [w^{2r}] \frac{1}{(1+w)^2} \frac{1}{z-1/(1+w)^2}.$$

The contribution from $z$ is

$$\;\underset{z}{\mathrm{res}}\; \frac{1}{z^{n+1}} (1+3z)^n \frac{1}{z-1/(1+w)^2}.$$

Here the residue at infinity is zero so we may use minus the residue at $z=1/(1+w)^2$ to get

$$ 2^{2r-2n} [w^{2r}] \frac{1}{(1+w)^2} (1+w)^{2n+2} (1+3/(1+w)^2)^n \\ = 2^{2r-2n} [w^{2r}] (4+2w+w^2)^n = 2^{-2n} [w^{2r}] (4+4w+4w^2)^n \\ = [w^{2r}] (w^2+w+1)^n.$$

We have equality and thus the claim. Here we had some help from OEIS A005714.

Answer 3

We transform the binomial expressions into hypergeometric series and show this way equality.

Left-hand side:

Starting with the left-hand side we obtain using rising factorials $(a)_{k}:=a(a+1)\cdots(a+k-1)$ \begin{align*} \color{blue}{\sum_{k=0}^r}&\color{blue}{\underbrace{\binom{n}{2k}\binom{n-2k}{r-k}}_{=:t_k}}\\ &=\sum_{k=0}^r t_k\\ &= t_0\sum_{k=0}^r\prod_{j=0}^{k-1}\frac{t_{j+1}}{t_j}\\ &=\binom{n}{r}\sum_{k=0}^r\prod_{j=0}^{k-1}\left(\binom{n}{2j+2}\binom{n-2j-2}{r-j-1}\binom{n}{2j}^{-1}\binom{n-2j}{r-j}^{-1}\right)\\ &=\binom{n}{r}\sum_{k=0}^r\prod_{j=0}^{k-1}\left(\frac{1}{4}\frac{(j-r)(j-n+r)}{(j+1)\left(j+\frac{1}{2}\right)}\right)\\ &=\binom{n}{r}\sum_{k=0}^{r}\frac{(-r)_k(r-n)_{k}}{\left(\frac{1}{2}\right)_k}\left(\frac{1}{4}\right)^k\frac{1}{k!}\\ &\,\,\color{blue}{= \binom{n}{r}\ _2F_1\left(-r,r-n;\frac{1}{2};\frac{1}{4}\right)}\tag{1} \end{align*}

Right-hand side:

We obtain \begin{align*} \color{blue}{\sum_{k=r}^n}&\color{blue}{ \binom{n}{k}\binom{2k}{2r}\left(\frac{3}{4}\right)^{n-k}\left(\frac{1}{2}\right)^{2k-2r}}\\ &=\sum_{k=0}^{n-r}\binom{n}{k+r}\binom{2k+2r}{2r}\left(\frac{3}{4}\right)^{n-k-r}\left(\frac{1}{4}\right)^k\\ &=\left(\frac{3}{4}\right)^{n-r}\sum_{k=0}^{n-r}\underbrace{\binom{n}{k+r}\binom{2k+2r}{2r}\left(\frac{1}{3}\right)^k}_{=:t_k}\\ &=\left(\frac{3}{4}\right)^{n-r}\sum_{k=0}^{n-r} t_k\\ &= \left(\frac{3}{4}\right)^{n-r}t_0\sum_{k=0}^{n-r}\prod_{j=0}^{k-1}\frac{t_{j+1}}{t_j}\\ &=\left(\frac{3}{4}\right)^{n-r}\binom{n}{r}\sum_{k=0}^{n-r}\prod_{j=0}^{k-1} \left(\binom{n}{j+1+r}\binom{2j+2+2r}{2r}\left(\frac{1}{3}\right)^{j+1}\right.\\ &\qquad\qquad\qquad\qquad\qquad\qquad\left.\cdot\binom{n}{j+r}^{-1}\binom{2j+2r}{2r}^{-1}\left(\frac{1}{3}\right)^{-j}\right)\\ &=\left(\frac{3}{4}\right)^{n-r}\binom{n}{r}\sum_{k=0}^{n-r}\prod_{j=0}^{k-1} \left(\frac{\left(j+r+\frac{1}{2}\right)(j-n+r)\left(-\frac{1}{3}\right)}{(j+1)\left(j+\frac{1}{2}\right)}\right)\\ &=\left(\frac{3}{4}\right)^{n-r}\binom{n}{r}\sum_{k=0}^{n-r}\frac{\left(r+\frac{1}{2}\right)_k(r-n)_k} {\left(\frac{1}{2}\right)_k}\left(-\frac{1}{3}\right)^k\frac{1}{k!}\\ &\,\,\color{blue}{=\left(\frac{3}{4}\right)^{n-r}\binom{n}{r}\ _2F_1\left(r+\frac{1}{2},r-n;\frac{1}{2};-\frac{1}{3}\right)}\tag{2} \end{align*}

Pfaff Transformation:

Applying to (1) the Pfaff transformation \begin{align*} \,\,\color{blue}{_2F_1\left(a,b;c;z\right)=(1-z)^{-b}\ _2F_1\left(c-a,b;c;\frac{z}{z-1}\right)} \end{align*} and equality of (1) and (2) follows.