1 Please prove the following using induction

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 - k)!(k!) = (n-1)!/(n - k)!(k-1)! + (n-1)!/(n - k - 1)!(k!)

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

n!/(n - j - 1)!(j + 1)! = (n-1)![1/(n - j - 1)!(j)! + 1/(n - j - 2)!(j + 1)!]

n!/(n - j - 1)!(j + 1)! = (n-1)![1/(n - j - 1)(n - j - 2)!(j)! + 1/(n - j - 2)!(j + 1)(j)!]

n!/(n - j - 1)!(j + 1)! = (n-1)![(j + 1)/(n - j - 1)(n - j - 2)!(j + 1)(j)! + (n - j - 1)/(n - j - 1)(n - j - 2)!(j + 1)(j)!]

n!/(n - j - 1)!(j + 1)! = (n-1)![(j + 1 + n - j - 1)/(n - j - 1)(n - j - 2)!(j + 1)(j)!]

n!/(n - j - 1)!(j + 1)! = (n-1)![(n)/(n - j - 1)!(j + 1)!]

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

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?

The inclusion and exclusion principle say that if A and B are finite sets, the number of elements in the union of A and B can be obtained by adding the number of elements in A to the number of elements in B, and then subtracting from this sum the number of elements in the intersection of A and B. We can extend this to more than 2 sets (notice that the plus and minus signs alternate):

Here, the sets are genres of books. The information in the problem is summarized below:

mysteries 32 mysteries&spy 17 mysteries&spy&westerns 2
spy 34 mysteries&westerns 8 mysteries&spy&scifi 11
westerns 18 mysteries&scifi 19 mysteries&westerns&spy 6
sci fi 41 spy&westerns 5 spy&westerns&scifi 5
spy&scifi 20
westerns&scifi 12 all 4 groups 2

125 people signed up for at least one category, 81 signed up for at least two, 24 signed up for at least three, and 2 signed up for all four.

Using the inclusion-exclusion formula, that gives us 125 - 81 + 24 - 2 = 66 people who signed up 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

Pascal's formula is stated in the second part of question 1. It says that C(n, r) = C(n - 1, r) + C(n - 1, r - 1). Applying this to C(n + 2, r) gives us:

C(n + 2, r) = C(n + 1, r) + C(n + 1, r - 1)
C(n + 2, r ) = C(n, r) + C(n, r - 1) + C(n, r - 1) + C(n, r - 2)
C(n + 2, r ) = C(n, r) + 2C(n, r - 1) + C(n, r - 2)

Why is r limited to between 2 and n?

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

A generalized form of this is given by the binomial theorem:
Here, y = 1.

n = 1:

(1 + x)

n = 2:

(1 + x)2 = 1 + 2x + x2

n = 3:

(1 + x)3 = 1 + 2x + x2 + x + 2x2 + x3 = 1 + 3x + 3x2 + x3

General form:

(1 + x)n = C(n, n) + C(n, n - 1)x + C(n, n - 2)x2 + C(n, n - 3)x3 + ... + C(n, 1)xn-1 + C(n, 0)xn

We know from question 1 that C(n, n) = C(n, 0) = 1, so the first and last coefficients are 1.

The question didn't ask you to prove the binomial theorem, but you can prove it using induction on n. The proof is below (I got it from Wikipedia), and the proof of this case would be exactly the same, only letting y equal 1:
One way to prove the binomial theorem is with mathematical induction. When n = 0, we have

For the inductive step, assume the theorem holds when the exponent is m. Then for n = m + 1

by the inductive hypothesis
by multiplying through by a and b
by pulling out the k = 0 term
by letting j = k &#8722; 1
by pulling out the k = m + 1 term from the right hand side
by combining the sums
from Pascal's rule
by adding in the m + 1 terms.

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

The equation from part a is:

(1 + x)n = C(n, n) + C(n, n - 1)x + C(n, n - 2)x2 + C(n, n - 3)x3 + ... + C(n, 1)xn-1 + C(n, 0)xn

Because C(n, n) = C(n, 0), C(n, n - 1) = C(n, 1), etc., this can be written as the following to make it match the question:

(1 + x)n = C(n, 0) + C(n, 1)x + C(n, 2)x2 + C(n, 3)x3 + ... + C(n, n - 1)xn-1 + C(n, n)xn

Then, differentiating, we get:

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

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

From the previous problem, we have:

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

Let x = 1:

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

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

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

Again, start with n(1 + x)n-1 = C(n, 1) + 2C(n, 2)x + 3C(n, 3)x2 + ... + (n - 1)C(n, n - 1)xn-2 + nC(n, n)xn-1, but this time, let x = -1:

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

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

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)

This formula can't be right....look at n = 1:

2^(1 + 1)/(1 + 1) = C(1, 0) + (1/2)C(1, 1)
4/2 = 1 + ½
2 = 1 + ½

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)

Again, this formula can't be right either...in the last part of the formula, there's a (-1)^n, which means that there should be alternating + and - signs in the summation.