\centerline{Quiz 4 Math 302}
 \parindent=20 pt
\parskip=10 pt
\nopagenumbers
Work any two of the first three problems below.

\item{1.} Define $T_n$ by the starting value $T_0:=1$ and the rule $T_n=2T_{n-1}+2^n-1$ for $n\ge 1$. Thus $T_1=3$ and $T_2=9$. 
\itemitem{(a)} Find $T_k$ for $k=3,4,5$ and 6.
\itemitem{(b)} Find $(T_k-1)/k$ for $k=1,2,3,4,5$ and 6.
\itemitem{(c)} Based on the evidence from (a) and (b), conjecture a formula for $T_n$.
\itemitem{(d)} Prove that formula. 

\item{2.} Let $(F_n)$ denote the Fibonacci sequence, so that $F_0=0,F_1=1,F_2=1,F_3=2$ and for $n\ge 2$, $F_n=F_{n-1}+F_{n-2}$. 
\itemitem{(a)} Verify that for $n=6$ and 7, $2F_n>3F_{n-1}$ while $3F_n<5F_{n-1}$. 
\itemitem{(b)} Prove that for all $n\ge 6$,  $2F_n>3F_{n-1}$ and  $3F_n<5F_{n-1}$. 

\item{3.} Let  $A=\{1,2,3\}$ and $B=\{1,2\}$, for all parts of this problem.
\itemitem{(a)}write out $A\times B$ in full. 
\itemitem{(b)} Give an example of a relation from $A$ to $B$ which is not a function. 
\itemitem{(c)} List all functions from $A$ to $B$, or say how many relations there are from $A$ to $B$ [your choice of task.]

\item{4.} If you are finished and would like to go for extra credit (up to 25 points), 
\itemitem{(a)} State the binomial theorem in full detail.
\itemitem{(b)} Let $$f_n(x):=\sum_{k=0}^n\pmatrix{n\cr k\cr}x^k.$$Find a simpler expression for $f_n(x)$  which involves no summation sign.
\itemitem{(c)} Prove by differentiating both sides of the result of part (b) twice, and then setting $x=1$, that $$\sum_{k=0}^n(k^2-k)\pmatrix{n\cr k\cr}=n(n-1)2^{n-2}$$for $n\ge 2$. 
\itemitem{(d)} Prove that  $$\sum_{k=0}^nk^2\pmatrix{n\cr k\cr}=n(n+1)2^{n-2}$$for $n\ge 2$. 
\bye