2
$\begingroup$

I have a sum of the form $$ G_n(\mathbf{x})=\sum_{k=0}^n(-1)^k\binom{n+k}{k}\binom{n}{k}g_k(\mathbf{x}) $$ where $\mathbf{x}=(x_1,x_2...)$ is a vector of any number of (complex) parameters, and $g_k$ is some expression involving $x_1,x_2...$.

What techniques are there for computing this type of sum with numerical stability? The problem is that for large $n$, numerical errors occur due to subtracting large numbers to obtain a relatively small result (the binomial coefficients grow very quickly). Is there a method to find some type of recurrence?

In my specific case I have $\mathbf{x}=(x,y,z)$ and $$g_k=\frac{k(2k+1)^2}{(kx+1)(ky+1)z^{2k+1}+k(k+1)(x-2)(y-2)}\frac{1}{kx+1}$$ with $0<z<1$, and the sum $G_n$ has huge numerical errors for $n>\approx 20$. I have tried expressing the binomial coefficients be expressed as sums themselves and rearranging the order of summation, without success. I do not think that there is anything specific about this $g_k$ that would simplify computations, hence the question about a general $g_k$.

$\endgroup$
  • 1
    $\begingroup$ The usual first thing to try is to analytically combine each term for even $k$ with the following term, so that the cancellation effect is determined exactly. In your case also write the binomial coefficients for $k+1$ in terms of those for $k$. A very messy expression is obtained, but it's worth a try. $\endgroup$ – Brendan McKay Apr 10 '17 at 2:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.