Summation with binomial coefficient

by fungarwai, Jan 12, 2019, 2:04 PM

Summation with one binomial coefficient
$ \sum_{r=0}^n \binom nr = 2^{n} $ from Binomial theorem

$\sum_{r=m}^n (-1)^r \binom Nr =-(-1)^{m-1}\binom{N-1}{m-1}+(-1)^n \binom{N-1}n$

Proof

$\sum_{k=m}^{n} (-1)^k {\binom{N}{k}}^{-1}
=\frac{N+1}{N+2}\left((-1)^m{\binom{N+1}{m}}^{-1}-(-1)^{n+1}{\binom{N+1}{n+1}}^{-1}\right)$

Proof

$\sum_{N=m}^n\binom{N}{k}^{-1}=\frac{k}{k-1}\left(\binom{m-1}{k-1}^{-1}-\binom{n}{k-1}^{-1}\right)$

Proof

$\sum_{r=0}^n (-1)^r \binom{n}{r}\frac{1}{r+s}=\frac{n!(s-1)!}{(n+s)!}$

Proof

$\sum_{r=1}^n (-1)^{r-1}\binom{n}{r}\frac{1}{r}=\sum_{r=1}^n \frac{1}{r}$

Proof

$\sum_{k=0}^\infty (-1)^k \binom{m-k}{k}=\begin{cases}
1 & m\equiv 0\pmod{6}\\
1 & m\equiv 1\pmod{6}\\
0 & m\equiv 2\pmod{6}\\
-1 & m\equiv 3\pmod{6}\\
-1 & m\equiv 4\pmod{6}\\
0 & m\equiv 5\pmod{6}
\end{cases}
=\begin{cases}
(-1)^m & m\equiv 0\pmod{3}\\
-(-1)^m & m\equiv 1\pmod{3}\\
0 & m\equiv 2\pmod{3}\\
\end{cases}$

Proof

$\sum_{k=0}^\infty (-1)^k \frac{1}{m-k}\binom{m-k}{k}
=\begin{cases}
\frac{2}{m} & m\equiv 0\pmod{6}\\
\frac{1}{m} & m\equiv 1\pmod{6}\\
\frac{-1}{m} & m\equiv 2\pmod{6}\\
\frac{-2}{m} & m\equiv 3\pmod{6}\\
\frac{-1}{m} & m\equiv 4\pmod{6}\\
\frac{1}{m} & m\equiv 5\pmod{6}\\
\end{cases}
=\begin{cases}
\frac{2(-1)^m}{m} & m\equiv 0\pmod{3}\\
\frac{-(-1)^m}{m} & m\equiv 1\pmod{3}\\
\frac{-(-1)^m}{m} & m\equiv 2\pmod{3}\\
\end{cases}$

Proof

$\sum_{m=0}^{\lfloor\frac{n}{k}\rfloor}{n\choose km+r}=
\frac{1}{k} \sum_{j=0}^{k-1}  e^{\frac{-2rj\pi i}{k}}(1+e^{\frac{2j\pi i}{k}})^n$

$ F_n=\sum_{i=0}^{\infty} \binom {n-i}{i}$
Proof

$\sum^n_{i=r}{i\choose r}={n+1\choose r+1}$ which is Hockey-stick identity

Other forms

Summation with two binomial coefficient
$\sum_{i=0}^n \binom {r_1+n-1-i}{r_1-1} 
\binom {r_2+i-1}{r_2-1}=\binom {r_1+r_2+n-1}{r_1+r_2-1}$

Proof with Generating function

$\sum_{i=0}^k \binom ni \binom m{k-i}=\binom {n+m}k$ which is Vandermonde's identity

Proof with Generating function

Proof with Hypergeometric function

Example

Summation with three binomial coefficient

${\binom {n+k}k}^2=\sum_{j=0}^k {\binom kj}^2 \binom {n+2k-j}{2k}$ which is the Li Shanlan identity

Proof with Hypergeometric function

Summation with multiple binomial coefficient

$\sum_{k_{ij}} {n_1 \choose k_{11}, k_{12}, \dots, k_{1t}}
\dots {n_s \choose k_{s1}, k_{s2}, \dots, k_{st}}
={n_1+n_2+\dots+n_s \choose r_1, r_2, \dots, r_t}$

where ${n \choose n_1, n_2, \dots, n_m}
=\frac{n!}{n_1!n_2!\dots n_m!},k_{1l}+k_{2l}+\dots+k_{sl}
=r_l,l=1,\dots,t$

It is the Generalized Vandermonde's identity

Proof

$\sum_{n_i\ge m_i\atop n_1+n_2+\dots+n_k =n}
\binom{n_1}{m_1}\binom{n_2}{m_2}\dots\binom{n_k}{m_k}=
\binom{n+k-1}{\sum m_i+k-1}$

Named as Vandermonde type convolution formula in
Combinatorial identities associated with new families of the numbers and polynomials and their approximation values
(Theorem 5.4 of Section 5)

The probability of the sum of negative binomial random variables also implies that

$\sum_{n_1+n_2+\cdots+n_k=n} \binom{n_1+m_1-1}{n_1}\binom{n_2+m_2-1}{n_2}\cdots 
\binom{n_k+m_k-1}{n_k}=\binom{n+m-1}{n}$

Reference: Negative binomial distribution - sum of two random variables


Proof by recalculating number of integer solution of a linear equation

Proof by generating functions of negative binomial series

Proof by sum of negative binomial random variables

It can be further generalised as:

$\displaystyle \sum_{\sum c_in_i=n} \binom{n_1}{m_1}\binom{n_2}{m_2}\cdots 
\binom{n_k}{m_k}=[x^{n-\sum c_im_i}]\prod_{i=1}^k\frac{1}{(1-x^{c_i})^{m_i+1}}$

Proof by generating functions of negative binomial series

Example
This post has been edited 24 times. Last edited by fungarwai, Today at 12:54 AM

Comment

1 Comment

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Simply amazing!

by cardesigner06, Apr 30, 2019, 6:41 PM

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: 5835
  • Total comments: 8
Search Blog
a