4
$\begingroup$

So basically I want to find the closed form of $G_n = \sum_{k = 1}^n \binom{n+k - 1}{2k-1}$.

After checking for $n = 1,2,3,4$ the values are $1, 3, 8, 21$ respectively. I claim that it is $F_{2n}$ where $F_0 = 0, F_1 = 1$ and $F_n = F_{n-1} + F_{n-2}$. My idea was to prove this using generating functions.

We have that $\binom{n+k-1}{2k-1}$ is the $n$th coefficient of $X^k \sum_{i \geq 0} \binom{i + 2k - 1}{i} X^i = \frac{X^k}{(1-X)^{2k}}$ so the $$\sum_{n \geq 0} G_n X^n = \sum_{k = 1}^n \frac{X^k}{(1-X)^{2k}}$$

Now we want to find what $F_0 + F_2X + F_4X^2 + ...$ is and we know that $F_0 + F_1X + ... = \frac{X}{1-X-X^2}$.

So \begin{align*} F_0 + F_2X^2 + F_4X^4 + ... & = \frac{1}{2} \left ( \frac{X}{1-X-X^2} + \frac{-X}{1 + X - X^2} \right ) \\ & = \frac{X^2}{(1-X^2)^2 - X^2} \end{align*} which means $$F_0 + F_2X + F_4X^2 + ... = \frac{X}{(1-X)^2 - X}.$$

So if suffices to show \begin{align*} \frac{X}{(1-X)^2 - X} & = \sum_{k = 1}^n \frac{X^k}{(1-X)^{2k}} \\ \frac{1}{(1-X)^2 - X} & = \sum_{k = 1}^n \frac{X^{k-1}}{(1-X)^{2k}} \\ \frac{(1-X)^{2n}}{(1-X)^2 - X} & = ((1-X)^2)^{n-1} + ((1-X)^2)^{n-2}X + ... + X^{n-1} \\ \frac{(1-X)^{2n}}{(1-X)^2 - X} & = \frac{(1-X)^{2n} - X^n}{(1-X)^2 - X} \end{align*} which is not true. I don't see where I went wrong with this.

$\endgroup$
3
$\begingroup$

Hint: There is just a small calculation error when transforming $\binom{n+k-1}{2k-1}$.

We obtain \begin{align*} \sum_{n=0}^\infty G_nx^n&=\sum_{n=0}^\infty\sum_{k=1}^n\binom{n+k-1}{2k-1}x^n\\ &=\sum_{k=1}^\infty\sum_{n=k}^\infty\binom{n+k-1}{2k-1}x^n\tag{1}\\ &=\sum_{k=1}^\infty\sum_{n=0}^\infty\binom{n+2k-1}{2k-1}x^{n+k}\tag{2}\\ &=\sum_{k=1}^\infty x^k\sum_{n=0}^\infty\binom{-2k}{n}(-x)^n\tag{3}\\ &=\sum_{k=1}^\infty \frac{x^k}{(1-x)^{2k}}\tag{4}\\ &=\frac{\frac{x}{(1-x)^2}}{1-\frac{x}{(1-x)^2}}\tag{5}\\ &=\frac{x}{1-3x+x^2}\\ &=x+3x^2+8x^3+21x^4+55x^5+144x^6+\cdots=\sum_{n=1}^\infty F_{2n}x^n \end{align*}

and the claim follows according to OPs expectation.

Commment:

  • In (1) we exchange the summation order.

  • In (2) we shift the index of the inner series by $k$.

  • In (3) we use the binomial identity $\binom{p+q-1}{q}=\binom{-p}{q}(-1)^q$.

  • In (4) we use the binomial series expansion.

  • In (5) we apply the geometric series expansion.

$\endgroup$
2
  • $\begingroup$ Right, that was pretty unfortunate :( $\endgroup$ – Alan Yan Jul 30 '16 at 18:06
  • 1
    $\begingroup$ @AlanYan: The good thing is, you've found a nice relationship and your approach was fine and clever. $\endgroup$ – Markus Scheuer Jul 30 '16 at 18:11
0
$\begingroup$

Suppose we seek the closed form of

$$G_n = \sum_{k=1}^n {n+k-1\choose 2k-1}.$$

Observe that the binomial coefficient

$${n+k-1\choose 2k-1} = {n+k-1\choose n-k}$$

has the property that its integral representation

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-k+1}} (1+z)^{n+k-1} \; dz$$

vanishes when $k\gt n$ and also when $k=0$ ($[z^n] (1+z)^{n-1} = 0$). Therefore we can set the range of the sum from $k=0$ to infinity, getting

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (1+z)^{n-1} \sum_{k\ge 0} z^k (1+z)^k \; dz$$

which converges for $|z(1+z)|<1$ to yield

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (1+z)^{n-1} \frac{1}{1-z(1+z)} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (1+z)^{n+1} \frac{1}{(1+z)^2} \frac{1}{1-z(1+z)} \; dz.$$

Putting $z/(1+z) = w$ we get $z = w/(1-w),$ $1+z=1/(1-w),$ $z(1+z) = w/(1-w)^2,$ and $dz = 1/(1-w)^2 dw$ which yields

$$\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n+1}} (1-w)^2 \frac{1}{1-w/(1-w)^2} \frac{1}{(1-w)^2} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n+1}} \frac{1}{1-w/(1-w)^2} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n+1}} \frac{1-2w+w^2}{1-3w+w^2} \; dw.$$

Recognizing the generating function of $F_{2n}$ which is

$$\frac{w}{1-3w+w^2}$$

we get

$$F_{2n+2} - 2 F_{2n} + F_{2n-2} \\ = F_{2n+1} + F_{2n} - 2 F_{2n} + F_{2n} - F_{2n-1} \\ = F_{2n} + F_{2n-1} + F_{2n} - 2 F_{2n} + F_{2n} - F_{2n-1} = F_{2n}$$

and we are done. The difference in these two generating function is the constant term which produces a value of one in the second generating function.

$\endgroup$

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.