Category 1:  Sums

 
                                                            Category 2:  Products

                                                            Category 3:  Sums of Products

                                                            Category 4:  Products of Sums

                                                            Category 5:  Identities (mod n) and factors

                                                        Category 1: Identities involving sums

1.0: B.C. = B.C.

Catalog #: 1000001

                             
Known as: The Symmetry Rule, Pascal’s 4^th Identity
Proof
One of the Top Ten Identities

Return to top

1.1:  B.C.s = B.C. and B.C.s = B.C.s

Catalog #: 1100001

                         
Known as:  The Basic Additive Identity, Pascal’s 1^st Identity
Proof
One of the Top Ten Identities

Catalog #: 1100002

                         
Known as: Upper Summation and Parallel Summation (respectively), The Christmas Stocking Theorem, Pascal’s 2^nd  Identity
Sometimes incorrectly called The Hockey Stick Theorem (see Cat. # 3400001)
Proof
One of the Top Ten Identities

Catalog #: 1100003

                     
Known as: Pascal’s 3^rd Identity
Hint: Multiple uses of the Christmas Stocking Theorem

Catalog #: 1100004

                         
Known as: Sums of Rows Doubling,  1^st part, Pascal’s 5^th Identity
Proof

Catalog #: 1100005

               
Known as: Partial Row Sum Rule, Pascal’s 6^th Identity

Catalog #: 1100006

                 
Known as:  Pascal’s 11^th Identity

Catalog #: 1100007


                 
 The second difference equation of the row sequence is zero only at these values (and their mirror images on the same row) among all rows of Pascal’s Triangle
Proof

Return to top

1.2: B.C.s = non-B.C.

Catalog #: 1200001

                 
Known as: Row Sum Identity, Pascal’s 5^th Identity
Hint:  The difference triangle for the sequence 1, 2, 4, 8, 16, 32, ...

Catalog #: 1200002

               
Proof by picture
Generalized in Cat. # 3600002

Catalog #: 1200003
 , where F₀ = 0, F₁ = 1 and F_n = F_n-1 + F_n-2    
                 
Known as: The Binomial to Fibonacci Identity
Proof

Catalog #: 1200004
= # of non-negative integer 3×3 matrices where all row and column sums = n            
               
from Enumerative Combinatorics, Chapter 2, problem 6b

Catalog #: 1200005
where  is the ceiling of x, smallest integer n >= x
               
from Concrete Mathematics, page 228

Catalog #: 1200006
where r_max(n) for positive integers n is the maximum number of regions created in a circle by connecting n points on the circumference with straight lines
              
from The Colossal Book of Mathematics, page 561 by Martin Gardner; answered credited to Leo Moser
Note: first five entries are 1, 2, 4, 8, 16, but r_max(6) = 6 + 15 + 10 = 31 and r_max(7) = 57
As a polynomial, the function can be written as (n⁴ - 6n³ + 23n² - 18n + 24)/24

Catalog #: 1200007


from Table of integrals, series, and products by Gradshteyn and Ryzhik

Catalog #: 1200008


from Table of integrals, series, and products by Gradshteyn and Ryzhik

Catalog #: 1200009


from Table of integrals, series, and products by Gradshteyn and Ryzhik

Catalog #: 1200010

 
from Table of integrals, series, and products by Gradshteyn and Ryzhik

Catalog #: 1200011

 
from Table of integrals, series, and products by Gradshteyn and Ryzhik

Catalog #: 1200012
 

from Table of integrals, series, and products by Gradshteyn and Ryzhik

Catalog #: 1200013
 

from Table of integrals, series, and products by Gradshteyn and Ryzhik

Catalog #: 1200014

where F is a set of subsets of the set {1, 2, ..., n} such that no element of F is a subset of another element of F (this type of set sometimes called an antichain)

known as Sperner's Theorem
from Proof Techniques in the Theory of Finite Sets by Greene and Kleitman
published in MAA Studies In Mathematics, Vol. 17, edited by Rota
Hint:  If we take all subsets of some fixed equal size, none of them can be subsets of each other.

Catalog #: 1200015
For all positive integers m and k, there is a unique k-binomial representation of m

Hint: find the largest value in row k that is less than m, subtract that value from m, repeat the process on the remainder in row k-1, etc.

Catalog #: 1200016

known as Kruskal-Katona Theorem
uses the k-binomial representation from the identity above

Return to top

1.3: (non-B.C.s) = B.C.

Catalog #: 1300001

Known as: The relationship between the triangular numbers T_n and the 2^nd column of Pascal’s Triangle.

Catalog #: 1300002
 
Picture Proof                         


Catalog #: 1300003

                      
Known as: sum of odd cubes
Picture Proof

Return to top

1.4: B.C.s = (non-B.C.s)

Catalog #: 1400001

                     
Two ways to write the square numbers (see Cat. #: 1200002)

Return to top

1.5: B.C.s = mixed product

Catalog #: 1500001

                     
  Known as: Pascal’s 9^th Identity

Catalog #: 1500002

                     
  Known as: Pascal’s 10^th Identity

Return to top

                                                Category 2: Identities involving products and quotients

2.1:  B.C.s = B.C. And B.C.s =  B.C.s

Catalog #: 2100001

                         
Known as: trinomial revision
Hint: write out the fractions
From Concrete Mathematics, page 174
Note:  In his book Combinatorial Identities, Riordan writes that trinomial revision has 48 alternative forms.
One of the Top Ten Identities

Catalog #: 2100002

             
Known as:  The Star of David rule or The Hexagon Property
Hint: write out the fractions
From Concrete Mathematics, page 155
Compare to Cat. #: 5300001, the g.c.d version of the Star of David rule

Return to top

2.2: B.C.s = non-B.C.

Catalog #: 2200001

 , where all s_i are positive integers
                
Formula for binomial to multinomial coefficients
Example:  

Catalog #: 2200002

                          
picture proof  
communicated by Rick West

Return to top

2.3: (non-B.C.s) = B.C.

Catalog #: 2300001

  Known as: the factorial fractional formula
One of the Top Ten Identities

Catalog #: 2300002
 , where n^k = n(n-1)…(n-k+1) written also as (n)_k in Stanley
  Known as falling factorial representation, simplest when k <= ½n

Catalog #: 2300003
                     
Pascal’s Last Identity (from Part 2 of the Treatise)
Hint: write out the fractions

Return to top

2.4: mixed product = B.C.

Catalog #: 2400001

                         
Known as: The recursive multiplicative method for row entries, Pascal’s 7^th Identity
Hint: write out the fractions

Catalog #: 2400002
,  and
                         
 Known as: Absorption, Pascal’s 8^th Identity
Hint: write out the fractions
One of the Top Ten Identities

Catalog #: 2400003
 
                     
Known as: Pascal’s 12^th Identity
Proof

Catalog #: 2400004


Known as: Upper Negation, relates positive upper index B.C.'s to negative upper index B.C.'s
One of the Top Ten Identities

Return to top

 
2.5: mixed product = non-B.C.

Catalog #: 2500001

                     
The generalized binomial series
from Concrete Mathematics (5.58)
Also listed at Cat. #3900042, since it is properly a sum of products

Catalog #: 2500002
 , for n >= 0
                    
Known as: the Catalan numbers: 1, 1, 2, 5, 14, 42, etc. named for Eugene Catalan; equal to the coefficients of the B₂ series as defined above in Cat. # 2500001

Catalog #: 2500003
for all complex z and positive integer n
                    
This limit was discovered by Euler at the age of 22.  What did you do today?
from Concrete Mathematics, page 210

Catalog #: 2500004
for p > 1 if and only if p is a prime

Proof of half and a hint

Catalog #: 2500005


Formula for the Narayana numbers.  The sum of the n^th row of the Narayana triangle is C_n, the n^th Catalan number. The fact that this is always an integer is given by Cat. # 5200001.

Catalog #: 2500006
  for n , k non-negative integers with n >= k

from Proofs That Really Count, page 63
Hint:  Fractional factorial representation Cat. # 2300001

Catalog #: 2500007

number of digits in these central binomial coefficients divided by the appropraite power of 10 converges to log 4.

Return to top

                                Category 3: Identities involving sums of products and/or quotients

 
3.1: ( B.C.s) = B.C. and ( B.C.s) = B.C.s and ( B.C.s) = (mixed products)

Catalog #: 3100001

                         
Two proofs

Catalog #: 3100002

             
from A=B

Catalog #: 3100003

                     
Known as: Vandermonde’s Convolution
from Concrete Mathematics (5.22)
One of the Top Ten Identities

Special case: m = 0:      

from Proofs That Really Count, page 66
Hint for special case: How many ways can you pick n ornaments from a set with r red ornaments and s silver ornaments?
See our Java applet

Catalog #: 3100004

                 
from Concrete Mathematics (5.23)

Special case m = n = 0:      

Catalog #: 3100005
all non-negative n >= q
                
from Concrete Mathematics (5.26)

Special case: q = 0: 

from Proofs That Really Count, page 68

Catalog #: 3100006

   
from A=B, page 33

Catalog #: 3100007


Catalog #: 3100008


Catalog #: 3100009

Hint:  There is no "middle term" in an odd row and Cat# 3100001

Catalog #: 3100010

Catalog #: 3100011

Catalog #: 3100012

Catalog #: 3100013

Cat. #'s 3100010 through 3100013 are from a paper by Grzegorz Rzadkowski

Catalog #: 3100014

from Proofs That Really Count, page 78

Catalog #: 3100015

from Proofs That Really Count, page 78

Catalog #: 3100016

from Proofs That Really Count, page 78

Catalog #: 3100017

communicated by Andrés Masegosa
a generalization of Vandermonde's Convolution Cat. #3100003
Hint: the hint for the special case of  Vandermonde's Convolution would apply if you had more than two colors of ornaments.
See our Java applet

Return to top

3.2: ( B.C.s) = non-B.C.

 Catalog #: 3200001


Picture Proof                       

Catalog #: 3200002

  where n >= m                            
from Concrete Mathematics, pages 173-174

Catalog #: 3200003

                         
from Concrete Mathematics, page 187

Catalog #: 3200004

                          
from Concrete Mathematics, page 196
(can be derived from Cat. # 3200002)

Catalog #: 3200005
where f₀ = 0, f₁ = 1 and f_n = f_n-1 + f_n-2 , also known as the Fibonacci numbers 

from Proofs That Really Count, page 5

Catalog #: 3200006

where D(n,n) is a central Delannoy number

Return to top

3.3: ( non-B.C.s) = B.C.

Catalog #: 3300001

                     
Relation between the Stirling numbers of the First and Second kinds to generate the binomial coefficients
from Concrete Mathematics (6.24)

Catalog #: 3300002

   where n >= m
                    
Another relation between the Stirling numbers of the First and Second kinds to generate the binomial coefficients
from Concrete Mathematics (6.25)

Return to top

3.4: (alternating product) = B.C. or B.C.

Catalog #: 3400001

                     
Known as: Hockey Stick Theorem
Picture proof by induction

Catalog #: 3400002
where

Communicated by Daniel Soll
This is a relationship between the central binomial coefficients and the coefficients from the Lucas polynomials, which are further discussed through the link.
 
Return to top

3.5: (mixed product) = B.C. or B.C.

Catalog #: 3500001

                 
Picture Proof

Catalog #: 3500002

                      
Picture Proof

Catalog #: 3500003

                          
Picture Proof

Catalog #: 3500004
 
                     
from Concrete Mathematics, page 175
Hint: Multiple uses of Christmas Stocking Theorem

Catalog #: 3500005
  for m,n > 0         
  
from Concrete Mathematics, page 183

Catalog #: 3500006

                  
from A=B, page 31

 Catalog #: 3500007

                
from A=B, page 47

Catalog #: 3500008

                      
Known as: Reed-Dawson Identity (note: sum is 0 if over 2n+1)
from A=B, page 63

Catalog #: 3500009

Communicated by Bo Brinkman

Catalog #: 3500010

from Proofs That Really Count, page 78

Catalog #: 3500011

from Proofs That Really Count, page 78

Catalog #: 3500012

from Proofs That Really Count, page 78

Catalog #: 3500013

communicated by Gottfried Helms

Return to top

3.6: (alternating product) = alternating product

Catalog #: 3600001

             
from Concrete Mathematics (5.24)

Catalog #: 3600002

             
from Concrete Mathematics (5.25)

Catalog #: 3600003

                  
from Concrete Mathematics (5.55)
special case: let r = 2n, we get
from A=B, page 45

Return to top

 
3.6.1: (alternating product) = non-B.C.

Catalog #: 3610001
 The Kronecker delta function on 0, so it equals 1 when n=0 and 0 otherwise
                         
Known as: Alternating Row Sum Identity
Hint: (1-1)ⁿ, when n > 0, only one term = 1 when n = 0

Catalog #: 3610002

         
from Concrete Mathematics, page 177
(note similarity to Cat. #: 1200003, the Binomial to Fibonacci Identity) s₀=s₁=1, s_n = s_n-1 – s_n-2

Catalog #: 3610003

     
Known as: Dixon’s Identity (1903)

 Catalog #: 3610004
 , where k_ij are a set of index variables, numbering from 1 to
        
from Concrete Mathematics (5.31)
The authors considered this to be “the hairiest sum of binomial coefficients known”, this is the generalization of Dixon’s Identity to have more variables, both in the top entry of the binomial coefficient and in the index variables; it was conjectured by Freeman Dyson in 1962 and proved by several people shortly thereafter.  Here is a slightly more readable form of the specific example n = 4.


 
For more information on this monster, consult Concrete Mathematics.

Catalog #: 3610005

                     
from A=B, page 22
Note: if upper we use odd number 2n+1 as final summand, sum is 0
Note similarilty to Dixon's Identity (Cat. #3610003) when a = b = c = n

Catalog #: 3610006
, the Kronecker delta function on m and n

Known as: Orthogonality
Orthogonality and linear algebra (Java applet)

Catalog #: 3610007


A generalization of orthogonality
Presented by Vasyl Dmytrenko and Felix Lazebnik
Generalized orthogonality (Second applet on page)

Catalog #: 3610008
for all complex z

Communicated by Sebastián Martín Ruiz

Catalog #: 3610009

See the orthogonality applet for details

Return to top

 
3.7: (mixed product) = mixed product and (mixed product) = (mixed product)

Catalog #: 3700001
where n >= 0
            
from Concrete Mathematics, page 181

Catalog #: 3700002
for m,n > 0
            
from Concrete Mathematics, page 184
(uses Cat. #: 3700001 in proof)

Catalog #: 3700003
for x not an element of {0,-1,…,-n}
            
from Concrete Mathematics, page 188

Catalog #: 3700004
 
                 
Correction by Sean A. Irvine

Catalog #: 3700005

         
Known as:  The Inversion Formula
from Concrete Mathematics, page 193

Catalog #: 3700006

                     
From A=B, page 31

Catalog #: 3700007
  for m > n > 0 and (m+n) even
            
from Concrete Mathematics (5.112)

Catalog #: 3700008


Catalog #: 3700009


Cat. #'s 3700008 and 3700009 are from the paper An Extension of a Curious Binomial Identity by Zhi-Wei Sun and Ke-Jian Wu which can be accessed through this link; an alternate proof by David Callan can be found through this link, in paper A5 on the list.

Catalog #: 3700010


From Combinatorial Identities by Riordan, Chapter 1.3

Catalog #: 3700011

Known as: Cauchy's formula

From Combinatorial Identities by Riordan, Chapter 1.5

Catalog #: 3700012

Catalog #: 3700013


Cat. #'s 3700012 and 3700013 are from the paper A Binomial Identity, via Derangements by Leo Chao, Paul DesJarlais and John L. Leonard

Catalog #: 3700014

Communicated by Steven Poon
Hint: induction and absorption

Return to top

3.8: (mixed product) = alternating product
Currently empty

Return to top

 
3.9: (mixed product) = non-B.C.

Catalog #: 3900000

                     
Known as: The Binomial Theorem (about which we are teeming with a lot of news)
For example, by setting  y=1 we get,   
and y = -1 gives us  

and when p is between 0 and 1, is the probability of having exactly k successes in n attempts when the probability of success for any single attempt is p; if we sum up all these probabilities, the total must be 1.  More about this probability method here.
One of the Top Ten Identities

Catalog #: 3900001
where  is from Euler’s Triangle
                    
Known as: Worpitzky’s Identity
Proof by construction

Catalog #: 3900002
where  is from Euler’s Triangle
                   
Hint: Worpitzky’s Identity (Cat. #3900001) and the Christmas Stocking Theorem (Cat. #1100002)

Catalog #: 3900003