University Discrete Mathematics — Recurrence Relations and Advanced Counting Worksheet

All 9 questions

Each question targets one named concept from the sheet. Read them here, or print the PDF — it has working space under each one.

1. Q1Modelling a Counting Problem with a Recurrence

   A door code is a string of $n$ digits taken from $1,2,\dots ,9$ (no zero), and a code is valid if no two consecutive digits are both even. Let $c_n$ be the number of valid codes of length $n$.

   1. Find $c_1$ and $c_2$.
   2. By considering the last digit of a valid code, show that $c_n=5c_{n-1}+20c_{n-2}$ for $n\ge 3$.
   3. Compute $c_4$.
2. Q2Modelling a Counting Problem with a Recurrence

   A librarian places $n$ different books on three different shelves. On each shelf the books stand in a row from left to right, and a shelf may be left empty. Two placements are the same only when every shelf holds the same books in the same order. Let $s_n$ be the number of placements.

   1. Find $s_1$ and $s_2$.
   2. Place the books in the order $1,2,\dots ,n$. By counting the positions available to the last book once the first $n-1$ are on the shelves, find a recurrence expressing $s_n$ in terms of $s_{n-1}$ for $n\ge 2$, and justify it.
   3. Compute $s_5$, and write $s_n$ in terms of factorials.
3. Q3Linear Homogeneous Recurrences with Distinct Roots

   Solve the recurrence $a_n=a_{n-1}+6a_{n-2}$ for $n\ge 2$, with $a_0=3$ and $a_1=4$. Check your formula against $a_2$ computed from the recurrence.

4. Q4Linear Homogeneous Recurrences with Distinct Roots

   A sequence satisfies $a_{n+1}=2a_n+8a_{n-1}$ for $n\ge 2$, with $a_1=4$ and $a_2=4$. Find a closed form for $a_n$, $n\ge 1$, and check it against $a_3$.

5. Q5Linear Homogeneous Recurrences with a Repeated Root

   Solve $a_n=6a_{n-1}-9a_{n-2}$ for $n\ge 2$, with $a_0=2$ and $a_1=3$, and check your formula against $a_2$ and $a_3$ computed from the recurrence.

6. Q6The Inclusion-Exclusion Principle

   How many integers from $1$ to $1000$ inclusive are divisible by none of $4$, $6$ and $15$?

7. Q7The Inclusion-Exclusion Principle

   A food bank has $14$ identical one-hour shifts to hand out among $4$ volunteers, and no volunteer may take more than $5$ shifts (a volunteer may take none). In how many ways can the shifts be handed out? You may use the fact that the equation $x_1+x_2+\dots +x_k=m$ has ${\displaystyle \left(\genfrac{}{}{0ex}{}{m+k-1}{k-1}\right)}$ solutions in nonnegative integers.

8. Q8Counting Derangements and Onto Functions
   1. Five distinct manuscripts are sent to three editors, every manuscript going to exactly one editor, and every editor must receive at least one. In other words, count the surjective (onto) functions from a $5$-element set to a $3$-element set: the functions that hit every element of the target.
   2. Five reviewers each wrote a report, and the reports are collected and handed back so that each reviewer checks one report — never their own. In how many ways can this be done?
9. Q9Synthesis — drawing on several topics in this unit

   A signal occupies $n$ consecutive time slots and is built as a sequence of pulses: a short pulse fills one slot and can be sent at any of $2$ frequencies; a long pulse fills two slots and can be sent at any of $3$ frequencies. Let $a_n$ be the number of different signals filling exactly $n$ slots, with $a_0=1$ (the empty signal).

   1. Explain why $a_n=2a_{n-1}+3a_{n-2}$ for $n\ge 2$, and give $a_1$.
   2. Solve the recurrence, and check your formula against $a_4$.

The 6 challenge problems for this topic are a separate, paid sheet and are not reproduced here.

How to do every concept on this sheet

This is the part worksheet sites usually leave out. Below is the actual reasoning behind each group of questions — not a full solution set, the decisions that get you to one. Read it before you start, or after you get stuck.

Modelling a counting problem with a recurrence

A recurrence is an argument, not a formula you spot. The argument always has the same shape: take an arbitrary object of size n, look at one feature of it — usually the last choice made — split into cases according to that feature, and show that each case is counted by a smaller member of the same sequence. Q1 and Q2 both name the feature to condition on, so the work is in the justification, not in the guessing.

Q1 is the version where the last choice constrains the one before it. The condition forbids a pattern in two consecutive positions, so knowing the last digit alone is not enough to know how many valid codes end that way — you have to know whether the last digit is of the kind that restricts its neighbour. That is exactly why a term two steps back appears in the recurrence the question asks you to establish, and why the sequence needs two starting values. Part (a) asks for those two by direct count; part (c) then asks you to run the recurrence forward, which is also your check that parts (a) and (b) agree with each other.

Q2 is the version with a one-term recurrence, and it is worth seeing why. The question fixes an order on the items being placed and asks you to count the positions available to the last one once the others are already on the shelves. Because the shelves are distinguishable and each shelf holds its items in a left-to-right row, a new item can go at either end of a shelf or in any gap between two items already on it — so the number of positions available depends only on how many items are already placed, not on how they happen to be spread out. That independence is the whole content of the justification part (b) asks for. Part (c) then asks for sₙ in terms of factorials: unfold the recurrence, write the product of the successive multipliers, and recognise that product as a ratio of factorials.

Linear homogeneous recurrences with distinct roots

