Introduction to Discrete Mathematics, Fall 2000
Problem Set 4, 17-19 October

1. Walking up a staircase, one can ascend either 1 or 2 stairs at a time. Construct a recurrence relation that describes how many different ways there are to ascend an $n$-stair staircase. (Hint: Partition the ways to ascend an $n$-staircase according to whether the first step ascends 1 or 2 stairs.)

2. Solve the following recurrences using the technique of characteristic polynomials:
   1. 
      
      $$\left\{\begin{array}{l} t_0 = 0, \quad t_1 = 1,\\ t_n = 5t_{n-1} - 6t_{n-2}, \quad n \geq 2; \end{array}\right.$$
      
      

   2. 
      
      $$\left\{\begin{array}{l} a_0 = 1,\\ a_n = 2a_{n-1} + n, \quad n \geq 1. \end{array}\right.$$
      
      

3. Let $A(x)$ be the generating function for sequence $\langle a_k \rangle = \langle a_0, a_1, a_2, \dots \rangle$, and $c \in {\mathbf R}$, $p \in {\mathbf N}$ some constants. Find the sequences corresponding to the following functions:
   1. $G(x) = A(cx)$,
   2. $H(x) = A(x^p)$,
   3. $A_0(x) = \frac{1}{2}(A(x) + A(-x))$ and $A_1(x) = \frac{1}{2}(A(x) - A(-x))$?

4. Find the generating functions for the following sequences:
   1. $\langle 0,0,0,0,-6,6,-6,6,-6,\dots \rangle$;
   2. $\langle 1,0,1,0,1,0,\dots \rangle$;
   3. $\langle 1,2,1,4,1,8,\dots \rangle$;
   4. $\langle 1,1,0,1,1,0,1,1,0,\dots \rangle$.

5. Newton's (generalized) binomial theorem states that the following expansion holds for all values of $r \in {\mathbf R}$ and $\vert x\vert < 1$:
   
   $$(1+x)^r = \sum_{k \geq 0} {{r}\choose{k}} x^k,$$
   
   
   where the generalized binomial coefficient ${{r}\choose{k}}$ is defined as:
   
   $${{r}\choose{k}} = \frac{r(r-1)\cdots(r-k+1)}{k!}, \qquad r \in {\mathbf R},\; k \in {\mathbf N}.$$
   
   
   Additionally, one stipulates that ${{r}\choose{k}} = 0$ for $k < 0$. Establish the following properties of the generalized binomial coefficients:
   1. ${{n}\choose{k}} = 0$, when $n \in {\mathbf N}$ and $k > n$;
   2. ${{-n}\choose{k}} = (-1)^k{{n+k-1}\choose{k}}$, for $n \in {\mathbf N}$;
   3. ${{-1/2}\choose{k}} = \frac{(-1)^k}{2^{2k}}{{2k}\choose{k}}$, ${{1/2}\choose{k}} = \frac{(-1)^{k-1}}{2^{2k}(2k-1)}{{2k}\choose{k}}$.

6. Find the sequences corresponding to the functions $\frac{1}{(1-x)^2}$ and $\frac{x}{(1-x)^2}$. (Hint: Apply the results of Problem 5.)

7. Solve the recurrence of Problem 2(b) using the technique of generating functions.