Discrete Math Quiz: Characteristic Equations For Recurrences
11 questions · exam conditions
0:00
Characteristic Equations For RecurrencesQuestion 1 of 11

A sequence follows the recurrence hn=2hn−1+3hn−2h_n = 2h_{n-1} + 3h_{n-2} for n≥2n \geq 2. If the explicit solution is hn=A(−1)n+B⋅3nh_n = A(-1)^n + B \cdot 3^n for some constants AA and BB, what is the relationship between the coefficients in the characteristic equation?

The characteristic equation is r2+2r+3=0r^2 + 2r + 3 = 0 with discriminant Δ=−8\Delta = -8
The characteristic equation is r2+2r−3=0r^2 + 2r - 3 = 0 with discriminant Δ=16\Delta = 16
The characteristic equation is r2−2r−3=0r^2 - 2r - 3 = 0 with discriminant Δ=4\Delta = 4
The characteristic equation is r2−2r−3=0r^2 - 2r - 3 = 0 with discriminant Δ=16\Delta = 16
← Back to quizzes

Discrete Math Quiz

Discrete Math Quiz: Characteristic Equations For Recurrences

Practice Characteristic Equations For Recurrences 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 Characteristic Equations For Recurrences, 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

A sequence follows the recurrence hn=2hn−1+3hn−2h_n = 2h_{n-1} + 3h_{n-2} for n≥2n \geq 2. If the explicit solution is hn=A(−1)n+B⋅3nh_n = A(-1)^n + B \cdot 3^n for some constants AA and BB, what is the relationship between the coefficients in the characteristic equation?

  1. The characteristic equation is r2+2r+3=0r^2 + 2r + 3 = 0 with discriminant Δ=−8\Delta = -8
  2. The characteristic equation is r2+2r−3=0r^2 + 2r - 3 = 0 with discriminant Δ=16\Delta = 16
  3. The characteristic equation is r2−2r−3=0r^2 - 2r - 3 = 0 with discriminant Δ=4\Delta = 4
  4. The characteristic equation is r2−2r−3=0r^2 - 2r - 3 = 0 with discriminant Δ=16\Delta = 16 (correct answer)
Explanation: When you encounter a linear recurrence relation with a given explicit solution, you need to work backwards to find the characteristic equation that produces those solution terms. The explicit solution hn=A(−1)n+B⋅3nh_n = A(-1)^n + B \cdot 3^n tells you that the characteristic equation has roots r1=−1r_1 = -1 and r2=3r_2 = 3. This is because each term in the explicit solution corresponds to a root raised to the nnth power. To find the characteristic equation from these roots, use the fact that if r1=−1r_1 = -1 and r2=3r_2 = 3 are roots, then: (r−(−1))(r−3)=0(r - (-1))(r - 3) = 0 (r+1)(r−3)=0(r + 1)(r - 3) = 0 r2−3r+r−3=0r^2 - 3r + r - 3 = 0 r2−2r−3=0r^2 - 2r - 3 = 0 The discriminant is Δ=b2−4ac=(−2)2−4(1)(−3)=4+12=16\Delta = b^2 - 4ac = (-2)^2 - 4(1)(-3) = 4 + 12 = 16. Choice A incorrectly flips signs, giving r2+2r+3=0r^2 + 2r + 3 = 0, which would have complex roots, not the real roots −1-1 and 33 we need. Choice B has the wrong constant term (−3-3 becomes +3+3) and wrong linear coefficient. Choice C correctly identifies the characteristic equation but miscalculates the discriminant as 44 instead of 1616. Study tip: Always verify your characteristic equation by checking that its roots match the base terms in the explicit solution. The roots should be the numbers being raised to the nnth power in each term.

Question 2

Consider the recurrence jn=kjn−1+ℓjn−2j_n = kj_{n-1} + \ell j_{n-2} where k>0k > 0 and ℓ<0\ell < 0. If one characteristic root is r1=4r_1 = 4 and the other root r2r_2 satisfies ∣r2∣<1|r_2| < 1, which constraint must hold?

  1. k>4k > 4 and ℓ>−k4\ell > -\frac{k}{4}
  2. k<4k < 4 and −4<ℓ<0-4 < \ell < 0
  3. k=4+r2k = 4 + r_2 and −4<ℓ<0-4 < \ell < 0
  4. k=4+r2k = 4 + r_2 and ℓ=−4r2\ell = -4r_2 (correct answer)
