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 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 4 Summation with geometric sequence and factorial

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
This post has been edited 31 times. Last edited by fungarwai, Aug 1, 2024, 12:54 PM

Comment

5 Comments

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Thank you so much ! I learned something new today and very interesting algebraic setup

by Alphatrion, May 18, 2020, 1:35 PM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Can you explain what $\Delta p(x)$ is it?

by Wildabandon, Jan 26, 2021, 3:01 AM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Ignore it. Missread ._.

by Wildabandon, Jan 26, 2021, 3:02 AM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Thanks for this.

by jasperE3, May 14, 2021, 5:51 PM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
This is the first and most important post in my algebra blog.
I was surprised that Finite Difference has become an excellent tool for power sum.
I hope that everyone would have the chance to learn this earlier.
I think Finite Difference should be something we should study before differentiation.
I would like to pay most of the effort to promote this operator.

by fungarwai, Aug 28, 2021, 5:07 AM

Notable algebra methods with proofs and examples

avatar

fungarwai
Shouts
Submit
  • Nice blog!

    by Inconsistent, Mar 18, 2024, 2:41 PM

  • hey, nice blog! really enjoyed the content here and thank you for this contribution to aops. Sure to subscribe! :)

    by thedodecagon, Jan 22, 2022, 1:33 AM

  • thanks for this

    by jasperE3, Dec 3, 2021, 10:01 PM

  • I am working as accountant and studying as ACCA student now.
    I graduated applied mathematics at bachelor degree in Jinan University but I still have no idea to find a specific job with this..

    by fungarwai, Aug 28, 2021, 4:54 AM

  • Awesome algebra blog :)

    by Euler1728, Mar 22, 2021, 5:37 AM

  • I wonder if accountants need that kind of math tho

    by Hamroldt, Jan 14, 2021, 10:55 AM

  • Nice!!!!

    by Delta0001, Dec 12, 2020, 10:20 AM

  • this is very interesting i really appericate it :)

    by vsamc, Oct 29, 2020, 4:42 PM

  • this is god level

    by Hamroldt, Sep 4, 2020, 7:48 AM

  • Super Blog! You are Pr0! :)

    by Functional_equation, Aug 23, 2020, 7:43 AM

  • Great blog!

    by freeman66, May 31, 2020, 5:40 AM

  • cool thx! :D

    by erincutin, May 18, 2020, 4:55 PM

  • How so op???

    by Williamgolly, Apr 30, 2020, 2:42 PM

  • Beautiful

    by Al3jandro0000, Apr 25, 2020, 3:11 AM

  • Nice method :)

    by Feridimo, Jan 23, 2020, 5:05 PM

  • This is nice!

    by mufree, May 26, 2019, 6:40 AM

  • Wow! So much Algebra.

    by AnArtist, Mar 15, 2019, 1:19 PM

  • :omighty: :omighty:

    by AlastorMoody, Feb 9, 2019, 5:17 PM

  • 31415926535897932384626433832795

    by lkarhat, Dec 25, 2018, 11:53 PM

  • rip 0 shouts and 0 comments until now

    by harry1234, Nov 17, 2018, 8:56 PM

20 shouts
Tags
About Owner
  • Posts: 859
  • Joined: Mar 11, 2017
Blog Stats
  • Blog created: Sep 15, 2018
  • Total entries: 18
  • Total visits: 5839
  • Total comments: 8
Search Blog
a