Deck 8: Advanced Counting Techniques

Question 1

determine whether the recurrence relation is a linear homogeneous recurrence relation with
constant coefficients.

Answer 1

Yes.

Question 2

A vending machine dispensing books of stamps accepts only $1 coins, $1 bills, and $2 bills. Let an denote the
number of ways of depositing n dollars in the vending machine, where the order in which the coins and bills
are deposited matters.
(a) Find a recurrence relation for an and give the necessary initial condition(s).
(b) Find an explicit formula for an by solving the recurrence relation in part (a).

Answer 2

Question 3

In questions solve the recurrence relation either by using the characteristic equation or by discovering
a pattern formed by the terms.

Answer 3

Question 4

In questions solve the recurrence relation either by using the characteristic equation or by discovering
a pattern formed by the terms.

Question 5

determine whether the recurrence relation is a linear homogeneous recurrence relation with
constant coefficients.

Question 6

determine whether the recurrence relation is a linear homogeneous recurrence relation with
constant coefficients.

Question 7

In questions solve the recurrence relation either by using the characteristic equation or by discovering
a pattern formed by the terms.

Question 8

In questions solve the recurrence relation either by using the characteristic equation or by discovering
a pattern formed by the terms.

Question 9

In questions solve the recurrence relation either by using the characteristic equation or by discovering
a pattern formed by the terms.

Question 10

In questions solve the recurrence relation either by using the characteristic equation or by discovering
a pattern formed by the terms.

Question 11

In questions , describe each sequence recursively. Include initial conditions and assume that the sequences
begin with a1.
= the number of bit strings of length n that contain a pair of consecutive 0's.

Question 12

In questions , describe each sequence recursively. Include initial conditions and assume that the sequences
begin with a1.
= the number of bit strings of length n that begin with 1.

Question 13

In questions solve the recurrence relation either by using the characteristic equation or by discovering
a pattern formed by the terms.

Question 14

determine whether the recurrence relation is a linear homogeneous recurrence relation with
constant coefficients.

Question 15

Find the solution of the recurrence relation

Question 16

determine whether the recurrence relation is a linear homogeneous recurrence relation with
constant coefficients.

Question 17

determine whether the recurrence relation is a linear homogeneous recurrence relation with
constant coefficients.

Question 18

In questions solve the recurrence relation either by using the characteristic equation or by discovering
a pattern formed by the terms.

Question 19

In questions , describe each sequence recursively. Include initial conditions and assume that the sequences
begin with a1.
= the number of bit strings of length n with an even number of 0's.

Question 20

In questions , describe each sequence recursively. Include initial conditions and assume that the sequences
begin with a1.
= the number of ways to go down an n-step staircase if you go down 1, 2, or 3 steps at a time.

Question 21

Question 22

Consider the recurrence relation (a) Write the associated homogeneous recurrence relation.
(b) Find the general solution to the associated homogeneous recurrence relation.
(c) Find a particular solution to the given recurrence relation.
(d) Write the general solution to the given recurrence relation.
(e) Find the particular solution to the given recurrence relation when

Question 23

Suppose Find https://d2lvgg3v3hfg70.cloudfront.net/TB34225555/.

Question 24

Assume that the characteristic equation for a homogeneous linear recurrence relation with constant coefficients Describe the form for the general solution to the recurrence relation.

Question 25

Consider the recurrence relation (a) Write the associated homogeneous recurrence relation.
(b) Find the general solution to the associated homogeneous recurrence relation.
(c) Find a particular solution to the given recurrence relation.
(d) Write the general solution to the given recurrence relation.
(e) Find the particular solution to the given recurrence relation when

Question 26

Suppose https://d2lvgg3v3hfg70.cloudfront.net/TB34225555/. Find

Question 27

Consider the recurrence relation (a) Write the associated homogeneous recurrence relation.
(b) Find the general solution to the associated homogeneous recurrence relation.
(c) Find a particular solution to the given recurrence relation.
(d) Write the general solution to the given recurrence relation.
(e) Find the particular solution to the given recurrence relation when a0 = 1.

Question 28

The Catalan numbers count the number of strings of n +’s and n −’s with the following property: as each string is read from left to right, the number of +’s encountered is always at least as large as the number of −’s . (a) Verify this by listing these strings of lengths 2,4 , and 6 and showing that there are C1, C2, and C3 of these, respectively.
(b) Explain how counting these strings is the same as counting the number of ways to correctly parenthesize strings of variables.

Question 29

What form does a particular solution of the linear nonhomogeneous recurrence relation + have when ?

Question 30