A recurrence of the form aₙ = p·aₙ₋₁ + q·aₙ₋₂ is linear (each earlier term appears to the first power), homogeneous (no term free of the sequence) and has constant coefficients. For these, and only for these, there is a method. Try a solution of the form aₙ = rⁿ, substitute, and divide by the lowest power of r that appears: what is left is a quadratic in r.

Q3 is the method in its plainest form: the two initial values sit at the first two indices, the characteristic equation factors over the integers, and the question names the term you should check against. Do that check — it is the only step that catches a sign error in a root or an arithmetic slip in the system.

Q4 changes two things at once, deliberately. The recurrence is written with its highest term as aₙ₊₁ rather than aₙ, and the two given values sit at indices 1 and 2 rather than 0 and 1. The shift is cosmetic — rewrite the relation with the index lowered by one so that it matches the standard form before you read off the coefficients — but the initial values are not. Substitute n = 1 and n = 2 into the general solution, not n = 0 and n = 1, or the constants will solve a system that belongs to a different sequence. The closed form is wanted for n ≥ 1, and the check is against a term you compute from the recurrence itself.

The repeated root, and why n appears

When the characteristic equation has a discriminant of zero it has one root r, used twice, and c₁·rⁿ + c₂·rⁿ collapses into a single constant times rⁿ — one constant is not enough to meet two initial conditions. The second independent solution is n·rⁿ, so the general solution carries a factor of n on one term.

Q5 is that case. Recognise it before you start writing constants: a perfect-square quadratic is the signal, and factoring it is faster than the discriminant. Then substitute the two given indices, solve for c₁ and c₂, and check against both of the terms the question names — two checks, because a repeated-root formula that is wrong in the n-term can still agree at one index by accident.

The inclusion-exclusion principle

Adding the sizes of overlapping sets counts each shared element more than once. The inclusion-exclusion principle is the bookkeeping that repairs it: add the sets, subtract every pairwise overlap, add back every triple overlap, and so on with alternating signs.

Q6 asks for a count of the integers in a range divisible by none of three given numbers, which is the complement of a union. So there are two decisions before any arithmetic: name the three sets precisely, and decide to count the union and subtract from the size of the whole range rather than trying to describe "none of them" directly.

Q7 is inclusion-exclusion used the other way round: not on three sets you are given, but on conditions you construct. The question supplies the formula for the number of nonnegative integer solutions of x₁ + x₂ + … + xₖ = m, which counts the distributions with no upper limit at all. The cap each volunteer faces is then handled by subtracting the distributions that violate it.

By symmetry every Aᵢ has the same size and every pairwise intersection has the same size, so the work is one count per level multiplied by C(k, 1), C(k, 2) and so on. Say that the sets are symmetric rather than leaving the multiplier unexplained.

Derangements and onto functions

Q8 is the pair of classical applications, one in each part, and both are inclusion-exclusion over the things that are missed or fixed.

Part (a) counts the onto (surjective) functions from a set of n elements to a set of m elements. The functions that are not onto are those missing at least one target value, and the ones missing a chosen set of k targets are just the functions into the remaining m − k values — of which there are (m − k)ⁿ. Inclusion-exclusion over which targets are missed gives the standard alternating sum.

Part (b) counts derangements — the arrangements in which nothing stays where it started. Here the bad sets are the arrangements that fix a chosen element, and fixing a chosen set of k elements leaves the other n − k free, so that set has (n − k)! members. The same alternating sum, divided through by n!, gives the familiar series form.

The synthesis question

Q9 puts the two halves in one problem. Part (a) is the modelling of Q1: a sequence counting signals built from pieces of two different lengths, where conditioning on the last piece splits into a case that consumes one slot and a case that consumes two, each weighted by the number of frequencies that piece can carry. Justify the split and say why the cases are disjoint, then find the missing starting value by listing the signals that fill a single slot — the empty signal is given for you, and it is given precisely so that the recurrence works from n = 2 without a separate argument.

Part (b) is Q3 and Q4: standard form, characteristic equation, general solution, the two starting values, and then the check the question names against a term computed directly from the recurrence. If the check fails, it is almost always part (a) that is wrong rather than the algebra — re-run the recurrence by hand from the starting values and compare with a direct count of the short signals.

Preview all 5 pages

Click any page to open the full PDF.

Getting the most out of it

Count small cases before you model anything

Write out the objects of size 1 and 2 in full and count them, even when the question does not ask. Those numbers are both your initial conditions and the test data for every claim you make afterwards. A recurrence that disagrees with a hand count at n = 3 is wrong, and finding that out early costs nothing.

Write the case split in words before the equation

"Every valid object of size n either ends in this or ends in that, and never both" is the sentence the marks are for. The equation follows from it in one line. Written the other way round — equation first, justification bolted on — the justification tends to describe the equation rather than prove it.

Normalise the indices, every time

Before solving, rewrite the recurrence so the highest term is aₙ and the initial conditions are written as substitutions into the general solution rather than as terms of the sequence. Most wrong closed forms on this topic are right formulas with constants fitted at the wrong indices.

Name every set, in full, before writing an inclusion-exclusion line

Write "A is the set of … in the range" for each set, then the union formula, then the substitutions. When the sets are defined by divisibility, note the lcm of each pair on the same line so that the intersection sizes cannot be taken from products by reflex.

Verify the closed form against the recurrence

A closed form is a claim about every term, so testing it at one new index is cheap and surprisingly effective. Compute a term from the recurrence, compute it from the formula, and write both down. Several of these questions ask for exactly that check; do it on the ones that do not, too.

Common questions