Prove that nCr−1+nCr=n+1Cr
nCr−1+nCr=n+1Cr
Without the use of formula:
Suppose we have to take r things out of (n+1) things. Then there are n+1Cr combinations.
Now to find the combinations in which a particular thing always occurs we shall set aside that particular thing and form the combinations from the remaining n things taking r - 1 at a time which will be
nCr−1. (1)
Again we shall find the combinations in which a particular thing we have only n things from which we have to form combinations of taken r at a time which will be nCr. (2)
Clearly the sum of the combinations formed in the above two ways will be n+1Cr.
∴ nCr−1+nCr=n+1Cr
Alternative formula :
With use of formula
n+1Cr=(n+1)!r!(n−r+1)! (1)
nCr−1+nCr=n!(r−1)!(n−r+1)!+n!r!(n−r)!
Now (n−r+1)!=(n−r+1)(n−r)!
andr!=r.(r−1)!
∴ R.H.S/ = n!(r−1)(n−r)![1n−r+1+1r]
= n!(n+1)r.(r−1)!(n−r+1).(n−r)!
=(n+1)!r!(n−r+1)! (2)
Hence from (`1) and (2) we get
nCr−1+nCr=n+1Cr
nCr−1+nCr=n+1Cr
Without the use of formula:
Suppose we have to take r things out of (n+1) things. Then there are n+1Cr combinations.
Now to find the combinations in which a particular thing always occurs we shall set aside that particular thing and form the combinations from the remaining n things taking r - 1 at a time which will be
nCr−1. (1)
Again we shall find the combinations in which a particular thing we have only n things from which we have to form combinations of taken r at a time which will be nCr. (2)
Clearly the sum of the combinations formed in the above two ways will be n+1Cr.
∴ nCr−1+nCr=n+1Cr
Alternative formula :
With use of formula
n+1Cr=(n+1)!r!(n−r+1)! (1)
nCr−1+nCr=n!(r−1)!(n−r+1)!+n!r!(n−r)!
Now (n−r+1)!=(n−r+1)(n−r)!
andr!=r.(r−1)!
∴ R.H.S/ = n!(r−1)(n−r)![1n−r+1+1r]
= n!(n+1)r.(r−1)!(n−r+1).(n−r)!
=(n+1)!r!(n−r+1)! (2)
Hence from (`1) and (2) we get
nCr−1+nCr=n+1Cr
