1

I came across a sum: $$p_k(x, n) = \sum_{i=0}^{k-1} {n + i - 1 \choose i} x^i$$

and I was wondering if it had a closed form. I found on wikipedia:

$$\sum_{i=0}^{\infty} {n + i - 1 \choose i} x^i = (1 - x)^{-n} \text{ for } |x| < 1$$

but it had neither a derivation I could try to amend nor a partial sum expression.

I tried using partial derivatives wrt $x$ to transform it into a differential equation but couldn't work anything out. A good approximation for large $k$ would also be helpful.

DanielV
  • 23,556
  • By multiplying both sides by $(1-x)^n$, it is not difficult to see that $p_k(x,n)$ depends on a hypergeometric function: $$p_k(x,n)=\frac{1}{(1-x)^n}-x^k\binom{n+k-1}{k}\phantom{}_2 F_1\left(1,k+n;1+k;x\right).$$ – Jack D'Aurizio Jan 11 '15 at 17:22
  • @JackD'Aurizio Thanks I'll look into that. – DanielV Jan 11 '15 at 18:20

1 Answers1

1

It has been said many times on this site that there is no closed form expression for partial sums of binomial terms. In this case, the binomial series in question is $\big(1-x\big)^{-n}$, for whose partial sum no closed form expression exists, for the same reason that no such expression exists for the partial sum of $(1-x)^n$ either. Not unless you are willing to consider hypergeometric functions as such.

Lucian
  • 48,334
  • 2
  • 83
  • 154
  • Thanks, I guess I'll be learning about hypergeometric functions. For me, I think of "closed form" in terms of computing speed, so reducing it from O(k) to O(log k) , regardless of intermediary functions, is sufficient. – DanielV Jan 11 '15 at 18:22