SOLUTION: PLEASE HELP!!! Prove that U (n choose k-1) + (n choose k)=(n+1 choose k) for all natural numbers n and k, with k ≤ n.

Algebra ->  Finance -> SOLUTION: PLEASE HELP!!! Prove that U (n choose k-1) + (n choose k)=(n+1 choose k) for all natural numbers n and k, with k ≤ n.      Log On


   

Question 1073142: PLEASE HELP!!!
Prove that U
(n choose k-1) + (n choose k)=(n+1 choose k)
for all natural numbers n and k, with k ≤ n.
Answer by KMST(5328) About Me  (Show Source):
You can put this solution on YOUR website!
%28matrix%282%2C1%2Cn%2Ck-1%29%29%22=%22n%21%2F%28%28k-1%29%21%28n-%28k-1%29%29%21%29%22=%22n%21%2F%28%28k-1%29%21%28n-k%2B1%29%21%29 is n choose k-1.
%28matrix%282%2C1%2Cn%2Ck%29%29%22=%22n%21%2F%28k%21%28n-k%29%21%29 is n choose k.
The key to the proof is understanding that for any positive integer, h ,
%28h%2B1%29%21%22=%22%28h%2B1%29%2Ah%21 .
Let us add those two fractions.
%28matrix%282%2C1%2Cn%2Ck-1%29%29%22%2B%22%28matrix%282%2C1%2Cn%2Ck%29%29%22=%22n%21%2F%28%28k-1%29%21%28n-k%2B1%29%21%29%2Bn%21%2F%28k%21%28n-k%29%21%29
Taking out the common factors, we get
%28matrix%282%2C1%2Cn%2Ck-1%29%29%22%2B%22%28matrix%282%2C1%2Cn%2Ck%29%29%22=%22%28n%21%2F%28%28k-1%29%21%28n-k%29%21%29%29%2A%281%2F%28n-k%2B1%29%2B1%2Fk%29
Now we just have to deal with that simpler sum,
using as common denominator the product
%28n-k%2B1%29k .
So, we get
%28matrix%282%2C1%2Cn%2Ck-1%29%29%22%2B%22%28matrix%282%2C1%2Cn%2Ck%29%29%22=%22
%22=%22%28n%21%28n%2B1%29%29%2F%28%28%28k-1%29%21k%29%28%28n-k%2B1%29%28n-k%29%21%29%29
%22=%22%28n%2B1%29%21%2F%28k%21%28n-k%2B1%29%21%29%22=%22%28n%2B1%29%21%2F%28k%21%28%28n%2B1%29-k%29%21%29%22=%22%28matrix%282%2C1%2Cn%2B1%2Ck%29%29