Suppose . Find https://d2lvgg3v3hfg70.cloudfront.net/TB34225555/.

Question 31

Assume that the characteristic equation for a homogeneous linear recurrence relation with constant coefficients

Question 32

What form does a particular solution of the linear nonhomogeneous recurrence relation + have when ?

Question 33

Consider the recurrence relation (a) Write the associated homogeneous recurrence relation.
(b) Find the general solution to the associated homogeneous recurrence relation.
(c) Find a particular solution to the given recurrence relation.
(d) Write the general solution to the given recurrence relation.
(e) Find the particular solution to the given recurrence relation when a0 = 1.

Question 34

What form does a particular solution of the linear nonhomogeneous recurrence relation have when

Question 35

Assume that the characteristic equation for a homogeneous linear recurrence relation with constant coefficients
is

Question 36

What form does a particular solution of the linear nonhomogeneous recurrence relation have when

Question 37

Thesolutionssolutionsto thetogivanen=recurrence−3an−1 +relation?18an−2 have the form Which of the following are

Question 38

Suppose Find https://d2lvgg3v3hfg70.cloudfront.net/TB34225555/.

Question 39

Suppose Find https://d2lvgg3v3hfg70.cloudfront.net/TB34225555/.

Question 40

Assume that the characteristic equation for a homogeneous linear recurrence relation with constant coefficients

Question 41

In questions write the first seven terms of the sequence determined by the generating function.
cos x.

Question 42

find the coefficient of in the power series of each of the function.

Question 43

In questions write the first seven terms of the sequence determined by the generating function.
5.

Question 44

In questions write the first seven terms of the sequence determined by the generating function.

Question 45

find the coefficient of in the power series of each of the function.

Question 46

In questions write the first seven terms of the sequence determined by the generating function.

Question 47

find the coefficient of in the power series of each of the function.

Question 48

find the coefficient of in the power series of each of the function.

Question 49

Use generating functions to solve

Question 50

find the coefficient of in the power series of each of the function.

Question 51

In questions write the first seven terms of the sequence determined by the generating function.

Question 52

find the coefficient of in the power series of each of the function.

Question 53

find the coefficient of in the power series of each of the function.

Question 54

In questions write the first seven terms of the sequence determined by the generating function.

Question 55

find the coefficient of in the power series of each of the function.

Question 56

In questions write the first seven terms of the sequence determined by the generating function.

Question 57

In questions write the first seven terms of the sequence determined by the generating function.

Question 58

In questions write the first seven terms of the sequence determined by the generating function.

Question 59

Use generating functions to solve

Question 60

In questions write the first seven terms of the sequence determined by the generating function.

Question 61

In questions find a closed form for the generating function for the sequence.
2, 3, 4, 5, 6, 7, . . . .

Question 62

find the coefficient of in the power series of each of the function.

Question 63

In questions find a closed form for the generating function for the sequence.

Question 64

In questions find a closed form for the generating function for the sequence.

Question 65

Set up a generating function and use it to find the number of ways in which eleven identical coins can be put
in three distinct envelopes if no envelope is empty.

Question 66

In questions find a closed form for the generating function for the sequence.
4, 8, 16, 32, 64, . . . .

Question 67

In questions find a closed form for the generating function for the sequence.

Question 68

Set up a generating function and use it to find the number of ways in which eleven identical coins can be put
in three distinct envelopes if each envelope has at least two coins in it.

Question 69

In questions find a closed form for the generating function for the sequence.
2, 0, 0, 2, 0, 0, 2, 0, 0, 2, . . . .

Question 70

Set up a generating function and use it to find the number of ways in which eleven identical coins can be put
in three distinct envelopes if each envelope has an even number of coins in it.

Question 71

find the coefficient of in the power series of each of the function.

Question 72

Set up a generating function and use it to find the number of ways in which eleven identical coins can be put
in three distinct envelopes if each envelope has most six coins in it.

Question 73

find the coefficient of in the power series of each of the function.

Question 74

In questions find a closed form for the generating function for the sequence.
0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, . . . .

Question 75

In questions find a closed form for the generating function for the sequence.

Question 76

In questions find a closed form for the generating function for the sequence.
1, 0, 1, 0, 1, 0, 1, 0, . . . .

Question 77

In questions find a closed form for the generating function for the sequence.

Question 78

In questions find a closed form for the generating function for the sequence.
2, 4, 6, 8, 10, 12, . . . .

Question 79

In questions find a closed form for the generating function for the sequence.

Question 80

In questions find a closed form for the generating function for the sequence.
0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1 . . . .