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, the Fibonacci numbers  
                 
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

Catalog #: 1200017
where f_n is the n^th Fibonacci number, starting with f₀ = 0, f₁ = 1, etc.

from Proofs that Really Count by Benjamin and Quinn, page 78

Catalog #: 1200018
where f_n is the n^th Fibonacci number, starting with f₀ = 0, f₁ = 1, etc.

from Proofs that Really Count by Benjamin and Quinn, page 78
Hint:  #1200017 and #1200018 can be proven from #1200003 and the symmetry rule, #1000001

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 

Catalog #: 1300004

(Note: Last subscript is a_{k -1}.)

communicated by Ron Ozer

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

Catalog #: 2100003

Hint: write out the fractions
communicated by Pieter H. Van Der Kamp

Catalog #: 2100004

Hint: Cat. #2100003 and Cat. #2300003, distinguish between odd and even cases
communicated by Pieter H. Van Der Kamp

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

Catalog #: 2200003

Catalog #: 2200004

communicated by Sebastián Martín Ruiz
Hint:  Look at the middle product for the square matrix of ordered pairs A_i,j = (i, j)

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