Explanation: From Vieta's formulas for the characteristic equation r2−kr−ℓ=0r^2 - kr - \ell = 0: r1+r2=kr_1 + r_2 = k and r1r2=−ℓr_1 r_2 = -\ell. With r1=4r_1 = 4: k=4+r2k = 4 + r_2 and ℓ=−r1r2=−4r2\ell = -r_1 r_2 = -4r_2. Since ℓ<0\ell < 0 and ℓ=−4r2\ell = -4r_2, we need −4r2<0-4r_2 < 0, which means r2>0r_2 > 0. Combined with ∣r2∣<1|r_2| < 1, we have 0<r2<10 < r_2 < 1. This makes k=4+r2>4k = 4 + r_2 > 4 and ℓ=−4r2\ell = -4r_2 where −4<ℓ<0-4 < \ell < 0. The exact relationships are k=4+r2k = 4 + r_2 and ℓ=−4r2\ell = -4r_2. Choice A gives inequalities but not the precise relationships. Choice B is incorrect about kk. Choice C is partially correct but doesn't give the exact relationship for ℓ\ell.

Question 3

Consider two recurrence relations: un=5un−1−6un−2u_n = 5u_{n-1} - 6u_{n-2} and vn=5vn−1−6vn−2v_n = 5v_{n-1} - 6v_{n-2}. If u0=1,u1=2u_0 = 1, u_1 = 2 and v0=0,v1=1v_0 = 0, v_1 = 1, what is the relationship between unu_n and vnv_n?

  1. un=2vn+3nu_n = 2v_n + 3^n for all n≥0n \geq 0
  2. un=3n−2nu_n = 3^n - 2^n and vn=2nv_n = 2^n
  3. un=2nu_n = 2^n and vn=3n−2nv_n = 3^n - 2^n (correct answer)
  4. un=3nu_n = 3^n and vn=3n−2⋅2nv_n = 3^n - 2 \cdot 2^n
Explanation: When you encounter linear recurrence relations with the same characteristic equation but different initial conditions, you're looking at solutions that share the same general form but with different particular coefficients. Both sequences follow wn=5wn−1−6wn−2w_n = 5w_{n-1} - 6w_{n-2}, so they have the same characteristic equation: r2−5r+6=0r^2 - 5r + 6 = 0. This factors as (r−2)(r−3)=0(r-2)(r-3) = 0, giving roots r=2r = 2 and r=3r = 3. Therefore, the general solution is wn=A⋅2n+B⋅3nw_n = A \cdot 2^n + B \cdot 3^n. For unu_n with initial conditions u0=1,u1=2u_0 = 1, u_1 = 2:
  • u0=A+B=1u_0 = A + B = 1
  • u1=2A+3B=2u_1 = 2A + 3B = 2
Solving: From the first equation, A=1−BA = 1 - B. Substituting: 2(1−B)+3B=22(1-B) + 3B = 2, so 2−2B+3B=22 - 2B + 3B = 2, giving B=0B = 0 and A=1A = 1. Thus un=2nu_n = 2^n. For vnv_n with initial conditions v0=0,v1=1v_0 = 0, v_1 = 1:
  • v0=A+B=0v_0 = A + B = 0
  • v1=2A+3B=1v_1 = 2A + 3B = 1
From the first equation, A=−BA = -B. Substituting: 2(−B)+3B=12(-B) + 3B = 1, so B=1B = 1 and A=−1A = -1. Thus vn=3n−2nv_n = 3^n - 2^n. Option A gives an incorrect relationship formula. Option B swaps the expressions for unu_n and vnv_n. Option D has the wrong coefficient for vnv_n (should be −1-1, not −2-2). Study tip: Always solve recurrence relations by finding the characteristic equation first, then use initial conditions to determine the specific coefficients. Double-check by verifying your solution satisfies both the recurrence and initial conditions.

Question 4

