next up previous
Next: About this document ... Up: prob4 Previous: prob4

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. \begin{displaymath}\left\{\begin{array}{l}
t_0 = 0, \quad t_1 = 1,\\
t_n = 5t_{n-1} - 6t_{n-2}, \quad n \geq 2;

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

  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$:

    \begin{displaymath}(1+x)^r = \sum_{k \geq 0} {{r}\choose{k}} x^k,\end{displaymath}

    where the generalized binomial coefficient ${{r}\choose{k}}$ is defined as:

    \begin{displaymath}{{r}\choose{k}} = \frac{r(r-1)\cdots(r-k+1)}{k!}, \qquad
r \in {\mathbf R},\; k \in {\mathbf N}.\end{displaymath}

    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.

next up previous
Next: About this document ... Up: prob4 Previous: prob4
Pekka Orponen 2000-10-16