document.write( "Question 1116460: 5. Verify the identity. Justify your steps.
\n" ); document.write( "a) nC0 = 1
\n" ); document.write( "b) n+1Cr = nCr + nCr-1
\n" ); document.write( "c) nC1 = nP1
\n" ); document.write( " \n" ); document.write( "
Algebra.Com's Answer #731430 by math_helper(2461)\"\" \"About 
You can put this solution on YOUR website!
Note about notation I will use:
\n" ); document.write( "1. nCr = C(n,r) = \"+n%21%2F%28%28n-r%29%21r%21%29+\"
\n" ); document.write( "2. nPr = P(n,r) = \"+n%21%2F%28n-r%29%21++\"
\n" ); document.write( "
\n" ); document.write( "I will do b) which is the hardest part. Furthermore, I will do it algebraically only (it doesn't provide any great insight, but there are good websites that use arrangements of subsets of n and n+1 elements and use a logical argument to show the equality holds):\r
\n" ); document.write( "\n" ); document.write( "Left Hand Side (LHS): C(n+1,r) = \"+%28n%2B1%29%21%2F%28%28n%2B1-r%29%21r%21%29+\"
\n" ); document.write( "RHS: C(n,r) + C(n,r-1) = \"++%28n%21%2F%28%28n-r%29%21r%21%29%29+%2B+%28n%21%2F%28%28n-r%2B1%29%21%28r-1%29%21%29%29+\"\r
\n" ); document.write( "\n" ); document.write( "The RHS can be re-written:\r
\n" ); document.write( "\n" ); document.write( " =
\n" ); document.write( "factor out \"+n%21%2F%28%28n-r%29%21r%21%29+\"
\n" ); document.write( " = \"++%28n%21%2F%28%28n-r%29%21r%21%29%29+%28+1+%2B+r%2F%28n-r%2B1%29+%29+\"
\n" ); document.write( "put 2nd factor over common denominator
\n" ); document.write( " = \"++%28n%21%2F%28%28n-r%29%21r%21%29%29+%28+%28n+-+r+%2B1++%2B+r%29+%2F+%28n-r%2B1%29+%29+\"
\n" ); document.write( "simplify 2nd factor
\n" ); document.write( " = \"++%28n%21%2F%28%28n-r%29%21r%21%29%29+%28+%28n+%2B1+%29+%2F+%28n-r%2B1%29+%29+\"
\n" ); document.write( "combine loose factors into factorials, e.g. (n+1)*n! = (n+1)!, etc.
\n" ); document.write( " = \"++%28%28n%2B1%29%21%2F%28%28n%2B1-r%29%21r%21%29%29+\" = LHS (DONE)
\r
\n" ); document.write( "\n" ); document.write( "To do (a), remember 0! = 1 then use equation 1.
\n" ); document.write( "To do (c), plug into 1. and 2. and compare.
\n" ); document.write( "
\n" ); document.write( "==================================
\n" ); document.write( "Intuitive argument for (b):
\r
\n" ); document.write( "\n" ); document.write( "Start with a set S of n+1 elements: S = { X1, X2, X3, …, Xn, Xn+1 }
\r
\n" ); document.write( "\n" ); document.write( "Obviously you can choose r elements from this set in C(n+1, r) ways. That's the LHS.
\r
\n" ); document.write( "\n" ); document.write( "Now label one element of S with a *, it doesn't matter which one.
\r
\n" ); document.write( "\n" ); document.write( "In choosing r elements from S, there are two possibilities: (1) exclude element * or (2) include element *.
\n" ); document.write( "If it is excluded, that means you are choosing r elements from the remaining n, and that can be done in C(n,r) ways.
\r
\n" ); document.write( "\n" ); document.write( "Case (2). If element * is included, you are choosing element * (only 1 way to do this) and r-1 elements from the remaining n elements: this can be done in C(n,r-1) ways.
\r
\n" ); document.write( "\n" ); document.write( "We must add these two mutually exclusive possibilities: C(n,r) + C(n,r-1). That's the RHS and it is equal to the LHS.
\n" ); document.write( " \r
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( " \n" ); document.write( "
\n" );