Next: About this document ...
Up: prob4
Previous: prob4
 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.)
 Solve the following recurrences using the
technique of characteristic polynomials:


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

and
?
 Find the generating functions for the following sequences:

;

;

;

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

, when
and ;

, for
;

,
.
 Find the sequences corresponding to the functions
and
. (Hint: Apply the results of
Problem 5.)
 Solve the recurrence of Problem 2(b) using the technique of
generating functions.
Next: About this document ...
Up: prob4
Previous: prob4
Pekka Orponen
20001016