Discrete Math Quiz: Counting With Recursion
12 questions · exam conditions
0:00
Counting With RecursionQuestion 1 of 12

The Tribonacci sequence satisfies t1=1t_1 = 1, t2=1t_2 = 1, t3=2t_3 = 2, and tn=tn−1+tn−2+tn−3t_n = t_{n-1} + t_{n-2} + t_{n-3} for n≥4n \geq 4. A modified version counts only those sequences where tnt_n is even. Let En=1E_n = 1 if tnt_n is even, 0 otherwise. What is ∑k=16Ek\sum_{k=1}^{6} E_k?

3
2
4
1
← Back to quizzes

Discrete Math Quiz

Discrete Math Quiz: Counting With Recursion

Practice Counting With Recursion in Discrete Math with focused quiz questions that help you check what you know, review explanations, and build confidence with test-style prompts.

What this quiz covers

This quiz focuses on Counting With Recursion, giving you a quick way to practice the rules, question types, and explanations that matter most for Discrete Math.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

All questions

Question 1

The Tribonacci sequence satisfies t1=1t_1 = 1, t2=1t_2 = 1, t3=2t_3 = 2, and tn=tn−1+tn−2+tn−3t_n = t_{n-1} + t_{n-2} + t_{n-3} for n≥4n \geq 4. A modified version counts only those sequences where tnt_n is even. Let En=1E_n = 1 if tnt_n is even, 0 otherwise. What is ∑k=16Ek\sum_{k=1}^{6} E_k?

  1. 3
  2. 2 (correct answer)
  3. 4
  4. 1
Explanation: First compute the Tribonacci sequence: t1=1t_1 = 1 (odd), t2=1t_2 = 1 (odd), t3=2t_3 = 2 (even), t4=1+1+2=4t_4 = 1+1+2 = 4 (even), t5=1+2+4=7t_5 = 1+2+4 = 7 (odd), t6=2+4+7=13t_6 = 2+4+7 = 13 (odd). So E1=0E_1 = 0, E2=0E_2 = 0, E3=1E_3 = 1, E4=1E_4 = 1, E5=0E_5 = 0, E6=0E_6 = 0. Therefore ∑k=16Ek=0+0+1+1+0+0=2\sum_{k=1}^{6} E_k = 0+0+1+1+0+0 = 2. Choice A miscounts parity, choice C counts all positive terms, choice D only counts one even term.

Question 2

A sequence sns_n counts the number of subsets of {1,2,…,n}\{1, 2, \ldots, n\} that contain no two consecutive integers. Given s0=1s_0 = 1 and s1=2s_1 = 2, and the recursion sn=sn−1+sn−2s_n = s_{n-1} + s_{n-2} for n≥2n \geq 2, what is s4s_4?

  1. 7
  2. 13
  3. 8 (correct answer)
  4. 5
Explanation: When you encounter problems about counting subsets with restrictions, think about how each new element affects your existing valid subsets. This is a classic application of recurrence relations in combinatorics. To find s4s_4, you need to understand why the recursion sn=sn−1+sn−2s_n = s_{n-1} + s_{n-2} works. When building valid subsets of {1,2,…,n}\{1, 2, \ldots, n\}, you have two cases: either include element nn or don't. If you don't include nn, you can use any valid subset of {1,2,…,n−1}\{1, 2, \ldots, n-1\}, giving you sn−1s_{n-1} possibilities. If you do include nn, you cannot include n−1n-1 (no consecutive integers), so you can only use valid subsets of {1,2,…,n−2}\{1, 2, \ldots, n-2\}, giving you sn−2s_{n-2} possibilities. Now calculate step by step:
  • s0=1s_0 = 1 (just the empty set)
  • s1=2s_1 = 2 (empty set and {1}\{1\})
  • s2=s1+s0=2+1=3s_2 = s_1 + s_0 = 2 + 1 = 3
  • s3=s2+s1=3+2=5s_3 = s_2 + s_1 = 3 + 2 = 5
  • s4=s3+s2=5+3=8s_4 = s_3 + s_2 = 5 + 3 = 8
The answer is C) 8. Option A) 7 might come from miscounting or making an arithmetic error. Option B) 13 could result from incorrectly applying the recursion or confusing this with a different counting problem. Option D) 5 is actually s3s_3, suggesting you stopped one step too early. Study tip: With recurrence relations, always write out several terms carefully. The Fibonacci-like pattern here appears frequently in combinatorics problems involving restrictions.

Question 3

