document.write( "Question 1102843: Let n and r be positive integers with n ≥ r. Prove that rCr + (r+1Cr)+...+( nCr) = (n+1Cr+1) \n" ); document.write( "
Algebra.Com's Answer #717619 by math_helper(2461)\"\" \"About 
You can put this solution on YOUR website!
Proof by induction (using C(n,r) notation):\r
\n" ); document.write( "\n" ); document.write( "n=0: C(0,0) = 1 = C(1,1)\r
\n" ); document.write( "\n" ); document.write( "Assume its true for n=k:
\n" ); document.write( "n=k: C(r,r)+C(r+1,r)+ … + C(k-1,r) + C(k,r) = C(k+1, r+1) (*)
\n" ); document.write( "—
\n" ); document.write( "Now we need to show that it follows that (*) leads to the equality holding for n=k+1:
\n" ); document.write( "n=k+1: C(r,r)+C(r+1,r)+ … + C(k-1,r) + C(k,r) + C(k+1,r)
\n" ); document.write( "
\n" ); document.write( "Adding brackets around all but the last term from above:
\n" ); document.write( "[ C(r,r)+C(r+1,r)+ … + C(k-1,r) + C(k,r) ] + C(k+1,r) \r
\n" ); document.write( "\n" ); document.write( "The part between brackets [ ] is (*):
\n" ); document.write( "= C(k+1, r+1) + C(k+1, r)
\n" ); document.write( "=
\n" ); document.write( "—
\n" ); document.write( "— re-writing the above by multiplying the 2nd term by (r+1)/(r+1) and
\n" ); document.write( "— pulling out the first factor of (k+1-r)! in the denominator:
\n" ); document.write( "—
\n" ); document.write( "=
\n" ); document.write( "—
\n" ); document.write( "— allows us to factor to:
\n" ); document.write( "—
\n" ); document.write( "=
\n" ); document.write( "—
\n" ); document.write( "=
\n" ); document.write( "=
\n" ); document.write( "= \"+++%28k%2B2%29%21%2F%28%28k%2B1-r%29%21%28r%2B1%29%21%29+\"
\n" ); document.write( "= \"++C%28k%2B2%2Cr%2B1%29+\" Done. Assuming truth for n=k ==> true for n=k+1
\n" ); document.write( "—
\n" ); document.write( "The last statement can be re-written as
\n" ); document.write( "= \"++C%28n%2B1%2Cr%2B1%29+\"
\n" ); document.write( "because n=k+1. \r
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( " \n" ); document.write( "
\n" );