if 1 <=r<=n prove that ncr + ncr-1 = ncr +n+1cr+1

1 Answer | Add Yours

marizi's profile pic

marizi | High School Teacher | (Level 1) Associate Educator

Posted on

Combinations refers to number of ways to select "k" objects from a "n" collection. The formula for  combination of n things taken k at a time without repetition follows the formula:

`_nC_k` or C(n,k) =` (n!)/(k!(n-k)!)`

With the given condition `1<=r<=n` , it shows that  r and n are both non-negative integers greater than 1.` `

It coincides with the definition of factorial of non-negative integer "n" is the product of all positive integers less than or equal to n.

Factorial notation: `n= n*(n-1)!`

For the given, please double check the expression at the right-hand side.

They are not equal.

To clarify this, we may let n=7 and r =5.

Plug-in the values as shown:

`_nC_r + _nC_(r-1) ` =? `_nC_r + _(n+1)C_(r+1)`

`_7C_5 + _(7)C_(5-1)` =?` _7C_5 + _(7+1)C_(5+1)`

 `_7C_5 + _7C_4 `  = ?`_7C_5 + _8C_6`

   21  + 35  =?   21 +  28

          56 ≠ 49

In addition, it can be simplified as:

`_nC_r +_nC_(r-1)` = `_nC_r + _(n+1)C_(r+1)`

- `_nC_r `                       - `_nC_r`

-------------------------------------------------------------

               `_nC_(r-1)` = `_(n+1)C_(r+1)`

It will still not be an equal values. To check, we let n=7 and r=5 :

    ` ` = ` `

`_7C_(5-1)` =?` _(7+1)C_(5+1)`

`_7C_4` =?  `_8C_6`    

35  =?  28

 35 ≠ 28

  It might have been given as` _nC_r + _nC_(r-1)`  =`_(n+1)C_r` ` `

Starting at the left-hand side (LHS), we may apply the combination formula as:

`_nC_r + _nC_(r-1)` = `(n!)/(r!(n-r)!) +(n!)/(r!(n-(r-1))!)`

                            =`(n!)/(r!(n-r)!) +(n!)/((r-1)!(n-r+1)!) `       Simplify: `(n-(r-1)) =(n-r+1)`

                           =`(n!)/(r*(r-1)!(n-r)!) +(n!)/((r-1)!(n-r+1)(n-r)!)`

     Note

:` r! = r*(r-1)!`   and

`(n-r+1)! = (n-r+1)(n-r+1-1)! = (n-r+1)(n-r)!`

Factoring out `(n!)/((r-1)!(n-r)!)` :

`(n!)/((r-1)!(n-r)!) * ( 1/r +1/(n-r+1)) = (n!)/((r-1)!(n-r)!) * ( (n-r+1) +r)/(r(n-r+1)) `                           

                                              =`(n!)/((r-1)!(n-r)!) * (n+1)/(r(n-r+1)) `

                                              = `((n+1)(n!))/(r(r-1)!(n-r+1)(n-r)!) `

                                              = `((n+1)!)/(r!(n-r+1)!) ` or `((n+1)!)/(r!((n+1)-r)!)`  

                                              = `_(n+1)C_r`

Proof:  LHS = RHS

`_nC_r + _nC_(r-1)` = _(n+1)C_r

`_(n+1)C_r` =`_(n+1)C_r`

                              

Checking using n=7 and r=5 shows:

`_7C_5 + _7C_(5-1)` =? ` _(7+1)C5`

`_7C_5 + _7C_4 ` =? `_8C_5`

  21    +35  =? 56

        56 = 56

Sources:

We’ve answered 318,910 questions. We can answer yours, too.

Ask a question