SOLUTION: 5. Verify the identity. Justify your steps. a) nC0 = 1 b) n+1Cr = nCr + nCr-1 c) nC1 = nP1

Question 1116460: 5. Verify the identity. Justify your steps.
a) nC0 = 1
b) n+1Cr = nCr + nCr-1
c) nC1 = nP1

Answer by math_helper(2461) (Show Source): You can put this solution on YOUR website!
Note about notation I will use:
1. nCr = C(n,r) =
2. nPr = P(n,r) =

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):
Left Hand Side (LHS): C(n+1,r) =
RHS: C(n,r) + C(n,r-1) =
The RHS can be re-written:
=
factor out
=
put 2nd factor over common denominator
=
simplify 2nd factor
=
combine loose factors into factorials, e.g. (n+1)*n! = (n+1)!, etc.
= = LHS (DONE)

To do (a), remember 0! = 1 then use equation 1.
To do (c), plug into 1. and 2. and compare.

==================================
Intuitive argument for (b):

Start with a set S of n+1 elements: S = { X1, X2, X3, �, Xn, Xn+1 }

Obviously you can choose r elements from this set in C(n+1, r) ways. That's the LHS.

Now label one element of S with a *, it doesn't matter which one.

In choosing r elements from S, there are two possibilities: (1) exclude element * or (2) include element *.
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.

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.

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.

RELATED QUESTIONS
n-1cr-1... (answered by ikleyn,robertb)

Use the fact that nCr = n!/(n-r)!r! to show that: a.). nCr = nCn-r b.)... (answered by Edwin McCravy)

Using the result ncr + ncr-1 = n +1cr compute 10c5 +10C4 (answered by richard1234)

Simplify (a) nCr+nCr-1 (b) n+1C3-nC3 (c)... (answered by ikleyn)

Prove that nC r + nCr-1 =... (answered by sachi)

How to verify the identity of: (n+1)Cr= nCr +... (answered by ikleyn)

Prove that nCr is less than or equal to n+1Cr+1 . Hint: Make use of the fact that if A (answered by richard1234)

Hello, I'm at a loss of how to solve this. Any help would be very much appreciated.... (answered by Edwin McCravy)

Let n and r be positive integers with n ≥ r. Prove that rCr + (r+1Cr)+...+( nCr) =... (answered by math_helper)