Geometric sum with binomial coefficient

138 Views Asked by At

I'm looking for any kind of formula or insight concerning

$$ f(k,N)=\sum_{n=0}^N\binom{n}{k}\lambda^n $$

There are loads of binomial identities, so maybe I was just missing something, but I couldn't find anything yet.


Addendum: Further assumptions on $\lambda$, i.e. $\lambda=\exp(2\pi i\alpha)$ yield to the following problem: Gaussian like sum with binomial coefficients

2

There are 2 best solutions below

1
On

To get a sum of about $k$ terms (opposed to $N$ originally), use $$\sum_{n=0}^N\binom{n}{k}\lambda^n=\frac{\lambda^k}{k!}\frac{d^k}{d\lambda^k}\sum_{n=0}^N\lambda^n=\frac{\lambda^k}{k!}\frac{d^k}{d\lambda^k}\frac{1-\lambda^{N+1}}{1-\lambda}$$ and apply Leibniz rule. This can also be viewed as a closed-form answer for a fixed $k$.

2
On

Allow me to change your notation to $$ f(x,m,n) = \sum\limits_{k = 0}^n {\binom{k}{m}x^{\,k} } $$

Then a first approach would be through a double o.g.f. as $$ \eqalign{ & \sum\limits_{0\, \le \,n} {f(x,m,n)y^n } = \sum\limits_{0\, \le \,n} {\sum\limits_{0\, \le \,k\, \le \,n} {\left( \matrix{ k \cr m \cr} \right)x^{\,k} y^n } } = \cr & = \sum\limits_{0\, \le \,k} {\sum\limits_{\,k\, \le \,n} {\left( \matrix{ k \cr m \cr} \right)\left( {xy} \right)^{\,k} y^{n - k} } } = \sum\limits_{0\, \le \,k} {\sum\limits_{\,0\, \le \,j} {\left( \matrix{ k \cr m \cr} \right)\left( {xy} \right)^{\,k} y^j } } = \cr & = {1 \over {1 - y}}\sum\limits_{0\, \le \,k} {\left( \matrix{ k \cr k - m \cr} \right)\left( {xy} \right)^{\,k} } = {{\left( {xy} \right)^{\,m} } \over {1 - y}}\sum\limits_{0\, \le \,k - m} {\left( { - 1} \right)^{\,k - m} \left( \matrix{ - m - 1 \cr k - m \cr} \right) \left( {xy} \right)^{\,k - m} } = \cr & = {{\left( {xy} \right)^{\,m} } \over {\left( {1 - y} \right)\left( {1 - xy} \right)^{\,m + 1} }} \cr} $$

An other way is first to express the sum as an infinite sum with the index starting from $0$, as $$ \eqalign{ & f(x,m,n) = \sum\limits_{k = 0}^n {\left( \matrix{ k \cr m \cr} \right)x^{\,k} } = \cr & = \sum\limits_{0\, \le \,k} {\left( \matrix{ n - k \cr n - k \cr} \right) \left( \matrix{ k \cr k - m \cr} \right)x^{\,k} } = \cr & = \sum\limits_{0\, \le \,j} {\left( \matrix{ j \cr j \cr} \right)\left( \matrix{ n - j \cr n - m - j \cr} \right)x^{\,n - j} } = \cr & = x^{\,n} \sum\limits_{0\, \le \,j} {{{\left( {n - j} \right)^{\,\underline {\,n - m - j\,} } } \over {\left( {n - m - j} \right)!}}\left( {1/x} \right)^{\,j} } \cr} $$ where $x^{\,\underline {\,k\,} }$ represents the Falling Factorial

Then we can convert it into a Hypergeometric function by putting $$ t_{\,j} = {{\left( {n - j} \right)^{\,\underline {\,n - m - j\,} } } \over {\left( {n - m - j} \right)!}} $$ and determine that $$ t_{\,0} = {{\left( n \right)^{\,\underline {\,n - m\,} } } \over {\left( {n - m} \right)!}} = \left( \matrix{ n \cr m \cr} \right) $$ as well that the ratio is $$ \eqalign{ & {{t_{\,j + 1} } \over {t_{\,j} }} = {{\left( {n - 1 - j} \right)^{\,\underline {\,n - 1 - m - j\,} } } \over {\left( {n - 1 - m - j} \right)!}}{{\left( {n - m - j} \right)!} \over {\left( {n - j} \right)^{\,\underline {\,n - m - j\,} } }} = \cr & = {{\left( {n - 1 - j} \right)^{\,\underline {\,n - 1 - m - j\,} } } \over {\left( {n - j} \right)^{\,\underline {\,1\,} } \left( {n - 1 - j} \right)^{\,\underline {\,n - 1 - m - j\,} } }}{{\left( {n - m - j} \right)} \over 1} = \cr & = {{n - m - j} \over {n - j}} = {{j - n + m} \over {j - n}} \cr} $$

Therefore $$ f(x,m,n) = x^{\,n} \left( \matrix{ n \cr m \cr} \right){} _2F_{\,1} \left( {\left. {\matrix{ { - n + m,\;1} \cr { - n} \cr } \;} \right|\;{1 \over x}} \right) $$

Still another way to express $f(x,m,n)$ is $$ \eqalign{ & f(x,m,n) = \sum\limits_{k = 0}^n {\left( \matrix{ k \cr m \cr} \right)x^{\,k} } = \cr & = \sum\limits_{k = 0}^n {{{k^{\,\underline {\,m\,} } } \over {m!}}x^{\,k} } = {{x^{\,m} } \over {m!}}\sum\limits_{k = 0}^n {k^{\,\underline {\,m\,} } x^{\,k - m} } = \cr & = {{x^{\,m} } \over {m!}}\sum\limits_{k = 0}^n {{{d^{\,m} } \over {dx^{\,m} }}x^{\,k} } = {{x^{\,m} } \over {m!}}{{d^{\,m} } \over {dx^{\,m} }} \left( {{{1 - x^{\,n + 1} } \over {1 - x}}} \right) \cr} $$