The Catalan numbers CnC_n satisfy C0=1C_0 = 1 and Cn=∑i=0n−1CiCn−1−iC_n = \sum_{i=0}^{n-1} C_i C_{n-1-i} for n≥1n \geq 1. These count the number of ways to parenthesize a product of n+1n+1 factors. What is C3C_3?

  1. 3
  2. 4
  3. 6
  4. 5 (correct answer)
Explanation: Catalan numbers appear frequently in combinatorics problems involving recursive structures like parenthesizations, binary trees, and path counting. When you see the recurrence relation Cn=∑i=0n−1CiCn−1−iC_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}, think about how it breaks down a problem into smaller subproblems. To find C3C_3, you need to work systematically from the base case. Given C0=1C_0 = 1, let's calculate step by step: For C1C_1: C1=C0⋅C0=1⋅1=1C_1 = C_0 \cdot C_0 = 1 \cdot 1 = 1 For C2C_2: C2=C0⋅C1+C1⋅C0=1⋅1+1⋅1=2C_2 = C_0 \cdot C_1 + C_1 \cdot C_0 = 1 \cdot 1 + 1 \cdot 1 = 2 For C3C_3: C3=C0⋅C2+C1⋅C1+C2⋅C0=1⋅2+1⋅1+2⋅1=5C_3 = C_0 \cdot C_2 + C_1 \cdot C_1 + C_2 \cdot C_0 = 1 \cdot 2 + 1 \cdot 1 + 2 \cdot 1 = 5 You can verify this by listing all parenthesizations of four factors abcdabcd: (((ab)c)d)(((ab)c)d), ((ab)(cd))((ab)(cd)), ((a(bc))d)((a(bc))d), (a((bc)d))(a((bc)d)), and (a(b(cd)))(a(b(cd))) — exactly 5 ways. Choice A (3) likely comes from miscounting or confusing C3C_3 with C2+1C_2 + 1. Choice B (4) might result from forgetting one term in the sum or confusing this with the number of factors minus one. Choice C (6) could come from incorrectly applying factorial thinking or overcounting parenthesizations. When working with Catalan numbers, always build up from smaller values systematically. The recurrence relation captures how each parenthesization splits the expression at different points, making each term CiCn−1−iC_i C_{n-1-i} represent splitting after the (i+1)(i+1)-th factor.

Question 4

Let P(n,k)P(n, k) denote the number of ways to partition a set of nn elements into exactly kk non-empty subsets (Stirling numbers of the second kind). The recursion is P(n,k)=kP(n−1,k)+P(n−1,k−1)P(n, k) = kP(n-1, k) + P(n-1, k-1). Given P(3,2)=3P(3, 2) = 3, what is P(4,2)P(4, 2)?

  1. 8
  2. 6
  3. 7 (correct answer)
  4. 9
Explanation: When you encounter Stirling numbers of the second kind, you're dealing with partitions of sets into non-empty subsets. The recursion P(n,k)=kP(n−1,k)+P(n−1,k−1)P(n, k) = kP(n-1, k) + P(n-1, k-1) captures two ways to place the nth element: either add it to one of the existing k partitions, or create a new partition containing just that element. To find P(4,2)P(4, 2), apply the recursion: P(4,2)=2P(3,2)+P(3,1)P(4, 2) = 2P(3, 2) + P(3, 1). You're given that P(3,2)=3P(3, 2) = 3. For P(3,1)P(3, 1), there's only one way to put all 3 elements into 1 subset, so P(3,1)=1P(3, 1) = 1. Therefore: P(4,2)=2(3)+1=7P(4, 2) = 2(3) + 1 = 7. Looking at the wrong answers: Choice A (8) likely comes from incorrectly calculating 3×3−1=83 \times 3 - 1 = 8, misremembering the recursion formula. Choice B (6) results from forgetting the P(3,1)P(3, 1) term entirely and computing 2×3=62 \times 3 = 6. Choice D (9) might arise from incorrectly using 3×3=93 \times 3 = 9, perhaps confusing this with a different combinatorial formula. The correct answer is C (7). Study tip: Always write out the recursion formula explicitly and identify all needed base cases before substituting values. Stirling number problems often involve multiple recursive steps, so organize your work clearly to avoid arithmetic errors and ensure you're applying the correct formula.

Question 5

Let cnc_n count the number of ways to arrange nn distinct books on a shelf such that no book is in its original position (derangements). Given the recursion cn=(n−1)(cn−1+cn−2)c_n = (n-1)(c_{n-1} + c_{n-2}) and c1=0c_1 = 0, c2=1c_2 = 1, what is c4c_4?

  1. 6
  2. 8
  3. 11
  4. 9 (correct answer)