The Fibonacci-like sequence Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2} has initial conditions F0=pF_0 = p and F1=qF_1 = q where pp and qq are parameters. If the ratio lim⁡n→∞Fn+1Fn\lim_{n \to \infty} \frac{F_{n+1}}{F_n} exists and equals ϕ=1+52\phi = \frac{1+\sqrt{5}}{2}, which statement about pp and qq is correct?

  1. The limit equals ϕ\phi only when p=0p = 0 and q=1q = 1
  2. The limit equals ϕ\phi only when q≠p⋅1−52q \neq p \cdot \frac{1-\sqrt{5}}{2} (correct answer)
  3. The limit equals ϕ\phi for any choice of pp and qq
  4. The limit equals ϕ\phi only when pp and qq are both positive
Explanation: The characteristic equation r2−r−1=0r^2 - r - 1 = 0 has roots ϕ=1+52\phi = \frac{1+\sqrt{5}}{2} and ψ=1−52\psi = \frac{1-\sqrt{5}}{2}. Note that ∣ϕ∣>1|\phi| > 1 and ∣ψ∣<1|\psi| < 1. The general solution is Fn=Aϕn+BψnF_n = A\phi^n + B\psi^n. Using initial conditions: F0=A+B=pF_0 = A + B = p and F1=Aϕ+Bψ=qF_1 = A\phi + B\psi = q. Solving: A=q−pψϕ−ψA = \frac{q - p\psi}{\phi - \psi} and B=pϕ−qϕ−ψB = \frac{p\phi - q}{\phi - \psi}. For large nn, Fn+1Fn=Aϕn+1+Bψn+1Aϕn+Bψn=Aϕ+Bψ(ψ/ϕ)nA+B(ψ/ϕ)n\frac{F_{n+1}}{F_n} = \frac{A\phi^{n+1} + B\psi^{n+1}}{A\phi^n + B\psi^n} = \frac{A\phi + B\psi(\psi/\phi)^n}{A + B(\psi/\phi)^n}. Since ∣ψ/ϕ∣<1|\psi/\phi| < 1, as n→∞n \to \infty, this approaches AϕA=ϕ\frac{A\phi}{A} = \phi provided A≠0A \neq 0. If A=0A = 0, then Fn=BψnF_n = B\psi^n and Fn+1Fn=ψ≠ϕ\frac{F_{n+1}}{F_n} = \psi \neq \phi. From A=q−pψϕ−ψA = \frac{q - p\psi}{\phi - \psi}, we have A=0A = 0 when q−pψ=0q - p\psi = 0, i.e., q=pψ=p⋅1−52q = p\psi = p \cdot \frac{1-\sqrt{5}}{2}. So the limit equals ϕ\phi exactly when q≠p⋅1−52q \neq p \cdot \frac{1-\sqrt{5}}{2}. Choice A is too restrictive. Choice C ignores the special case where A=0A = 0. Choice D incorrectly focuses on the signs of pp and qq.

Question 5

Consider the recurrence relation an=5an−1−6an−2a_n = 5a_{n-1} - 6a_{n-2} with initial conditions a0=2a_0 = 2 and a1=7a_1 = 7. After solving using the characteristic equation method, what is the value of a4a_4?

  1. a4=47a_4 = 47
  2. a4=62a_4 = 62 (correct answer)
  3. a4=83a_4 = 83
  4. a4=95a_4 = 95
Explanation: The characteristic equation is r2−5r+6=0r^2 - 5r + 6 = 0, which factors as (r−2)(r−3)=0(r-2)(r-3) = 0, giving roots r1=2r_1 = 2 and r2=3r_2 = 3. The general solution is an=A⋅2n+B⋅3na_n = A \cdot 2^n + B \cdot 3^n. Using initial conditions: a0=A+B=2a_0 = A + B = 2 and a1=2A+3B=7a_1 = 2A + 3B = 7. Solving gives A=−1A = -1 and B=3B = 3. Therefore an=−2n+3⋅3n=−2n+3n+1a_n = -2^n + 3 \cdot 3^n = -2^n + 3^{n+1}. Thus a4=−24+35=−16+243=62a_4 = -2^4 + 3^5 = -16 + 243 = 62. Choice A results from computational errors in the coefficient calculation. Choice C comes from incorrectly setting up the characteristic equation as r2+5r+6=0r^2 + 5r + 6 = 0. Choice D results from sign errors in applying initial conditions.

Question 6

