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
Without any introduction of Finite Difference, this sum can just apply Hockey stick identity by:
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
with and Newton's series in Chapter 1,
We can get
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
Proof
Example
Proof
Proof
Chapter 3 Summation with geometric sequence
where
Proof
Example
When ,
Chapter 4 Summation with geometric sequence and factorial
Proof
This is related to a significant formula from Schaum's Outline of Calculus of Finite Differences and Difference Equations
Example
Chapter 5 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
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
Without any introduction of Finite Difference, this sum can just apply Hockey stick identity by:
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
with and Newton's series in Chapter 1,
We can get
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
You may watch the video course on Youtube (Cantonese version here) or (English version here)
You may try my test provided in ClassMarker for this Chapter here
Definition
Define which is called Finite difference
Linear operator
is a linear operator such that
n th power of finite difference
General results of high power finite difference
Define the degree of polynomial as , for the polynomial with leadiing coefficient 1 :
You may try my test provided in ClassMarker for this Chapter here
Definition
Define which is called Finite difference
Linear operator
is a linear operator such that
n th power of finite difference
General results of high power finite difference
Define the degree of polynomial as , for the polynomial with leadiing coefficient 1 :
Chapter 1 Newton's series
Every polynomial can be represented by each degree of its finite difference
which is known as Newton's series
Proof
Example
which is known as Newton's series
Proof
Let
Example
Chapter 2 Summation with polynomial only
Proof
which is called Hockey-stick identity
Example
Proof
Let where , and let
and .
Show by counting in two different ways that
Source: Principles and Techniques in Combinatorics by Chen Chuan - Chong
https://artofproblemsolving.com/community/c4h2519973_an_interesting_problem_revolving_around_sets_and_combinatorics
https://artofproblemsolving.com/community/c4h2081321p14972116
Considering
can be chosen from
can be separated to
which have elements respectively
So now we have
Considering all cases of
refer to Stirling numbers of the second kind
There are different sets
which contains elements respectively
The general result should be
which is equivalent to the result of the formula in this chapter.
and .
Show by counting in two different ways that
Source: Principles and Techniques in Combinatorics by Chen Chuan - Chong
https://artofproblemsolving.com/community/c4h2519973_an_interesting_problem_revolving_around_sets_and_combinatorics
https://artofproblemsolving.com/community/c4h2081321p14972116
Considering
can be chosen from
can be separated to
which have elements respectively
So now we have
Considering all cases of
refer to Stirling numbers of the second kind
There are different sets
which contains elements respectively
The general result should be
which is equivalent to the result of the formula in this chapter.
Proof
Chapter 3 Summation with geometric sequence
where
Proof
Example
When ,
Chapter 4 Summation with geometric sequence and factorial
Proof
This is related to a significant formula from Schaum's Outline of Calculus of Finite Differences and Difference Equations
Example
Chapter 5 Summation with Harmonic number
Define as Harmonic number
Proof
Example
Proof
Example
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 31 times. Last edited by fungarwai, Aug 1, 2024, 12:54 PM
by Alphatrion, May 18, 2020, 1:35 PM