## 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 -stair staircase. (Hint: Partition the ways to ascend an -staircase according to whether the first step ascends 1 or 2 stairs.)

2. Solve the following recurrences using the technique of characteristic polynomials:

3. Let be the generating function for sequence , and , some constants. Find the sequences corresponding to the following functions:
1. ,
2. ,
3. and ?

4. Find the generating functions for the following sequences:
1. ;
2. ;
3. ;
4. .

5. Newton's (generalized) binomial theorem states that the following expansion holds for all values of and :

where the generalized binomial coefficient is defined as:

Additionally, one stipulates that for . Establish the following properties of the generalized binomial coefficients:
1. , when and ;
2. , for ;
3. , .

6. Find the sequences corresponding to the functions and . (Hint: Apply the results of Problem 5.)

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