For the recurrence relation kn=2kn−1+3kn−2k_n = 2k_{n-1} + 3k_{n-2}, suppose the general solution can be written as kn=A⋅r1n+B⋅r2nk_n = A \cdot r_1^n + B \cdot r_2^n where r1>r2r_1 > r_2. If k0=4k_0 = 4 and k1=2k_1 = 2, what is the ratio AB\frac{A}{B}?

  1. 23\frac{2}{3}
  2. 32\frac{3}{2}
  3. 106\frac{10}{6}
  4. 610\frac{6}{10} (correct answer)
Explanation: The characteristic equation is r2−2r−3=0r^2 - 2r - 3 = 0, which factors as (r−3)(r+1)=0(r-3)(r+1) = 0. The roots are r1=3r_1 = 3 and r2=−1r_2 = -1 (since 3>−13 > -1). From the initial conditions: k0=A+B=4k_0 = A + B = 4 and k1=3A−B=2k_1 = 3A - B = 2. Adding these equations: 4A=64A = 6, so A=32A = \frac{3}{2}. From the first equation: B=4−32=52B = 4 - \frac{3}{2} = \frac{5}{2}. Therefore AB=3/25/2=35=610\frac{A}{B} = \frac{3/2}{5/2} = \frac{3}{5} = \frac{6}{10}.

Question 7

The sequence {dn}\{d_n\} satisfies dn−3dn−1+2dn−2=0d_n - 3d_{n-1} + 2d_{n-2} = 0 with d0=0d_0 = 0 and d1=1d_1 = 1. For which value of kk is dk=2k−1d_k = 2^k - 1?

  1. This formula holds for all k≥0k \geq 0 (correct answer)
  2. This formula holds only for k=1k = 1 and k=2k = 2
  3. This formula holds only for k≥1k \geq 1
  4. This formula never holds for any kk
Explanation: The characteristic equation is r2−3r+2=0r^2 - 3r + 2 = 0, factoring as (r−1)(r−2)=0(r-1)(r-2) = 0 with roots r1=1r_1 = 1 and r2=2r_2 = 2. The general solution is dn=A⋅1n+B⋅2n=A+B⋅2nd_n = A \cdot 1^n + B \cdot 2^n = A + B \cdot 2^n. Using initial conditions: d0=A+B=0d_0 = A + B = 0 and d1=A+2B=1d_1 = A + 2B = 1. Solving: B=1B = 1 and A=−1A = -1. Therefore dn=−1+2n=2n−1d_n = -1 + 2^n = 2^n - 1. Checking: d0=20−1=0d_0 = 2^0 - 1 = 0 ✓, d1=21−1=1d_1 = 2^1 - 1 = 1 ✓, d2=22−1=3d_2 = 2^2 - 1 = 3, and by recurrence d2=3d1−2d0=3(1)−2(0)=3d_2 = 3d_1 - 2d_0 = 3(1) - 2(0) = 3 ✓. Choice B incorrectly assumes the formula only works for the initial conditions. Choice C misses that it works for k=0k = 0. Choice D ignores the correct derivation.

Question 8

A sequence satisfies bn−4bn−1+4bn−2=0b_n - 4b_{n-1} + 4b_{n-2} = 0 for n≥2n \geq 2. If the characteristic equation has a repeated root, which form represents the correct general solution?

  1. bn=A⋅2n+B⋅n⋅2nb_n = A \cdot 2^n + B \cdot n \cdot 2^n for constants AA and BB (correct answer)
  2. bn=A⋅2n+B⋅22nb_n = A \cdot 2^n + B \cdot 2^{2n} for constants AA and BB
  3. bn=A⋅4n+B⋅n⋅4nb_n = A \cdot 4^n + B \cdot n \cdot 4^n for constants AA and BB
  4. bn=(A+Bn)⋅4nb_n = (A + Bn) \cdot 4^n for constants AA and BB
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 multiplicity 2. For repeated roots, the general solution is bn=A⋅rn+B⋅n⋅rn=A⋅2n+B⋅n⋅2nb_n = A \cdot r^n + B \cdot n \cdot r^n = A \cdot 2^n + B \cdot n \cdot 2^n. Choice B incorrectly treats this as having distinct roots 2 and 4. Choice C uses the wrong base (4 instead of 2). Choice D also uses the wrong base and represents the same form as A but with base 4.

Question 9

