1

I was trying to evaluate: $$\sum_{k=0}^{n} \frac{\binom{n}{k}}{\binom {2n-1}{k}}x^k$$ And in particular, when $x=1$.

I already have $2$ proofs for the $x=1$ case, (it is $2$) by counting subsets of a $2n-1$ size set and by splitting the term into a telescoping sum. I was looking for a solution using only generating functions.

mtheorylord
  • 4,274
  • What you have is a generating function. Do you mean that you want to find a closed form (i.e. without summation) for the expression in question? Mathematica gives something in terms of hypergeometric functions, for what it's worth. – Math1000 Nov 07 '19 at 02:44

2 Answers2

1

We have that $$ {{\left( \matrix{ n \cr k \cr} \right)} \over {\left( \matrix{ 2n - 1 \cr k \cr} \right)}} = {{n^{\,\underline {\,k\,} } } \over {\left( {2n - 1} \right)^{\,\underline {\,k\,} } }} = {{\left( { - 1} \right)^{\,k} \left( { - n} \right)^{\,\overline {\,k} } } \over {\left( { - 1} \right)^{\,k} \left( { - 2n + 1} \right)^{\,\overline {\,k} } }} = {{\left( { - n} \right)^{\,\overline {\,k} } } \over {\left( { - 2n + 1} \right)^{\,\overline {\,k} } }} $$ where $x^{\,\underline {\,k\,} } ,\quad x^{\,\overline {\,k\,} } $ represent respectively the Falling and Rising Factorial.

Therefore $$ S(x,n)=\sum\limits_{0\, \le \,k\,\left( { \le \,n} \right)} {{{\left( \matrix{ n \cr k \cr} \right)} \over {\left( \matrix{ 2n - 1 \cr k \cr} \right)}}x^{\,k} } = \sum\limits_{0\, \le \,k\,\left( { \le \,n} \right)} {{{1^{\,\overline {\,k} } \left( { - n} \right)^{\,\overline {\,k} } } \over {\left( { - 2n + 1} \right)^{\,\overline {\,k} } }}{{x^{\,k} } \over {k!}}} = {}_{2}F_{\,1} \left( {\left. {\matrix{ {1,\,\, - n} \cr { - 2n + 1} \cr } \,} \right|\;x} \right) $$ But the Hypergeometric with the parameters shown is not easy to handle.

Instead of working in finding equivalent forms for the hypergeometric, we change the approach and rewrite the starting sum as $$ \eqalign{ & S(x,n) = \sum\limits_{0\, \le \,k\, \le \,n} {{{\left( \matrix{ n \cr k \cr} \right)} \over {\left( \matrix{ 2n - 1 \cr k \cr} \right)}}x^{\,k} } \quad \left| {\;1 \le n} \right.\quad = \cr & = \sum\limits_{0\, \le \,k\, \le \,n} {{{\left( \matrix{ n \cr n - k \cr} \right)} \over {\left( \matrix{ 2n - 1 \cr n - 1 + n - k \cr} \right)}} x^{\,n - \left( {n - k} \right)} } = x^{\,n} \sum\limits_{0\, \le \,k\, \le \,n} {{{\left( \matrix{ n \cr k \cr} \right)} \over {\left( \matrix{ 2n - 1 \cr n - 1 + k \cr} \right)}}x^{ - \,k} } \cr & = x^{\,n} \sum\limits_{0\, \le \,k\, \le \,n} {{{n^{\,\underline {\,k\,} } \left( {n - 1 + k} \right)!} \over {k!\left( {2n - 1} \right)^{\,\underline {\,n - 1 + k\,} } }}x^{ - \,k} } = x^{\,n} \sum\limits_{0\, \le \,k\, \le \,n} {{{n^{\,\underline {\,k\,} } \left( {n - 1 + k} \right)!} \over {k!\left( {2n - 1} \right)^{\,\underline {\,n - 1\,} } n^{\,\underline {\,k\,} } }}x^{ - \,k} } = \cr & = {{x^{\,n} } \over {\left( {2n - 1} \right)^{\,\underline {\,n - 1\,} } }}\sum\limits_{0\, \le \,k\, \le \,n} {{{\left( {n - 1 + k} \right)!} \over {k!}}x^{ - \,k} } = {{\left( {n - 1} \right)!x^{\,n} } \over {\left( {2n - 1} \right)^{\,\underline {\,n - 1\,} } }} \sum\limits_{0\, \le \,k\, \le \,n} {\left( \matrix{ n - 1 + k \cr k \cr} \right)x^{ - \,k} } = \cr & = {{x^{\,n} } \over {\left( \matrix{ 2n - 1 \cr n - 1 \cr} \right)}} \sum\limits_{0\, \le \,k\, \le \,n} {\left( \matrix{ n - 1 + k \cr k \cr} \right)x^{ - \,k} } \cr} $$

