Grades
distribution
90-100 A (7)
65-89 B (7)
50-64 C (5)
35-49 D (2)
0-34 F (0)
median = 80
1. If a_n=A^n we get A^2=-3A+4, so A=1 or A=-4. Thus a_n =c1*(-4)^n+c2*1^n. Using the intial conditions we get c1=-1/5, c2=6/5.
2. There are (n choose k) total number of k-subsets. How many of them have largest element j? (j-1 choose k-1) choices for the smaller elements. The max j may be anything from k to n.
3. There are (9+4 choose 4)= 715 ways to dstribute the 9 balls.
(a) If Felix gets at least 2 balls, give him 2, and distribute the remaining 7 balls in (11 choose 4)= 330 ways. This is less than 50%, so FALSE.
(b) If Fanny gets 0 balls there are (12 choose 3)=220 ways, greater than 25%, TRUE.
(c) This is (x/(1-x))^5.
4.(a) Let A_n be the number of such compositions. Then A_1=1, A_2=2, and looking at the last entry A_n=A_{n-1}+A_{n-2}. So A_n=F_{n+1}, Fibonacci number.
(b) We know F_n grows like c1*\gamma^n, \gamma=(1+\sqrt(5))/2=1.62..., while the number of subsets of n is 2^n so the number of subsets is larger for large. But this is always true, as F_n=F_{n-1}+F_{n-2} while the subsets satisfy S_n=S_{n_1}+S_{n-1}.
5. The total number of k-subsets which do not include first m elements is (n-m choose k). Lets do this by PIE, letting A_i be the set of all k-subsets which do include i, for i between 1 and m. The size of an s-fold intersection is (n-s choose k-s), since s elements are forced to be in the set. There are (m choose s) such s-fold intersections, so we are done.
6. Proof #1: Let's count set partitions of n into n-3 blocks.
If we have n-3 blocks, we have only 3 extra elements not in singleton blocks.
CASE 1: 1 block of size 4: (n choose 4) choices.
CASE 2: 1 block of size 3, 1 block of size 2: (n choose 3)*(n-3 choose 2) choices.
CASE 3: 3 blocks of size 2: (n choose 6)*3*5.
So S(n,n-3) is the sum of these three terms, which are respectively polynomials of degree 4.5, and 6. So the sum is a polynomial of degree 6.
Proof #2: Note that S(n,n-1)=(n choose 2) is a polynomials of degree 2 in n.
Then S(n,n-2)=S(n-1,n-3)+(n-2)*S(n-1,n-2). If A_n=S(n,n-2) this is
A_n-A_{n-1}=(n-2)*(n-1 choose 2),
or the first difference is a polynomial in n of degree 3. So A_n is a polynomial in n
of degree 4.
Now put B_n=S(n,n-3) and get
S(n,n-3)=S(n-1,n-4)+(n-3)*S(n-1,n-3).
B_n-B_{n-1}=(n-3)*S(n-1,n-3), polynomials in n if degree 5.
So as before B_n is a polynomial in n of degree 6.