this is not an anwser: Please prove algebraicly!!! 40. Consider a set with a + b

Question

this is not an anwser: Please prove algebraicly!!!

40. Consider a set with a + b elements. We need to select n elements out of it.

There are two ways to do this.

(i) Directly choose n elements out of a + b elements.

This can be done in (a+b)Cn ways.

(ii) Take some elements out of first a elements and the remaining elements out of the remaining b elements.

We can take 0,1,2.......n-1, n elements out of a elements. Correspondingly we need to take n,n-1,n-2......1,0 elements out of b elements.

This can be done in aC0 * bCn + aC1 * bC(n-1) + aC2 * bC(n-2) + ...... aCn * bC0 ways.

Since both (i) and (ii) count the same thing, they are equal

=> aC0 * bCn + aC1 * bC(n-1) + aC2 * bC(n-2) + ...... aCn * bC0 = (a+b)Cn.

41. In the answer of 40, if we put a = b = n, we get

nC0 * nCn + nC1 * nC(n-1) + nC2 * nC(n-2) + ...... nCn * nC0 = (n+n)Cn.

Using the property nCr = nC(n-r)

=> nC0 * nC0 + nC1 * nC1 + nC2 * nC2 + ...... nCn * nCn = (2n)Cn.

=> nC02 + nC12 + nC22 + ...... nCn2 = (2n)Cn.

Et cetera... (40) For any positive integers a, b, and n, prove that () + () - ()) on () () M (41) Prove that 2n ()()is a +() - ()

Explanation / Answer

40. We shall prove by mathematical induction

Base case: n = 0

LHS = ac0 * bC0

= 1 * 1 = 1

RHS = (a + b)C0 = 1

LHS = RHS

Inductive hypothesis: Let the result be true for n = m

=> aC0 * bCm + aC1 * bC(m-1) + aC2 * bC(m-2) + ...... aCm * bC0 = (a+b)Cm

To prove: aC0 * bC(m+1) + aC1 * bCm + aC2 * bC(m-1) + ...... aC(m+1) * bC0 = (a+b)C(m+1)

Proof: Using inductive hypothesis

=> aC0 * bCm + aC1 * bC(m-1) + aC2 * bC(m-2) + ...... aCm * bC0 = (a+b)Cm

Multiplying by (b-m+1) / (m+1) both sides

=> aC0 * bCm * (b-m+1) / (m+1) + aC1 * bC(m-1) * (b-m+1) / (m+1) + aC2 * bC(m-2) * (b-m+1) / (m+1) + ...... aCm * bC0 = (a+b)Cm * (b-m+1) / (m+1)

=> aC0 * b! / [m!(b-m)!] * (b-m) / (m+1) +  aC1 * b! / [(m-1)!(b-m+1)!] * (b-m) / (m+1) + aC0 * b! / [(m-2)!(b-m+2)!] * (b-m) / (m+1) +.......... aCm * b! / [0!b!] * (b-m) / (m+1) = [(a+b)! / [m!(a+b-m)!] * (b-m) / (m+1)

=> aC0 * b! / [(m+1)!(b-m-1)!] + aC1 * b! / [m!(b-m)!] + aC2 * b! / [m!(b-m+1)!] + .....aCm * b! / [0!b!] = (a+b)! / [(m+1)!(a+b-m-1)!]

=> aC0 * bC(m+1) + aC1 * bCm + aC2 * bC(m-1) + ...... aC(m+1) * bC0 = (a+b)C(m+1).

Thus the result is also true for n = m+1 and by induction for all n.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.