1
$\begingroup$

Let $D,n\in \mathbb N$ with $0<D<n$, and $y>0$ is a real number.

Question: Is there a closed-form for the following alternating sequence \begin{equation} \sum_{k=0}^D (-y)^k {n\choose k}? \end{equation}

This question is related to a similar question where $y=1$.

Motivation: These kind of expressions arrive in numerical schemes that I am working on.

First attempt: I tried to repeat some of the techniques from $y=1$ case. For instance, using the complex integral argument, we have \begin{align} \sum_{k=0}^D (-y)^k {n\choose k} &= \sum_{k=0}^D (-y)^k \oint_{0<|z|<1} \frac{(1+z)^n}{z^{k+1}}\frac{dz}{2\pi i} = \oint_{0<|z|<1} \frac{(1+z)^n}{z} \sum_{k=0}^D \left(-\frac{y}{z}\right)^k \frac{dz}{2\pi i} \\ &= \oint_{0<|z|<1} \frac{(1+z)^n}{z} \left[\frac{z+y(-y/z)^D}{z+y}\right] \frac{dz}{2\pi i} \\ &= \oint_{0<|z|<1} \frac{(1+z)^n}{z+y} \frac{dz}{2\pi i} + y(-y)^D \oint_{0<|z|<1} \frac{(1+z)^n}{z^{D+1}(z+y)} \frac{dz}{2\pi i}. \end{align} I don't know much about complex integrals and so don't know how to complete this argument. Any ideas?

Or are their any other techniques that will work here? Any ideas/hints are appreciated.

$\endgroup$
  • $\begingroup$ There should be $|z|=1$ below the integral everywhere. And $\int_{|z|=1}f(z)\,dz = \int_0^{2\pi}f(e^{it})ie^{it}\,dt$. $\endgroup$ – amsmath Apr 17 at 12:19
  • $\begingroup$ @amsmath I don't understand. Is there a mistake in my question that you are referring to or is something else? Could you please elaborate. $\endgroup$ – UPS Apr 17 at 12:21
  • $\begingroup$ I just gave you the definition of a complex line integral. $\endgroup$ – amsmath Apr 17 at 12:23
  • $\begingroup$ BTW: Instead of the circle you can use a square. That might make integration easier. $\endgroup$ – amsmath Apr 17 at 12:28
  • $\begingroup$ Note that you want to evaluate a special polynomial of degree $D$ at $-y$. So, it might be advantageous to find the zeros of that polynomial (in case that's possible -- I guess not). Otherwise you can use Horner's scheme of course. $\endgroup$ – amsmath Apr 17 at 12:38
2
$\begingroup$

We show the difference between the variant with general $y$ and $y=1$. We use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ in a series. This way we can write for instance \begin{align*} [z^k](1+z)^n=\binom{n}{k}=\oint_{0<|z|<1} \frac{(1+z)^n}{z^{k+1}}\frac{dz}{2\pi i} \tag{1} \end{align*}

We obtain \begin{align*} \color{blue}{\sum_{k=0}^D(-y)^k\binom{n}{k}} &=\sum_{k=0}^D[z^k](1-yz)^n\tag{2}\\ &=[z^0](1-yz)^n\sum_{k=0}^Dz^{-k}\tag{3}\\ &=[z^0](1-yz)^n\frac{z^{-(D+1)}-1}{z^{-1}-1}\\ &=[z^{-1}](1-yz)^n\frac{z^{-(D+1)}-1}{1-z}\\ &=\left([z^D]-[z^{-1}]\right)\frac{(1-yz)^n}{1-z}\tag{4}\\ &\,\,\color{blue}{=[z^D]\frac{(1-yz)^n}{1-z}}\tag{5} \end{align*}

We see in (5) that in case $y=1$ we get \begin{align*} [z^D]\left.\frac{(1-yz)^n}{1-z}\right|_{y=1}=[z^D](1-z)^{n-1}=(-1)^D\binom{n-1}{D} \end{align*} but there is no way to make similar simplifications with general $y$.

Comment:

  • In (2) we apply the coefficient of operator according to (1).

  • In (3) we use the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.

  • In (4) we note $\frac{(1-yz)^n}{1-z}=(1-yz)^n\sum_{j=0}^\infty z^j$ is a power series in $z$ so that the residue $[z^{-1}]$ is zero.

$\endgroup$
  • $\begingroup$ Thank you for this nice answer. How do you get (4), or rather why exactly is $z^{-1}\frac{(1-yz)^n}{1-z}=0$? $\endgroup$ – UPS Apr 17 at 16:27
  • $\begingroup$ @UPS: You're welcome. I've added a corresponding comment. $\endgroup$ – Markus Scheuer Apr 17 at 16:34
1
$\begingroup$

You could write it using a hypergeometric function:

$$ \left( 1-y \right) ^{n}-{n\choose D+1} \left( -y \right) ^{D+1} {\mbox{$_2$F$_1$}(1,-n+D+1;\,D+2;\,y)} $$

$\endgroup$
  • $\begingroup$ Do you think this is better in numerical terms? $\endgroup$ – amsmath Apr 17 at 12:32
  • $\begingroup$ Not particularly, though it might depend on how good your library's hypergeometric function evaluator is. $\endgroup$ – Robert Israel Apr 17 at 12:35
  • $\begingroup$ Also might be useful if $D$ is close to $n$, especially if $y$ is small. $\endgroup$ – Robert Israel Apr 17 at 12:45
  • $\begingroup$ @RobertIsrael Thank you for this closed form. So in my schemes, $D$ is much smaller than $n$, and $y\geq 1$. As mentioned in the comments above, this expression increases as a function of $n$ and then decreases. For $y=1$ this critical value is $n/2$. Is there a good way to differentiate this hypergeometric expression to arrive at the critical value (even numerically)? Sorry for repeating earlier comment. By the way, should I edit my question to explain this motivation? $\endgroup$ – UPS Apr 17 at 12:49
  • $\begingroup$ Correction -- I mean it increases as a function of $k$, and then decreases ($n,y$ are fixed). $\endgroup$ – UPS Apr 17 at 12:57

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.