Proofs Using Induction, Pascal's Formula, Differentiation

Solution Preview

---

Double check your formulas for number 5.

1. Please prove the following using induction.

n choose 0 = n choose n = 1 for all n greater or equal to 0

"n choose k" = n!/(n - k)!k!. So, the problem turns into proving that:

n!/(n - 0)!(0!) = n!/(n - n)!(n!) = 1

for all n greater than or equal to 0. You can prove this without induction, just by simplifying the above formula and using the fact that 0! = 1. But, to prove this by induction, look at the case of n = 0, then assume that it's true for n = k, and prove for n = k + 1.

n = 0:

The statement becomes:

0!/(0 - 0)!(0!) = 0!/(0 - 0)!(0!) = 1
1/1*1 = 1/1*1 = 1
1 = 1 = 1

Assuming the statement is true for n = k, prove it is true for n = k + 1:

Plugging n = k + 1 into the problem, you get:

(k+1)!/(k+1 - 0)!(0!) = (k+1)!/(k+1- k -1)!(k+1)! = 1

Because (k + 1)! = k!(k + 1), this can be written as:

k!(k + 1)/(k+1 - 0)!(0!) = k!(k + 1)/(k+1- k -1)! k!(k + 1) = 1
k!(k + 1)/(k+1)!(0!) = k!(k + 1)/(0)! k!(k + 1) = 1
k!(k + 1)/k!(k+1)(0!) = k!(k + 1)/(0)! k!(k + 1) = 1
k!/k!(0!) = k!/(0)! k! = 1

Using k = k -0 and 0 = k - k, the previous statement can be written as k!/(k - 0)!(0!) = k!/(k - k)!(k!) = 1, which is the statement when n = k. Because we're assuming that the statement is true for n = k, we have also shown that it is true for n = k + 1.

n choose k = n - 1 choose k - 1 plus n - 1 choose k for all 0 < k < n; n greater than or equal to 0

The problem turns into showing the following:

n!/(n - k)!(k!) = (n-1)!/(n-1 - (k-1))!(k-1)! + (n-1)!/(n-1 - k)!(k!)

Simplified, that looks like:

n!/(n - k)!(k!) = (n-1)!/(n-1 - k + 1)!(k-1)! + (n-1)!/(n - 1 - k)!(k!)
n!/(n - k)!(k!) = (n-1)!/(n - k)!(k-1)! + (n-1)!/(n - k - 1)!(k!)

k = 1:

n!/(n - 1)!(1!) = (n-1)!/(n - 1)!(1-1)! + (n-1)!/(n - 1 - 1)!(1!)
n!/(n - 1)! = (n-1)!/(n - 1)! + (n-1)!/(n - 2)!
n = 1 + n - 1
n = n

Assuming the statement is true for k = j, prove it is true for k = j + 1:

Plugging k = j + 1 into the problem, you get:

n!/(n ...