Share
Explore BrainMass

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

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.

\$2.19