Deck 8: A: Advanced Counting Techniques

Question 1

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

Answer 1

No

Question 2

Find the solution of the recurrence relation an = 3an−1 with a0 = 2.

Answer 2

Question 3

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

Answer 3

Yes

Question 4

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

Question 5

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

Question 6

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

Question 7

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

Question 8

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

Question 9

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

Question 10

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

Question 11

A vending machine dispensing books of stamps accepts only $1 coins, $1 bills, and $2 bills. Let an denote

Question 12

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

Question 13

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

Question 14

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

Question 15

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

Question 16

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

Question 17

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

Question 18

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

Question 19

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

Question 20

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

Question 21

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

Question 22

Assume that the characteristic equation for a homogeneous linear recurrence relation with constant coeffi- cients is Describe the form for the general solution to the recurrence relation.

Question 23

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 24

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

Question 25

The solutions to have the form Which of the following are solutions to the given recurrence relation?

Question 26

Suppose . Find .

Question 27

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

Question 28

The Catalan numbers C_n 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 C₁ , C₂ , and C₃ 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

Suppose . Find .

Question 30

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

Question 31

Assume that the characteristic equation for a homogeneous linear recurrence relation with constant coeffi- cients is Describe the form for the general solution to the recurrence relation.

Question 32

Suppose . Find .

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

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.

Question 35

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 36

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

Question 37

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

Question 38

Assume that the characteristic equation for a homogeneous linear recurrence relation with constant coeffi- cients is Describe the form for the general solution to the recurrence relation.

Question 39

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

Question 40

Assume that the characteristic equation for a homogeneous linear recurrence relation with constant coeffi- cients is Describe the form for the general solution to the recurrence relation.

Question 41

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

Question 42

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

Question 43

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

Question 44

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

Question 45

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

Question 46

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

Question 47

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

Question 48

Use generating functions to solve

Question 49

Use generating functions to solve

Question 50

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

Question 51

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

Question 52

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

Question 53

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

Question 54

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

Question 55

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

Question 56

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

Question 57

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

Question 58

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

Question 59

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

Question 60

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

Question 61

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

Question 62

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

Question 63

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 64

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

Question 65

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

Question 66

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

Question 67

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 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 but no more than five coins in it.

Question 69

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 70

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

Question 71

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 72

find a closed form for the generating function for the sequence.
1, −1, 12!, −3!1 , 14!, − 15!, . . .

Question 73

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

Question 74

find a closed form for the generating function for the sequence.
1, −1, 1, −1, 1, −1, 1, −1, . . .

Question 75

find a closed form for the generating function for the sequence.
1, 12!, 14!, 16!, 18! . . .

Question 76

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

Question 77

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

Question 78

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

Question 79

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 80

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