So $$ \eqalign{ & S(1,n) = {1 \over {\left( \matrix{ 2n - 1 \cr n - 1 \cr} \right)}}\sum\limits_{0\, \le \,k\, \le \,n} {\left( \matrix{ n - 1 + k \cr k \cr} \right)} = \cr & = {1 \over {\left( \matrix{ 2n - 1 \cr n - 1 \cr} \right)}} \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( \matrix{ n - k \cr n - k \cr} \right)\left( \matrix{ n - 1 + k \cr k \cr} \right)} = \cr & = {{\left( \matrix{ 2n \cr n \cr} \right)} \over {\left( \matrix{ 2n - 1 \cr n \cr} \right)}} = {{\left( {2n} \right)!n!\left( {n - 1} \right)!} \over {n!n!\left( {2n - 1} \right)!}} = 2 \cr} $$

G Cab
  • 35,272
0

(I started an answer some hours ago, but had to stop, well, it is time to finish and submit.) Let $y=1/x$, (if $x$ is not zero,) and let us compute closer for some integer $n>0$ $$ \begin{aligned} \frac{\binom nk}{\binom {2n-1}k} &=\frac{n!}{k!(n-k)!}\cdot\frac{k!(2n-k-1)!}{(2n-1)!} \\ &=\frac{n!(n-1)!}{(2n-1)!}\cdot\frac{(2n-k-1)!}{(n-k)!(n-1)!} \\ &=\binom{2n-1}{n}^{-1}\cdot\binom{2n-k-1}{n-1}\ . \\ %[3mm] &\qquad\text{ This implies for the sum to be calculated:} \\ f(x) &:= \sum_{0\le k\le n} \frac{\binom nk}{\binom {2n-1}{k}}x^k = \binom{2n-1}{n}^{-1} \sum_{0\le k\le n} \binom{2n-k-1}{n-1} x^k \\ &= x^n \binom{2n-1}{n}^{-1} \sum_{0\le k\le n} \binom{n-1+(n-k)}{n-1} y^{n-k}\qquad\text{ (Recall $y=1/x$)} \\ &\qquad\text{ and let us use in the summation the variable $j=n-k$} \\ &= x^n \binom{2n-1}{n}^{-1} \sum_{n\ge j\ge 0} \binom{n-1+j}{n-1} y^j\ . \end{aligned} $$ Now it is time to set $x=y=1$, and recall the formula: $$ \binom KK + \binom {K+1}K + \binom {K+2}K + \dots + \binom NK = \binom{N+1}{K+1}\ .\qquad(*) $$ This gives $$ f(1) = \binom{2n-1}{n}^{-1} \sum_{n\ge j\ge 0} \binom{n-1+j}{n-1} = \binom{2n-1}{n}^{-1} \binom{(2n-1)+1}{(n-1)+1} = \binom{2n-1}{n}^{-1} \binom{2n}{n} =2\ . $$ (Because of $\binom{2n}n=\frac{2n}n\binom{2n-1}{n-1}=2\binom{2n-1}{n}$.)

For a more general formula of $f(x)$ containing the variable $x$, we would need a corresponding relation $(*)$ containing $x$.

dan_fulea
  • 32,856