1) How would I prove that (n - 1 + 2 C 2) = n + (n C 2)
2) A cafeteria offers 17 types of pizza and 5 types of soda. Bob goes there everyday for lunch, always buying two slices of pizza and one soda. However, he never gets exactly the same thing on two consecutive days (that is, each time, the drink or at least one of the slices is different from what he had yesterday). In how many ways Bob can choose his lunch for the next 30 days if he just returned from a vacation (and so hasn’t been at the cafeteria for the past few days)?
3) Prove by induction the following identity (for n ≥ 1)
1 · 1! + 2 · 2! + 3 · 3! + . . . + n · n! = (n + 1)! − 1
------------------------------
1) I do not understand how I would approach this
2) would it be (17c2) x (5c1)?
3) I understand the basic step where you prove by making n = 1, the assume case where n = k, but for the induction case where n = k+1 I am stuck. I got the equation when n=k+1, (k+1!-1) + ((k+1) x (k+1)!) = ((k+1)+1)!)-1
#1
nC2 = n(n-1)/2
I think you have a typo.
#2
N = 17C2 * 5C1 is the total number of ways he can pick a meal. But, he has each of 30 days to make a different choice. That means there are NC30 different meals he can make. If the order makes a difference (same meals on different days), then there are NP30 different ways he can pick his meals.
#3
check n=1:
1*1! = (1+1)!-1
1 = 1 ok
For n=k, we assume
1*1! + ... + k*k! = (k+1)!-1
Now, what about n=k+1? Add the new term to both sides and then massage the right side till it fits the same form:
1*1! + k*k! + (k+1)*(k+1)! = (k+1)! - 1 + (k+1)*(k+1)!
= (k+1)! - 1 + k*(k+1)! + (k+1)!
= (1+k+1)*(k+1)! - 1
= (k+2)*(k+1)! - 1
= (k+2)! - 1
= ((k+1)+1)! - 1
This is just what you want by replacing n=k with n=k+1
QED