Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit


Math 184

Winter 2022

Homework 4

 

Explanations should be given for your solutions. Use complete sentences.

(1) If  find a closed formula for an .

(2) Define a sequence by

(a) Express  as a rational function in x.

(b) Find a closed formula for an .

(3) Let S(n, k) be the Stirling number of the second kind.  For each k 2 1, define the ordinary generating function

(a) For k 2 2, translate the identity from lecture

into an identity involving 5k (x) and 5k -1 (x).

(b) Use the identity you found in (a) and induction on k to show that for all k 2 1:

(4) You want to build a stack of blocks that is n feet high.  You have 3 different kinds (unlimited of each):  green blocks are 1 foot high, while red and blue blocks are 2 feet high.  Blocks of the same color are considered indistinguishable.  Let an  be the number of ways to stack these blocks.

Find a linear recurrence relation and initial conditions satisfied by an .

(5) You are designing a race that takes place over n blocks in a city. It will consist of 3 portions: running, followed by biking, and ending with another running portion. The end of a portion should match up with the end of a block. The first running portion needs to designate 3 blocks to have a first aid tent, and the biking portion needs to designate 4 blocks to have a first aid tent. The second running portion doesn’t need anything, but must have positive length. Use generating functions to find a formula for the number of ways to design a race under these conditions.

(6) Let n be a positive integer and let an be the number of different ways to pay n dollars using only 1, 2, 5, 10, 20 dollar bills in which at most three 20 dollar bills are used. Express  as a rational function.