Explanation: When you encounter a recursion problem about derangements, you're working with a fundamental counting principle where each term depends on previous terms. The key is to apply the given formula systematically, using the provided base cases. Given the recursion cn=(n−1)(cn−1+cn−2)c_n = (n-1)(c_{n-1} + c_{n-2}) with c1=0c_1 = 0 and c2=1c_2 = 1, you need to build up to c4c_4 step by step. First, find c3c_3: c3=(3−1)(c2+c1)=2(1+0)=2c_3 = (3-1)(c_2 + c_1) = 2(1 + 0) = 2 Then calculate c4c_4: c4=(4−1)(c3+c2)=3(2+1)=3×3=9c_4 = (4-1)(c_3 + c_2) = 3(2 + 1) = 3 \times 3 = 9 Therefore, c4=9c_4 = 9, which is answer choice D. Looking at the wrong answers: Choice A (6) likely comes from incorrectly computing c3=3c_3 = 3 and then getting c4=3(1+2)=9c_4 = 3(1 + 2) = 9, but making an arithmetic error to reach 6. Choice B (8) might result from forgetting the factor of (n−1)(n-1) and calculating c4=c3+c2+c1+c0c_4 = c_3 + c_2 + c_1 + c_0 with some assumed value. Choice C (11) could come from misapplying the recursion formula, perhaps adding the factor incorrectly as c4=(c3+c2)+(4−1)=3+8=11c_4 = (c_3 + c_2) + (4-1) = 3 + 8 = 11. When solving recursion problems, always work methodically from the base cases upward, double-check your arithmetic at each step, and make sure you're applying the exact formula given—don't try to shortcut or modify the recursion relation.

Question 6

Let w(n)w(n) count the number of ways to write nn as an ordered sum of positive integers where each term is either 1 or a prime number. For example, w(4)=4w(4) = 4 since 4=1+1+1+1=1+1+2=1+2+1=2+1+14 = 1+1+1+1 = 1+1+2 = 1+2+1 = 2+1+1. What is w(7)w(7)?

  1. 16
  2. 18
  3. 20 (correct answer)
  4. 22
Explanation: We use the recurrence w(n)=w(n−1)+∑p≤n,p primew(n−p)w(n) = w(n-1) + \sum_{p \leq n, p \text{ prime}} w(n-p). Computing step by step: w(1)=1w(1) = 1, w(2)=2w(2) = 2, w(3)=3w(3) = 3, w(4)=4w(4) = 4, w(5)=6w(5) = 6, w(6)=9w(6) = 9. Then w(7)=w(6)+w(5)+w(4)+w(2)=9+6+4+1=20w(7) = w(6) + w(5) + w(4) + w(2) = 9 + 6 + 4 + 1 = 20 (using primes 2, 3, 5). Choice A undercounts by missing some compositions. Choice B uses an incorrect set of allowed terms. Choice D overcounts by including composite numbers.

Question 7

Consider sequences of length nn using the symbols A, B, C where no two consecutive symbols are the same, and the sequence cannot start with C. Let g(n)g(n) denote the number of such sequences. If g(1)=2g(1) = 2 and g(2)=4g(2) = 4, what is g(5)g(5)?

  1. 32
  2. 36 (correct answer)
  3. 40
  4. 44
Explanation: Let ana_n be sequences ending in A, bnb_n ending in B, cnc_n ending in C. Then an=bn−1+cn−1a_n = b_{n-1} + c_{n-1}, bn=an−1+cn−1b_n = a_{n-1} + c_{n-1}, cn=an−1+bn−1c_n = a_{n-1} + b_{n-1}, with a1=1,b1=1,c1=0a_1 = 1, b_1 = 1, c_1 = 0. Computing: g(3)=8g(3) = 8, g(4)=20g(4) = 20, g(5)=36g(5) = 36. Choice A ignores the restriction on starting with C. Choice C uses an incorrect recurrence relation. Choice D counts sequences that can start with any symbol.

Question 8

Let ana_n be the number of ways to tile a 2×n2 \times n rectangle using 1×21 \times 2 dominoes (which can be placed horizontally or vertically). Given that a1=1a_1 = 1 and a2=2a_2 = 2, what is a6a_6?

  1. 8
  2. 13 (correct answer)
  3. 21
  4. 34
