Solve linear recurrences by iteration/expansion - Discrete Math

1. Given $p_n = 2p_{n-1} - p_{n-2} + 2$ (non-homogeneous) with $p_0 = 1$ and $p_1 = 3$, what is $p_4$ found through direct iteration?
   Answer: $21$ Computing iteratively with the non-homogeneous term: $p_2 = 2p_1 - p_0 + 2 = 2(3) - 1 + 2 = 7$, $p_3 = 2p_2 - p_1 + 2 = 2(7) - 3 + 2 = 13$, $p_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$ at each iteration step.
2. The recurrence $g_n = 3g_{n-1} - 2g_{n-2} + 2^n$ has initial values $g_0 = 1$ and $g_1 = 5$. By expanding terms iteratively and observing the pattern, what is the homogeneous part of the solution?
   Answer: $g_n^{(h)} = A \cdot 2^n + B \cdot 1^n$ For the homogeneous equation $g_n = 3g_{n-1} - 2g_{n-2}$, the characteristic equation is $r^2 - 3r + 2 = 0$, which factors as $(r-1)(r-2) = 0$. This gives roots $r = 1, 2$. Therefore, the homogeneous solution is $g_n^{(h)} = A \cdot 1^n + B \cdot 2^n = A + B \cdot 2^n$. Choice B incorrectly uses $(-1)^n$, choice C uses wrong roots (would come from $r^2 - 5r + 6 = 0$), and choice D is the same as choice A but written differently.
3. The sequence $e_n = 5e_{n-1} - 6e_{n-2}$ has $e_0 = 0$ and $e_1 = 1$. Using iteration to find the pattern, which of the following correctly represents $e_5$?
   Answer: $e_5 = 3^5 - 2^5 = 211$ Computing iteratively: $e_2 = 5(1) - 6(0) = 5$, $e_3 = 5(5) - 6(1) = 19$, $e_4 = 5(19) - 6(5) = 65$, $e_5 = 5(65) - 6(19) = 211$. The characteristic equation $r^2 - 5r + 6 = 0$ has roots $r = 2, 3$. So $e_n = A \cdot 2^n + B \cdot 3^n$. From initial conditions: $A + B = 0$ and $2A + 3B = 1$, giving $A = -1, B = 1$. Thus $e_n = 3^n - 2^n$. Choice B incorrectly computes $3^5$, choice C has coefficient errors, and choice D swaps coefficients.
4. The sequence $j_n$ satisfies $j_n = 4j_{n-1} - 4j_{n-2}$ with $j_0 = 0$ and $j_1 = 2$. Through iterative expansion, which of the following best describes the growth pattern of $j_n$ for large $n$?
   Answer: Grows like $n \cdot 2^n$ due to repeated root structure The characteristic equation is $r^2 - 4r + 4 = 0$, which factors as $(r-2)^2 = 0$, giving a repeated root $r = 2$. With repeated roots, the general solution is $j_n = (A + Bn) \cdot 2^n$. Using initial conditions: $j_0 = A = 0$ and $j_1 = (0 + B) \cdot 2 = 2B = 2$, so $B = 1$. Therefore $j_n = n \cdot 2^n$, which grows like $n \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.
5. A sequence defined by $k_n = 2k_{n-1} + 3 \cdot 2^n$ with $k_0 = 4$ is solved by iteration. After computing several terms and identifying the pattern, what is the particular solution for the non-homogeneous term?
   Answer: $k_n^{(p)} = 3n \cdot 2^n$ The homogeneous equation $k_n = 2k_{n-1}$ has solution $k_n^{(h)} = A \cdot 2^n$. Since the non-homogeneous term is $3 \cdot 2^n$ and $2^n$ is already a solution to the homogeneous equation, we need to try a particular solution of the form $k_n^{(p)} = Cn \cdot 2^n$. Substituting into the recurrence: $Cn \cdot 2^n = 2C(n-1) \cdot 2^{n-1} + 3 \cdot 2^n$, which simplifies to $Cn \cdot 2^n = C(n-1) \cdot 2^n + 3 \cdot 2^n$. This gives $Cn = C(n-1) + 3$, so $C = 3$. Therefore $k_n^{(p)} = 3n \cdot 2^n$. Choice A has wrong coefficient, choice C ignores the resonance, and choice D has wrong coefficient.

Start this quiz