SOLUTION: Let n and r be positive integers with n ≥ r. Prove that rCr + (r+1Cr)+...+( nCr) = (n+1Cr+1)
Algebra.Com
Question 1102843: Let n and r be positive integers with n ≥ r. Prove that rCr + (r+1Cr)+...+( nCr) = (n+1Cr+1)
Answer by math_helper(2461) (Show Source): You can put this solution on YOUR website!
Proof by induction (using C(n,r) notation):
n=0: C(0,0) = 1 = C(1,1)
Assume its true for n=k:
n=k: C(r,r)+C(r+1,r)+ … + C(k-1,r) + C(k,r) = C(k+1, r+1) (*)
—
Now we need to show that it follows that (*) leads to the equality holding for n=k+1:
n=k+1: C(r,r)+C(r+1,r)+ … + C(k-1,r) + C(k,r) + C(k+1,r)
Adding brackets around all but the last term from above:
[ C(r,r)+C(r+1,r)+ … + C(k-1,r) + C(k,r) ] + C(k+1,r)
The part between brackets [ ] is (*):
= C(k+1, r+1) + C(k+1, r)
=
—
— re-writing the above by multiplying the 2nd term by (r+1)/(r+1) and
— pulling out the first factor of (k+1-r)! in the denominator:
—
=
—
— allows us to factor to:
—
=
—
=
=
=
= Done. Assuming truth for n=k ==> true for n=k+1
—
The last statement can be re-written as
=
because n=k+1.
RELATED QUESTIONS
Prove that nC r + nCr-1 =... (answered by sachi)
prove that:... (answered by venugopalramana)
Prove nCr = n/(n-r) * n-1Cr using an analytic and combinatoial... (answered by richard1234)
Please help me to solve this Qeustion(1) Prove that nCr=n+1Cr-nCr-1
and Qeustion (2)... (answered by math_helper)
Use the fact that nCr = n!/(n-r)!r! to show that:
a.). nCr = nCn-r
b.)... (answered by Edwin McCravy)
n-1cr-1... (answered by ikleyn,robertb)
Show that the way in which the entries in Pascal's triangle are formedby adding "above... (answered by Edwin McCravy)
prove that:... (answered by venugopalramana)
nCr/nCr-1 = (n-r+1)/r
prove it (answered by Edwin McCravy)