A sequence {wn}\{w_n\} satisfies a second-order linear homogeneous recurrence with constant coefficients. If w0=2w_0 = 2, w1=7w_1 = 7, w2=20w_2 = 20, and w3=61w_3 = 61, what is w4w_4?

  1. w4=188w_4 = 188
  2. w4=185w_4 = 185
  3. w4=182w_4 = 182 (correct answer)
  4. w4=191w_4 = 191
Explanation: When you encounter a second-order linear homogeneous recurrence with constant coefficients, you're looking for a relationship of the form wn=awn−1+bwn−2w_n = aw_{n-1} + bw_{n-2} where aa and bb are constants. Your task is to find these coefficients using the given terms. Using the known values, you can set up a system of equations. From w2=aw1+bw0w_2 = aw_1 + bw_0: 20=7a+2b20 = 7a + 2b. From w3=aw2+bw1w_3 = aw_2 + bw_1: 61=20a+7b61 = 20a + 7b. Solving this system: multiply the first equation by 7 and the second by 2 to get 140=49a+14b140 = 49a + 14b and 122=40a+14b122 = 40a + 14b. Subtracting gives 18=9a18 = 9a, so a=2a = 2. Substituting back: 20=14+2b20 = 14 + 2b, which yields b=3b = 3. The recurrence relation is wn=2wn−1+3wn−2w_n = 2w_{n-1} + 3w_{n-2}. Therefore: w4=2w3+3w2=2(61)+3(20)=122+60=182w_4 = 2w_3 + 3w_2 = 2(61) + 3(20) = 122 + 60 = 182. Answer A (188) likely comes from using incorrect coefficients like a=3,b=1a = 3, b = 1. Answer B (185) might result from computational errors in the system solving. Answer D (191) could arise from misapplying the recurrence formula or arithmetic mistakes. Study tip: Always verify your recurrence relation by checking it against all given terms before calculating the final answer. Setting up the coefficient equations systematically prevents algebraic errors.

Question 10

Consider the recurrence relation an=5an−1−6an−2a_n = 5a_{n-1} - 6a_{n-2} with initial conditions a0=2a_0 = 2 and a1=7a_1 = 7. What is the value of a5a_5?

  1. 122
  2. 242 (correct answer)
  3. 338
  4. 422
Explanation: The characteristic equation is r2−5r+6=0r^2 - 5r + 6 = 0, which factors as (r−2)(r−3)=0(r-2)(r-3) = 0. So r1=2r_1 = 2 and r2=3r_2 = 3. The general solution is an=A⋅2n+B⋅3na_n = A \cdot 2^n + B \cdot 3^n. Using initial conditions: a0=A+B=2a_0 = A + B = 2 and a1=2A+3B=7a_1 = 2A + 3B = 7. Solving: B=3B = 3 and A=−1A = -1. Thus an=−2n+3n+1a_n = -2^n + 3^{n+1}. Therefore a5=−32+36=−32+729=242a_5 = -32 + 3^6 = -32 + 729 = 242.

Question 11

A linear recurrence relation has the general solution fn=2⋅4n−3⋅(−1)nf_n = 2 \cdot 4^n - 3 \cdot (-1)^n. What are the initial conditions f0f_0 and f1f_1?

  1. f0=−1,f1=5f_0 = -1, f_1 = 5
  2. f0=5,f1=−1f_0 = 5, f_1 = -1
  3. f0=−1,f1=11f_0 = -1, f_1 = 11 (correct answer)
  4. f0=5,f1=11f_0 = 5, f_1 = 11
Explanation: To find the initial conditions, substitute n=0n = 0 and n=1n = 1 into the general solution. For n=0n = 0: f0=2⋅40−3⋅(−1)0=2⋅1−3⋅1=2−3=−1f_0 = 2 \cdot 4^0 - 3 \cdot (-1)^0 = 2 \cdot 1 - 3 \cdot 1 = 2 - 3 = -1. For n=1n = 1: f1=2⋅41−3⋅(−1)1=2⋅4−3⋅(−1)=8+3=11f_1 = 2 \cdot 4^1 - 3 \cdot (-1)^1 = 2 \cdot 4 - 3 \cdot (-1) = 8 + 3 = 11. Therefore f0=−1f_0 = -1 and f1=11f_1 = 11.