Explanation: To tile a 2×n2 \times n rectangle, we can either place a vertical domino in the last column (leaving a 2×(n−1)2 \times (n-1) rectangle) or place two horizontal dominoes in the last two columns (leaving a 2×(n−2)2 \times (n-2) rectangle). This gives us the recurrence an=an−1+an−2a_n = a_{n-1} + a_{n-2}. Starting with a1=1a_1 = 1 and a2=2a_2 = 2, we get a3=3a_3 = 3, a4=5a_4 = 5, a5=8a_5 = 8, and a6=13a_6 = 13. Choice A gives a5a_5. Choice C is a7a_7. Choice D is a8a_8.

Question 9

A sequence bnb_n counts the number of binary strings of length nn that do not contain two consecutive 1's. Given that b0=1b_0 = 1, b1=2b_1 = 2, and b2=3b_2 = 3, what is b5b_5?

  1. 11
  2. 13 (correct answer)
  3. 16
  4. 21
Explanation: The recursion is bn=bn−1+bn−2b_n = b_{n-1} + b_{n-2} for n≥2n \geq 2. A valid string of length nn either ends in 0 (any valid string of length n−1n-1 followed by 0) or ends in 01 (any valid string of length n−2n-2 followed by 01). Computing: b3=2+3=5b_3 = 2 + 3 = 5, b4=3+5=8b_4 = 3 + 5 = 8, b5=5+8=13b_5 = 5 + 8 = 13. Choice A (11) incorrectly uses b4+b3b_4 + b_3, choice C (16) doubles b4b_4, and choice D (21) is b8b_8.

Question 10

Let f(n)f(n) be the number of ways to climb nn stairs if you can take 1, 2, or 3 steps at a time. If f(1)=1f(1) = 1, f(2)=2f(2) = 2, and f(3)=4f(3) = 4, what is f(6)f(6)?

  1. 24 (correct answer)
  2. 13
  3. 7
  4. 44
Explanation: The recursion is f(n)=f(n−1)+f(n−2)+f(n−3)f(n) = f(n-1) + f(n-2) + f(n-3) for n≥4n \geq 4. To reach stair nn, you can come from stair n−1n-1 (1 step), n−2n-2 (2 steps), or n−3n-3 (3 steps). Computing: f(4)=1+2+4=7f(4) = 1 + 2 + 4 = 7, f(5)=2+4+7=13f(5) = 2 + 4 + 7 = 13, f(6)=4+7+13=24f(6) = 4 + 7 + 13 = 24. Choice B (13) is f(5)f(5), choice C (7) is f(4)f(4), and choice D (44) is f(7)f(7).

Question 11

Let ana_n represent the number of ways to tile a 2×n2 \times n rectangle using 1×21 \times 2 dominoes. If a1=1a_1 = 1 and a2=2a_2 = 2, what is the value of a6a_6?

  1. 13 (correct answer)
  2. 21
  3. 8
  4. 34
Explanation: The recursive relation is an=an−1+an−2a_n = a_{n-1} + a_{n-2} for n≥3n \geq 3. To tile a 2×n2 \times n rectangle, we can either place a vertical domino at the end (leaving a 2×(n−1)2 \times (n-1) rectangle) or place two horizontal dominoes at the end (leaving a 2×(n−2)2 \times (n-2) rectangle). Computing: a3=1+2=3a_3 = 1 + 2 = 3, a4=2+3=5a_4 = 2 + 3 = 5, a5=3+5=8a_5 = 3 + 5 = 8, a6=5+8=13a_6 = 5 + 8 = 13. Choice B (21) is a8a_8, choice C (8) is a5a_5, and choice D (34) is a9a_9.

Question 12

Let f(n)f(n) be the number of binary strings of length nn that contain no three consecutive 1's. If f(1)=2f(1) = 2, f(2)=4f(2) = 4, and f(3)=7f(3) = 7, what is f(6)f(6)?

  1. 44 (correct answer)
  2. 49
  3. 51
  4. 56
Explanation: A valid string of length nn can end in 0 (giving f(n−1)f(n-1) possibilities), end in 01 (giving f(n−2)f(n-2) possibilities), or end in 011 (giving f(n−3)f(n-3) possibilities). This yields f(n)=f(n−1)+f(n−2)+f(n−3)f(n) = f(n-1) + f(n-2) + f(n-3). Computing: f(4)=7+4+2=13f(4) = 7 + 4 + 2 = 13, f(5)=13+7+4=24f(5) = 13 + 7 + 4 = 24, f(6)=24+13+7=44f(6) = 24 + 13 + 7 = 44. Choice B miscounts by including some invalid strings. Choice C uses an incorrect recurrence. Choice D counts all binary strings without the restriction.