Discrete Math Quiz: Solving Recurrences By Iteration
5 questions · exam conditions
0:00
Solving Recurrences By IterationQuestion 1 of 5

The sequence jnj_n satisfies jn=4jn−1−4jn−2j_n = 4j_{n-1} - 4j_{n-2} with j0=0j_0 = 0 and j1=2j_1 = 2. Through iterative expansion, which of the following best describes the growth pattern of jnj_n for large nn?

Grows like n⋅2nn \cdot 2^n due to repeated root structure
Grows like 2n2^n with simple exponential behavior
Grows like 4n4^n due to the leading coefficient
Oscillates with bounded amplitude due to complex roots
← Back to quizzes

Discrete Math Quiz

Discrete Math Quiz: Solving Recurrences By Iteration

Practice Solving Recurrences By Iteration 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 Solving Recurrences By Iteration, 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 sequence jnj_n satisfies jn=4jn−1−4jn−2j_n = 4j_{n-1} - 4j_{n-2} with j0=0j_0 = 0 and j1=2j_1 = 2. Through iterative expansion, which of the following best describes the growth pattern of jnj_n for large nn?

  1. Grows like n⋅2nn \cdot 2^n due to repeated root structure (correct answer)
  2. Grows like 2n2^n with simple exponential behavior
  3. Grows like 4n4^n due to the leading coefficient
  4. Oscillates with bounded amplitude due to complex roots
Explanation: The characteristic equation is r2−4r+4=0r^2 - 4r + 4 = 0, which factors as (r−2)2=0(r-2)^2 = 0, giving a repeated root r=2r = 2. With repeated roots, the general solution is jn=(A+Bn)⋅2nj_n = (A + Bn) \cdot 2^n. Using initial conditions: j0=A=0j_0 = A = 0 and j1=(0+B)⋅2=2B=2j_1 = (0 + B) \cdot 2 = 2B = 2, so B=1B = 1. Therefore jn=n⋅2nj_n = n \cdot 2^n, which grows like n⋅2nn \cdot 2^n. Choice B would be correct for distinct roots. Choice C misinterprets the recurrence coefficient. Choice D would occur with complex characteristic roots, which doesn't happen here.

Question 2

The sequence en=5en−1−6en−2e_n = 5e_{n-1} - 6e_{n-2} has e0=0e_0 = 0 and e1=1e_1 = 1. Using iteration to find the pattern, which of the following correctly represents e5e_5?

  1. e5=35−25=211e_5 = 3^5 - 2^5 = 211 (correct answer)
  2. e5=35−25=243e_5 = 3^5 - 2^5 = 243
  3. e5=2⋅34−24=146e_5 = 2 \cdot 3^4 - 2^4 = 146
  4. e5=34−2⋅24=49e_5 = 3^4 - 2 \cdot 2^4 = 49
Explanation: Computing iteratively: e2=5(1)−6(0)=5e_2 = 5(1) - 6(0) = 5, e3=5(5)−6(1)=19e_3 = 5(5) - 6(1) = 19, e4=5(19)−6(5)=65e_4 = 5(19) - 6(5) = 65, e5=5(65)−6(19)=211e_5 = 5(65) - 6(19) = 211. The characteristic equation r2−5r+6=0r^2 - 5r + 6 = 0 has roots r=2,3r = 2, 3. So en=A⋅2n+B⋅3ne_n = A \cdot 2^n + B \cdot 3^n. From initial conditions: A+B=0A + B = 0 and 2A+3B=12A + 3B = 1, giving A=−1,B=1A = -1, B = 1. Thus en=3n−2ne_n = 3^n - 2^n. Choice B incorrectly computes 353^5, choice C has coefficient errors, and choice D swaps coefficients.

Question 3

A sequence defined by kn=2kn−1+3⋅2nk_n = 2k_{n-1} + 3 \cdot 2^n with k0=4k_0 = 4 is solved by iteration. After computing several terms and identifying the pattern, what is the particular solution for the non-homogeneous term?

  1. kn(p)=n⋅2nk_n^{(p)} = n \cdot 2^n
  2. kn(p)=3n⋅2nk_n^{(p)} = 3n \cdot 2^n (correct answer)
  3. kn(p)=3⋅2nk_n^{(p)} = 3 \cdot 2^n
  4. kn(p)=6⋅2nk_n^{(p)} = 6 \cdot 2^n
