1

I have an interesting problem. I have the sequence $c_i$ which is completely monotone. And in addition, $\sum_{i=0}^{n} c_i=1$. However, we know that $\sum_{i=0}^{n}\binom{n}{i}(-1)^i=0$. Can anybody give me an explicit formula for $\sum_{i=0}^{n}\binom{n}{i}(-1)^ic_i$?

Why do I need an explicit formula? $\binom{n}{i}$ grows fast and overflows memory. It will be excellent if I can have such an explicit formula without having to sum these large numbers.

Somos
  • 35,251
  • 3
  • 30
  • 76
Chamberlain Mbah
  • 167

1 Answers1

0

What you want is the $n$th forward difference of the sequence $c_i$. This can be computed by constructing a difference triangle by iterating the first forward difference. Begin with the sequence of $n+1$ elements $(c_0,c_1,\dots,c_{n-1},c_n)$. Replace each element by the difference of itself and the next from left to right giving $n$ elements $(c_0-c_1,c_1-c_2,\dots,c_{n-1}-c_n)$. This difference operation is performed $n$ times and the final result is a single element $(\sum_{i=0}^{n}\binom{n}{i}(-1)^ic_i)$.

Somos
  • 35,251
  • 3
  • 30
  • 76
  • I know that $\sum_{i=0}^{n}\binom{n}{i}(-1)^ic_i=(-1)^{n}\Delta^{n}c_0$. The problem is when you perform higher order differences you end up with subtracting very small numbers and the precision problem then arises again. – Chamberlain Mbah Aug 19 '17 at 12:48
  • @Chamberlain Fonca You did not mention that problem in your question, but the loss of precision you mention now seems inevitable here no matter how you compute the result. – Somos Aug 19 '17 at 12:55
  • Yes, I did I quote "Why do I need an explicit formula? $\binom{n}{i}$ grows fast and overflows memory." – Chamberlain Mbah Aug 19 '17 at 13:04
  • You know to compute $\sum_{i=1}^{n}\binom{n}{i}(-1)^{i}$ for large $n$, say $n=300$ you will never get zero. But the answer is 0 – Chamberlain Mbah Aug 19 '17 at 13:06