Fundamental theorem of the calculus of finite differences

Remarks

The proof is a telescoping sum: $\sum_{k=a}^{b-1} (F(k+1) - F(k))$ cancels to $F(b) - F(a)$, as in a telescoping series. For $a = b$ both sides are $0$. Example: $\Delta (k)_3 = 3 (k)_2$ for the falling factorial $(k)_3 = k(k-1)(k-2)$, so $\sum_{k=0}^{n-1} k(k-1) = \frac{n(n-1)(n-2)}{3}$. A related identity, with $\Delta$ of step $h$ on any additive commutative monoid, is $\sum_{k=0}^{n-1} f(x + kh) = \sum_{j=0}^{n-1} \binom{n}{j+1} \Delta_h^j f(x)$, obtained by summing Newton's forward difference formula.

Going deeper

For a student

The theorem reduces the evaluation of finite sums to finding indefinite sums, just as the fundamental theorem of calculus reduces integrals to antiderivatives. A table of differences, such as $\Delta (k)_m = m (k)_{m-1}$ for falling factorials and $\Delta c^k = (c - 1) c^k$, becomes a table of sums. To sum $k^2$, write $k^2 = (k)_2 + (k)_1$, which gives $\sum_{k=0}^{n-1} k^2 = \frac{(n)_3}{3} + \frac{(n)_2}{2}$. Summation by parts is the discrete analogue of integration by parts and is proved from the same telescoping.