Explanation: The homogeneous equation kn=2kn−1k_n = 2k_{n-1} has solution kn(h)=A⋅2nk_n^{(h)} = A \cdot 2^n. Since the non-homogeneous term is 3⋅2n3 \cdot 2^n and 2n2^n is already a solution to the homogeneous equation, we need to try a particular solution of the form kn(p)=Cn⋅2nk_n^{(p)} = Cn \cdot 2^n. Substituting into the recurrence: Cn⋅2n=2C(n−1)⋅2n−1+3⋅2nCn \cdot 2^n = 2C(n-1) \cdot 2^{n-1} + 3 \cdot 2^n, which simplifies to Cn⋅2n=C(n−1)⋅2n+3⋅2nCn \cdot 2^n = C(n-1) \cdot 2^n + 3 \cdot 2^n. This gives Cn=C(n−1)+3Cn = C(n-1) + 3, so C=3C = 3. Therefore kn(p)=3n⋅2nk_n^{(p)} = 3n \cdot 2^n. Choice A has wrong coefficient, choice C ignores the resonance, and choice D has wrong coefficient.

Question 4

The recurrence gn=3gn−1−2gn−2+2ng_n = 3g_{n-1} - 2g_{n-2} + 2^n has initial values g0=1g_0 = 1 and g1=5g_1 = 5. By expanding terms iteratively and observing the pattern, what is the homogeneous part of the solution?

  1. gn(h)=A⋅2n+B⋅1ng_n^{(h)} = A \cdot 2^n + B \cdot 1^n (correct answer)
  2. gn(h)=A⋅2n+B⋅(−1)ng_n^{(h)} = A \cdot 2^n + B \cdot (-1)^n
  3. gn(h)=A⋅3n+B⋅2ng_n^{(h)} = A \cdot 3^n + B \cdot 2^n
  4. gn(h)=A⋅1n+B⋅2ng_n^{(h)} = A \cdot 1^n + B \cdot 2^n
Explanation: For the homogeneous equation gn=3gn−1−2gn−2g_n = 3g_{n-1} - 2g_{n-2}, the characteristic equation is r2−3r+2=0r^2 - 3r + 2 = 0, which factors as (r−1)(r−2)=0(r-1)(r-2) = 0. This gives roots r=1,2r = 1, 2. Therefore, the homogeneous solution is gn(h)=A⋅1n+B⋅2n=A+B⋅2ng_n^{(h)} = A \cdot 1^n + B \cdot 2^n = A + B \cdot 2^n. Choice B incorrectly uses (−1)n(-1)^n, choice C uses wrong roots (would come from r2−5r+6=0r^2 - 5r + 6 = 0), and choice D is the same as choice A but written differently.

Question 5

Given pn=2pn−1−pn−2+2p_n = 2p_{n-1} - p_{n-2} + 2 (non-homogeneous) with p0=1p_0 = 1 and p1=3p_1 = 3, what is p4p_4 found through direct iteration?

  1. 1919
  2. 2323
  3. 1717
  4. 2121 (correct answer)
Explanation: Computing iteratively with the non-homogeneous term: p2=2p1−p0+2=2(3)−1+2=7p_2 = 2p_1 - p_0 + 2 = 2(3) - 1 + 2 = 7, p3=2p2−p1+2=2(7)−3+2=13p_3 = 2p_2 - p_1 + 2 = 2(7) - 3 + 2 = 13, p4=2p3−p2+2=2(13)−7+2=21p_4 = 2p_3 - p_2 + 2 = 2(13) - 7 + 2 = 21. Choice A results from forgetting the constant term in one step. Choice B comes from sign errors. Choice C reflects computational mistakes with the non-homogeneous recurrence. The key is carefully tracking the constant term +2+2 at each iteration step.