Combinatorial Identities: ‘Combinatorial identities, often used in combinatorics, are mathematical expressions that equate two different ways of counting or organizing objects. They arise from counting the same collection of objects in two different ways, leading to an identity that holds true regardless of the specific values of the variables involved. Proofs of combinatorial identities often involve demonstrating that both sides of the equation represent the same counting problem. This can be done by finding a bijection (a one-to-one correspondence) between the sets being counted on each side of the equation or by using algebraic manipulations to transform one expression into the other. ‘Some basic combinations are given below:- 1) Prove that (") = (,",) (Known as complementary combinations) Prooft- LHS.=(*)= 5 RuS.=(")= oa a...) 2) Prove that (") =(""}) (provided that 221 Proof: Ql) net) 9 Got RHS.=8(() =? ae nest fl (2) a) *e=DIO=-FDT From (1) and (2), we have (") = 2(*}) Hence Proved.3) Prove that ()==(") (provided that r21) Proof: Las. (‘5 Lins, = St") ay From (I) and (2), we have (*)=#(.")) Hence Proved 4) Prove hat (*)=("-t)+(",") Las. (Go CH RH From (1) and (2), we have (*)=(27))+(°") Hence Proved.5) Prove that(," )(™)=(" )( ar) Proof:- uus-(5)(¢) “Fem rus=(7)(cr) = me From (1) &(2), we have (2. )(%)= (=) (Grr) Hence Proved: 6) Prove that (") === ) Proof:- LHS=(1)= 7 A) my 8 fet From (1) & (2), we have (* = 2, (*7)) Hence Proved.Example 22:- Show that for all eo neN, Solution:- We can write the binomial theorem in signa notation as: Oey @+y" Putting Nel, we have J, 9(verr=5 C0" Differentiating both sides werty. we get n+ yt = yo meray” Cearey Or war (+2() 22G)--n6) Yer) 2 Chen Example 23:- ‘Show that for all integers nEN. x, ("e(*) +27 (0) + 32 (Mesut n?(") = n(n + 1)2"°? Solution: wwe can write the binomial theorem in sigma notation as: wore) Oey Putting x=1, we have arr=h( Qorv=7 (yr os Differentiating both sides w.ry. wwe getatl + yy = YOr yo soneaan at Differentiating again both sides w.r..y, we got YO) ms n= 1) ty Puty=l, n@a= 1) +1)" = y ()ro- yoy (r= age = N@" = 20 (") +E ("4e(").-+m- 9 (2) nin-t)@@)""2=2 (") +6 (") +12 (")...tmene)(*) Adding S7_, 1 (")to both side of the above equation n(n = Dy" + Dyr(*)=2(t) +6(C)+12()-ra@—9()+ Zar() Expanding the summation from R. H. S. we have, n= nents Sr(°)=2(0) +60) +12(,) 4-9) + & -2(0) +6(°) +12(°)...+ aD ()+()+2@+30) +40) a Combining the like terms on R. H. S. we get, =()*4@) 2) » #16 (4) ou Engn~ 1) +m) () n(n = 12"? + oO) =r( (+2) + eQ)+#() '). one (") Writing the value of summation on L, HLS. fom the previous example n(n= sant net =12(*) +22 (0) +3#(2) +4 (().- +n2(") pe ensnaiersan()e24Qea@)+e()-+e()=2n0e() otear (2 QerQee Ore O=mued) Bar (hC)+2 Qs O-teenarnePascal's Identity and Pascal's Triangle:- The set of binomial coefficients (") can be conveniently arranged in a triangular form from top to bottom and left to right in increasing order of the values n and respectively. This diagram is called the Pascal Triangle (after the renown French mathematician Blaise Pascal who discovered it in 1653). The triangle is also called Yang Huis triangle in China as its discovery was claimed by Chiness mathematician Yang Hui much earlier In 1261. The Pascal's gle is shows below Here, we make some observations with reference tothe diagram shown. (As (") = (%,) so entries ofthe triangle are symmetric with respect 0 the vertical line passing through the vertex () (ii) The sum of the binomial coefficients a the mh level is equal to 20. The binomial coefficients satisfy many identities. One of them given below in the form of a theorem. (iii) Pascal's identity, together with initial conditions (") = (" *) = 1 can be used 10 recursively define binomial coefficients. This recursive definition is useful in the computation of binomial coefficients, Pascal's identity shows when get two adjacent binomial coefficients in this triangle are added, we get the next coefficientsNote: (?) + (2) = (°) that is used to produce the next row of triangle ne the above arrangemens, using the Pasca'stdenty(*) + (,",) = ("t") fe get the next terms of binomial coeffici Sie of numbers is ee ficients, anda triangle of numbers is formed 14641 151010 51 1615 201561 ‘Theorem: 2.1.3. (Pascal's identity):- Let n and r be positive integers with nr, then ae Cs)=C") Proof: ‘The proof of the Pascal's identity as However, itis possible to prove this identity by algebraic manipulation from the di a nt me formula (")==¥ 5 Here we use the ‘algebraic approach Foe * TOA wus.-()+( 5 + one A combinatorial proof has already given. rect 5 Fir De " Tarn Gtr om (este wane ocr Daa Manet) oe ore alt Fara * )= (1!) tence Proved. From (1) and (2),e have (") +(,",