Summation with polynomial

by fungarwai, Sep 15, 2018, 9:23 AM

Main Applications of Finite Difference

The following Chapters would introduce the method of Finite Difference to solve some typical types of summation with polynomial,
including summation of Arithmetic sequence, Geometric sequence and Arithmetico-Geometric sequence.

For Arithmetic sequence $a_n=a+(n-1)d,$
$\displaystyle S_n=\sum_{k=1}^n a_k=\sum_{k=1}^n a+(k-1)d \left(=an+\frac{(n-1)n}{2}d=a\binom{n}{1}+d\binom{n}{2} \text{(to be concerned})\right)$
Without any introduction of Finite Difference, this sum can just apply Hockey stick identity by:
$\displaystyle \sum_{k=1}^n a+(k-1)d=\sum_{k=1}^n a\binom{k-1}{0}+d\binom{k-1}{1}=a\binom{n}{1}+d\binom{n}{2}$
The problem is whether we can use a general method to rewrite a polynomial to a linear combination of binomial coefficients.

Deem Arithmetic sequence as a polynomial, let $p(k)=a+(k-1)d,$
with $\Delta p(k)=d$ and Newton's series in Chapter 1,
We can get $p(k)=\sum_{m=0}^{deg(p)} \binom{k-a}{m}\Delta^m p(a) =\sum_{m=0}^{1} \binom{k-1}{m}\Delta^m p(1)$
$=\binom{k-1}{0}p(1)+\binom{k-1}{1}\Delta p(1)=a\binom{k-1}{0}+d\binom{k-1}{1}$
Hence Arithmetic sequence is rewritten as a linear combination of binomial coefficients.

Summation of Geometric sequence and Arithmetico-Geometric sequence can be generalized in the later Chapter 3.

Chapter 0 Basic properties of finite difference

Chapter 1 Newton's series

Chapter 2 Summation with polynomial only

$\sum_{k=n_0}^n p(k)=\sum_{m=0}^{\deg(p)} \binom{n+1-n_0}{m+1}\Delta^m p(n_0)$
$\quad\sum_{k=0}^n p(k)=\sum_{m=0}^{\deg(p)} \binom{n+1}{m+1}\Delta^m p(0)$
$\quad\sum_{k=1}^n p(k)=\sum_{m=0}^{\deg(p)} \binom{n}{m+1}\Delta^m p(1)$

Proof

Example

$\sum_{k=1}^n k^m =\sum_{k=1}^m k!\left\{m\atop k\right\}\binom{n+1}{k+1}$

Proof

$\sum_{k=1}^n k^a (n+1-k)^b=\sum_{i=1}^a \sum_{j=1}^b i!j!\left\{a\atop i\right\}\left\{b\atop j\right\}\binom{n+2}{i+j+1}$

Proof

Chapter 3 Summation with factorial

$\sum_{k=n_0}^n p(k)(k-a)!=\sum_{k=n_0}^n \sum_{m=0}^{\deg(p)}\left(\frac{1}{m!}\Delta^m p(a-1-m)\right)(k-a+m)!$
This kind of sum may result in telescoping sum for some polynomial, but some times may not.
For example, $\sum_{k=1}^n k!$ cannot be determined when $p(k)=1$ .

Proof

Example

Chapter 4 Summation with geometric sequence

$\sum_{k=n_0}^n p(k)q^{k-n_0}=f(n)q^{n+1-n_0}-f(n_0-1)$

$\quad\sum_{k=0}^n p(k)q^k=f(n)q^{n+1}-f(-1)$

$\quad\sum_{k=1}^n p(k)q^{k-1}=f(n)q^n-f(0)$

where $f(n)=\frac{p(n)}{q-1}+\frac{1}{(q-1)^2}\sum_{k=1}^{deg(p)} \frac{(-1)^kq^{k-1}}{(q-1)^{k-1}}\Delta^k(p(n)) =\frac{1}{q-1}\sum_{k=0}^{deg(p)} (\frac{-q}{q-1})^k\Delta^k p(n+1)$

Proof

Example

Chapter 5 Summation with geometric sequence and factorial

Chapter 6 Summation with Harmonic number

Reference book:
Schaum's outline of calculus of finite differences and difference equations
Reference sources:
Finite Calculus: A Tutorial for Solving Nasty Sums
Finite Calculus, Stirling Numbers, and Cleverly Changing Basis
Sums of Powers of Integers
The Calculus of Finite Differences

This post has been edited 33 times. Last edited by fungarwai, Dec 24, 2024, 4:21 AM

polynomial

Summation

Finite difference

Comment

5 Comments