Consider the recurrence $b_n = 10b_{n−1} − 25b_{n−2}$, subject to initial conditions $b_0 = 4$ and $b_1 = 12$
(a) Compute $b_2, b_3, b_4,$ and $b_5$.
(b) Find a solution to the recurrence.
(c) Check that your solution gives the correct result for $b_5$
<aside> 💡 (a) $b_2 = 20, b_3 = -100, b_4 = -1500$, and $b_5 = -12500$.
</aside>
<aside> 💡 (b) The characteristic equation of the recurrence is $r^2 - 10r + 25 = 0$, which has a repeated root of $r = 5$.
Let $b_n=c_15^n+c_2n5^n$
$$ \begin{cases}b_0=c_1=4\\b_1=5c_1+5c_2=12\end{cases}\rArr\begin{cases}c_1=4\\c_2=-\frac{8}{5}\end{cases} $$
Therefore, the general solution is
$$ b_n=4\cdot5^n-\frac{8\cdot5^n\cdot n}{5}=4\cdot5^{n-1}(5-2n) $$
</aside>
<aside> 💡 (c) Correct by checked.
</aside>
Solve the recurrence $c_n=6c_{n-1}+4c_{n-2}$, subject to initial conditions $c_0=7, c_1=4$.
After you find a formula for $c_n$, check that your formula gives the correct result for $c_4$.
<aside> 💡 Since $c_n=6c_{n-1}+4c_{n-2}$, we can get the characteristic equation:
$$ r^2-6r-4=0\rArr\begin{cases}r_1=3+\sqrt{13}\\r_2=3-\sqrt{13}\end{cases}\\\text{then we have }c_n=a_1(3+\sqrt{13})^n+a_2(3-\sqrt{13})^n\\\begin{cases}c_0=7=a_1+a_2\\c_1=4=(3+\sqrt{13})a_1+(3-\sqrt{13})a_2\end{cases}\\\rArr\begin{cases}a_1=\frac{91-17\sqrt{13}}{26}\\a_2=\frac{91+17\sqrt{13}}{26}\end{cases}\\\therefore c_n=\frac{91-17\sqrt{13}}{26}(3+\sqrt{13})^n+\frac{91+17\sqrt{13}}{26}(3-\sqrt{13})^n $$
| $c_0$ | 7 |
|---|---|
| $c_1$ | 4 |
| $c_2$ | 52 |
| $c_3$ | 328 |
| $c_4$ | 2716 |
</aside>
This question examines how to find a particular solution to a non-homogeneous recurrence. We’ll solve: $a_n = 10a_{n−1} − 33a_{n−2} + 36a_{n−3} + 3C^n,$ and see how the correct form for a particular solution depends on the value of $C$.
(a) What is the characteristic equation of the corresponding homogeneous recurrence?
(b) Check by multiplication that $(x − 3)^2(x − 4) = x^3 − 10x^2 + 33x − 36$, and conclude that there is a homogeneous solution of the form $a^{(h)}_n = αn3^n + β3^n + γ4^n$
(c) Evaluate the original recurrence at $n − 1$ and multiply by $C$ (think about why we use $C$ here) to show $Ca_{n−1} = 10Ca_{n−2} − 33Ca_{n−3} + 36Ca_{n−4} + 3C^n$.
(i) Subtract this from the original recurrence and rearrange terms to find a homogeneous recurrence satisfied by $a_n$.
(ii) What is the characteristic equation of this new recurrence, and how is this related to the characteristic equation of the original recurrence?
(iii) Conclude that $a_n$ is of the form
$$ a_n =\begin{cases} αn3^n + β3^n + γ4^n + δn^23^n &\text{ if } C = 3\\ αn3^n + β3^n + γ4^n + δn4^n &\text{ if } C = 4\\ αn3^n + β3^n + γ4^n + δC^n &\text{ otherwise }\end{cases} $$
<aside> 💡 Comment: This means that there is a particular solution of the form $a^{(p)}_n = δn^23^n$ if $C = 3$, $a^{(p)}_n = δn4^n$ if $C = 4$, or $a^{(p)}_n = δC^n$ if $C\notin \{3, 4\}$. In all cases, $α, β,$ and $δ$ can be determined to match initial conditions.
Theorem 6 from section 8.2 summarizes the conclusions of this question.
(d) Using the derived formula from part (c)(iii), determine the form of the particular solution $$a^{(p)}_n$$ for $$C = 2$$. The form of $$a^{(p)}_n$$ will be the same as the general $a_n$ formula from part (c)(iii), but with $$C$$ replaced by $2$ and the coefficients $$α$$, $$β$$, $$γ$$, and $$δ$$ determined to match initial conditions.
</aside>
<aside> 💡 (a)
The characteristic equation of the corresponding homogeneous recurrence is
$$ x^3 - 10x^2 + 33x - 36 = 0 $$
</aside>
<aside> 💡 (b)
By factoring the polynomial, we get $(x-3)^2(x-4) = 0$,
which means that there is a homogeneous solution of the form
$a^{(h)}_n = αn3^n + β3^n + γ4^n$
</aside>
<aside> 💡 (c)
$\mathrm{(i)}$ By subtracting $Ca_{n-1}$ from the original recurrence, we obtain
$$ a_n - Ca_{n-1} = 10(a_{n-1} - Ca_{n-2}) - 33(a_{n-2} - Ca_{n-3}) + 36(a_{n-3} - Ca_{n-4}) $$
Rearranging terms, we get
$$ a_n = 10a_{n-1} - 33a_{n-2} + 36a_{n-3} + 3C^n + C a_{n-1} - 10C a_{n-2} + 33C a_{n-3} - 36C a_{n-4} $$
$\rm{(ii)}$ The characteristic equation is
$$ x^4-(10+C)x^3+(33+10C)x^2-(36+33C)x+36C=0\\\rArr (x-3)^2(x-4)(x-C)=0 $$
This is related to the characteristic equation of the original recurrence since this is it multiple $(x-C)$ .
$\rm{(iii)}$
case 1: if $C=3$, the characteristic equation is
$$ x^4-13x^3+63x^2-135x+108=0\rArr(x-4)(x-3)^3=0 $$
in this case, $p^n=4^n,3^n,n3^n,n^23^n$ all satisfied the original homogeneous recurrence
so $a_n=αn3^n + β3^n + γ4^n + δn^23^n$ if $C=3$.
case 2: if $C=4$, the characteristic equation is
$$ (x-4)^2(x-3)^2=0 $$
in this case, $p^n=4^n,3^n,n3^n,n4^n$ all satisfied the original homogeneous recurrence
so $a_n=αn3^n + β3^n + γ4^n + δn4^n$ if $C=4$.
other cases: $p^n=4^n,3^n,n3^n,C^n$ is the solution since $(x-C)(x-4)(x-3)^2=0$,
so $a_n=αn3^n + β3^n + γ4^n + δC^n$otherwise.
</aside>
