Solve linear recurrences with characteristic equations (intro) - Discrete Math

1. Consider the recurrence $j_n = kj_{n-1} + \ell j_{n-2}$ where $k > 0$ and $\ell < 0$. If one characteristic root is $r_1 = 4$ and the other root $r_2$ satisfies $|r_2| < 1$, which constraint must hold?
   Answer: $k = 4 + r_2$ and $\ell = -4r_2$ From Vieta's formulas for the characteristic equation $r^2 - kr - \ell = 0$: $r_1 + r_2 = k$ and $r_1 r_2 = -\ell$. With $r_1 = 4$: $k = 4 + r_2$ and $\ell = -r_1 r_2 = -4r_2$. Since $\ell < 0$ and $\ell = -4r_2$, we need $-4r_2 < 0$, which means $r_2 > 0$. Combined with $|r_2| < 1$, we have $0 < r_2 < 1$. This makes $k = 4 + r_2 > 4$ and $\ell = -4r_2$ where $-4 < \ell < 0$. The exact relationships are $k = 4 + r_2$ and $\ell = -4r_2$. Choice A gives inequalities but not the precise relationships. Choice B is incorrect about $k$. Choice C is partially correct but doesn't give the exact relationship for $\ell$.
2. Consider two recurrence relations: $u_n = 5u_{n-1} - 6u_{n-2}$ and $v_n = 5v_{n-1} - 6v_{n-2}$. If $u_0 = 1, u_1 = 2$ and $v_0 = 0, v_1 = 1$, what is the relationship between $u_n$ and $v_n$?
   Answer: $u_n = 2^n$ and $v_n = 3^n - 2^n$ 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 $w_n = 5w_{n-1} - 6w_{n-2}$, so they have the same characteristic equation: $r^2 - 5r + 6 = 0$. This factors as $(r-2)(r-3) = 0$, giving roots $r = 2$ and $r = 3$. Therefore, the general solution is $w_n = A \cdot 2^n + B \cdot 3^n$. For $u_n$ with initial conditions $u_0 = 1, u_1 = 2$: - $u_0 = A + B = 1$ - $u_1 = 2A + 3B = 2$ Solving: From the first equation, $A = 1 - B$. Substituting: $2(1-B) + 3B = 2$, so $2 - 2B + 3B = 2$, giving $B = 0$ and $A = 1$. Thus $u_n = 2^n$. For $v_n$ with initial conditions $v_0 = 0, v_1 = 1$: - $v_0 = A + B = 0$ - $v_1 = 2A + 3B = 1$ From the first equation, $A = -B$. Substituting: $2(-B) + 3B = 1$, so $B = 1$ and $A = -1$. Thus $v_n = 3^n - 2^n$. Option A gives an incorrect relationship formula. Option B swaps the expressions for $u_n$ and $v_n$. Option D has the wrong coefficient for $v_n$ (should be $-1$, not $-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.
3. A sequence follows the recurrence $h_n = 2h_{n-1} + 3h_{n-2}$ for $n \geq 2$. If the explicit solution is $h_n = A(-1)^n + B \cdot 3^n$ for some constants $A$ and $B$, what is the relationship between the coefficients in the characteristic equation?
   Answer: The characteristic equation is $r^2 - 2r - 3 = 0$ with discriminant $\Delta = 16$ 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 $h_n = A(-1)^n + B \cdot 3^n$ tells you that the characteristic equation has roots $r_1 = -1$ and $r_2 = 3$. This is because each term in the explicit solution corresponds to a root raised to the $n$th power. To find the characteristic equation from these roots, use the fact that if $r_1 = -1$ and $r_2 = 3$ are roots, then: $(r - (-1))(r - 3) = 0$ $(r + 1)(r - 3) = 0$ $r^2 - 3r + r - 3 = 0$ $r^2 - 2r - 3 = 0$ The discriminant is $\Delta = b^2 - 4ac = (-2)^2 - 4(1)(-3) = 4 + 12 = 16$. Choice A incorrectly flips signs, giving $r^2 + 2r + 3 = 0$, which would have complex roots, not the real roots $-1$ and $3$ we need. Choice B has the wrong constant term ($-3$ becomes $+3$) and wrong linear coefficient. Choice C correctly identifies the characteristic equation but miscalculates the discriminant as $4$ instead of $16$. 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 $n$th power in each term.
4. For the recurrence relation $k_n = 2k_{n-1} + 3k_{n-2}$, suppose the general solution can be written as $k_n = A \cdot r_1^n + B \cdot r_2^n$ where $r_1 > r_2$. If $k_0 = 4$ and $k_1 = 2$, what is the ratio $\frac{A}{B}$?
   Answer: $\frac{6}{10}$ The characteristic equation is $r^2 - 2r - 3 = 0$, which factors as $(r-3)(r+1) = 0$. The roots are $r_1 = 3$ and $r_2 = -1$ (since $3 > -1$). From the initial conditions: $k_0 = A + B = 4$ and $k_1 = 3A - B = 2$. Adding these equations: $4A = 6$, so $A = \frac{3}{2}$. From the first equation: $B = 4 - \frac{3}{2} = \frac{5}{2}$. Therefore $\frac{A}{B} = \frac{3/2}{5/2} = \frac{3}{5} = \frac{6}{10}$.
5. A sequence satisfies $b_n - 4b_{n-1} + 4b_{n-2} = 0$ for $n \geq 2$. If the characteristic equation has a repeated root, which form represents the correct general solution?
   Answer: $b_n = A \cdot 2^n + B \cdot n \cdot 2^n$ for constants $A$ and $B$ The characteristic equation is $r^2 - 4r + 4 = 0$, which factors as $(r-2)^2 = 0$, giving a repeated root $r = 2$ with multiplicity 2. For repeated roots, the general solution is $b_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.
6. Consider the recurrence relation $a_n = 5a_{n-1} - 6a_{n-2}$ with initial conditions $a_0 = 2$ and $a_1 = 7$. After solving using the characteristic equation method, what is the value of $a_4$?
   Answer: $a_4 = 62$ The characteristic equation is $r^2 - 5r + 6 = 0$, which factors as $(r-2)(r-3) = 0$, giving roots $r_1 = 2$ and $r_2 = 3$. The general solution is $a_n = A \cdot 2^n + B \cdot 3^n$. Using initial conditions: $a_0 = A + B = 2$ and $a_1 = 2A + 3B = 7$. Solving gives $A = -1$ and $B = 3$. Therefore $a_n = -2^n + 3 \cdot 3^n = -2^n + 3^{n+1}$. Thus $a_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 $r^2 + 5r + 6 = 0$. Choice D results from sign errors in applying initial conditions.
7. A sequence $\{w_n\}$ satisfies a second-order linear homogeneous recurrence with constant coefficients. If $w_0 = 2$, $w_1 = 7$, $w_2 = 20$, and $w_3 = 61$, what is $w_4$?
   Answer: $w_4 = 182$ When you encounter a second-order linear homogeneous recurrence with constant coefficients, you're looking for a relationship of the form $w_n = aw_{n-1} + bw_{n-2}$ where $a$ and $b$ 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 $w_2 = aw_1 + bw_0$: $20 = 7a + 2b$. From $w_3 = aw_2 + bw_1$: $61 = 20a + 7b$. Solving this system: multiply the first equation by 7 and the second by 2 to get $140 = 49a + 14b$ and $122 = 40a + 14b$. Subtracting gives $18 = 9a$, so $a = 2$. Substituting back: $20 = 14 + 2b$, which yields $b = 3$. The recurrence relation is $w_n = 2w_{n-1} + 3w_{n-2}$. Therefore: $w_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 = 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.
8. The Fibonacci-like sequence $F_n = F_{n-1} + F_{n-2}$ has initial conditions $F_0 = p$ and $F_1 = q$ where $p$ and $q$ are parameters. If the ratio $\lim_{n \to \infty} \frac{F_{n+1}}{F_n}$ exists and equals $\phi = \frac{1+\sqrt{5}}{2}$, which statement about $p$ and $q$ is correct?
   Answer: The limit equals $\phi$ only when $q \neq p \cdot \frac{1-\sqrt{5}}{2}$ The characteristic equation $r^2 - r - 1 = 0$ has roots $\phi = \frac{1+\sqrt{5}}{2}$ and $\psi = \frac{1-\sqrt{5}}{2}$. Note that $|\phi| > 1$ and $|\psi| < 1$. The general solution is $F_n = A\phi^n + B\psi^n$. Using initial conditions: $F_0 = A + B = p$ and $F_1 = A\phi + B\psi = q$. Solving: $A = \frac{q - p\psi}{\phi - \psi}$ and $B = \frac{p\phi - q}{\phi - \psi}$. For large $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 $|\psi/\phi| < 1$, as $n \to \infty$, this approaches $\frac{A\phi}{A} = \phi$ provided $A \neq 0$. If $A = 0$, then $F_n = B\psi^n$ and $\frac{F_{n+1}}{F_n} = \psi \neq \phi$. From $A = \frac{q - p\psi}{\phi - \psi}$, we have $A = 0$ when $q - p\psi = 0$, i.e., $q = p\psi = p \cdot \frac{1-\sqrt{5}}{2}$. So the limit equals $\phi$ exactly when $q \neq p \cdot \frac{1-\sqrt{5}}{2}$. Choice A is too restrictive. Choice C ignores the special case where $A = 0$. Choice D incorrectly focuses on the signs of $p$ and $q$.
9. Consider the recurrence relation $a_n = 5a_{n-1} - 6a_{n-2}$ with initial conditions $a_0 = 2$ and $a_1 = 7$. What is the value of $a_5$?
   Answer: 242 The characteristic equation is $r^2 - 5r + 6 = 0$, which factors as $(r-2)(r-3) = 0$. So $r_1 = 2$ and $r_2 = 3$. The general solution is $a_n = A \cdot 2^n + B \cdot 3^n$. Using initial conditions: $a_0 = A + B = 2$ and $a_1 = 2A + 3B = 7$. Solving: $B = 3$ and $A = -1$. Thus $a_n = -2^n + 3^{n+1}$. Therefore $a_5 = -32 + 3^6 = -32 + 729 = 242$.
10. The sequence $\{d_n\}$ satisfies $d_n - 3d_{n-1} + 2d_{n-2} = 0$ with $d_0 = 0$ and $d_1 = 1$. For which value of $k$ is $d_k = 2^k - 1$?
    Answer: This formula holds for all $k \geq 0$ The characteristic equation is $r^2 - 3r + 2 = 0$, factoring as $(r-1)(r-2) = 0$ with roots $r_1 = 1$ and $r_2 = 2$. The general solution is $d_n = A \cdot 1^n + B \cdot 2^n = A + B \cdot 2^n$. Using initial conditions: $d_0 = A + B = 0$ and $d_1 = A + 2B = 1$. Solving: $B = 1$ and $A = -1$. Therefore $d_n = -1 + 2^n = 2^n - 1$. Checking: $d_0 = 2^0 - 1 = 0$ ✓, $d_1 = 2^1 - 1 = 1$ ✓, $d_2 = 2^2 - 1 = 3$, and by recurrence $d_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 = 0$. Choice D ignores the correct derivation.
11. A linear recurrence relation has the general solution $f_n = 2 \cdot 4^n - 3 \cdot (-1)^n$. What are the initial conditions $f_0$ and $f_1$?
    Answer: $f_0 = -1, f_1 = 11$ To find the initial conditions, substitute $n = 0$ and $n = 1$ into the general solution. For $n = 0$: $f_0 = 2 \cdot 4^0 - 3 \cdot (-1)^0 = 2 \cdot 1 - 3 \cdot 1 = 2 - 3 = -1$. For $n = 1$: $f_1 = 2 \cdot 4^1 - 3 \cdot (-1)^1 = 2 \cdot 4 - 3 \cdot (-1) = 8 + 3 = 11$. Therefore $f_0 = -1$ and $f_1 = 11$.

Start this quiz