# Proofs Using Induction, Pascal's Formula, Differentiation

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 - 1 choose k - 1 plus n - 1 choose k for all 0 < k < n; n greater than or equal to 0

2. Please prove using the Inclusion and Exclusion Principle.

Patrons of a local bookstore can sign up for advance notification of new book arrivals in genres of interest. In the first month of this service, 32 sign up for mysteries, 34 for spy novels, 18 for westerns, and 41 for science fiction. Of these, 17 sign for both mysteries and spy novels, 8 for both mysteries and westerns, 19 for mysteries and science fiction, 5 for spy novels and westerns, 20 for spy novels and science fiction, and 12 for westerns and science fiction. In addition, 2 sign up for mysteries, spy novels and westerns; 11 for mysteries, spy novels, and science fiction; 6 for mysteries, westerns, and science fiction; and 5 for spy novels, westerns, and science fiction. Finally, 2 people sign up for all four categories. How many people signed up for service in the first month?

3. Prove using Pascal's formula.

C(n + 2, r) = C(n,r) + 2C(n, r - 1) + C(n, r - 2) for all 2 less than or equal to r which is less than or equal to n

4. a) Expand (1 + x)^n

b) Differentiate both sides of the equation from part (a) with respect to x to obtain:

n(1 + x)^n-1 = C(n, 1) + 2C(n, 2)x + 3C(n, 3)x^2 + ... + nC(n, n)x^n-1

c) Prove that C(n, 1) + 2C(n, 2) + 3C(n, 3) + ... + nC(n,n) = n2^n-1

d) Prove that C(n, 1) - 2C(n,2) + 3C(n, 3) - 4C(n, 4) + ... + (-1)^n-1 ? nC(n, n) = 0

5. a) Prove that (2^n + 1) / (n + 1) = C(n,0) + (1/2)C(n,1) + (1/3)C(n,2) + ... +

(1/n+1)C(n,n)

b) Prove that (1/n + 1) = C(n,0) + (1/2)C(n,1) + (1/3)C(n,2) + ... + (-1)^n ? (1/n + 1)C(n,n)

#### 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 ...

#### Solution Summary

The solution gives step-by-step solutions to the proofs.