this is not an anwser: Please prove algebraicly!!! 40. Consider a set with a + b
ID: 3335527 • Letter: T
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
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.