1. Let $c(n)$ denote the number of sequences of length $n$, 
   over $[0,1]$, wherein there are no two consecutive $0$'s.
   Write $c(n)=a(n)+b(n)$, where $a(n)$ are those which end in
   $0$, and $b(n)$ are those which end in $1$. 

   Note that: $b(n)=a(n-1)+b(n-1)$.
	      $a(n)=b(n-1)$. 

   Guess a method of solving such recurrence relations.

2. Let $f_k $ stand for the polynomial $x(x-1)\ldots
(x-k+1)/k! $. Let $g$ be a polynomial such that for all
integers $i$, $g(i)$ is an integer. Show that $g$ is an integral
linear combination of the polynomials $\{ f_k \}_{k=0,1,\ldots }
$. 

3. Let $B(n,k)=nCk x^k (1-x)^{n-k} $. Show that
$B(n,0),B(n,1),\ldots ,B(n,n)$ is a basis for the space of all
polynomials of degree $n$ or less.

4. Check that the expression of the ordinary monomial basis in
terms of the falling factorials give Sterling numbers of the Ist
kind.

5. Let $f,f' \in Surj(X,Y)$. We say that $f\tilda f'$ if there are
$\phi \in Bij(Y)$ and $\alpha \in Bij(X)$ such that $f'=\phi \circ
f \circ \alpha $. Show that $\tilda $ is an equivalence relation.
How many classes does $\tilda $ have?

6. Let $S$ be a square lying flat on a table. Let $F$ be the
collection of its four edges. List all the bijections on $F$ which
arise from rotations of the square, lying flat on the table. Do
the same, with reflections allowed as well.

7. Solve the recurrence relation $a(n)=4a(n-1)-4a(n-2)$ with the
initial conitions $a(0)=0$ and $a(1)=1$.