Sonsider the following second-order recurrence relation and its characteristic polynomial \( \Delta(x) \) : \[ a_{n}=s a_{n-1}+t a_{n-2} \text { and } \Delta(x)=x^{2}-s x-r \] (a) Suppose \( p(n) \) and \( q(n) \) are solutions of (*). Show that, for any constants \( c_{1} \) and \( c_{2}, c_{1} p(n)+c_{2} q(n) \) is also a solutior of (*). (b) Suppose \( r \) is a root of \( \Delta(x) \). Show that \( a_{n}=r^{n} \) is a solution to (*). (c) Suppose \( r \) is a double root of \( \Delta(x) \). Show that: (i) \( s=2 r \) and \( t=-r^{2} \); (ii) \( a_{n}=n r^{n} \) is also a root of (*).

To show that \( c_1 p(n) + c_2 q(n) \) is a solution, we can start by noting that both \( p(n) \) and \( q(n) \) satisfy the recurrence relation: \( p(n) = s p(n-1) + t p(n-2) \) and \( q(n) = s q(n-1) + t q(n-2) \). By applying linearity, we have: \[ c_1 p(n) + c_2 q(n) = c_1 (s p(n-1) + t p(n-2)) + c_2 (s q(n-1) + t q(n-2)) = s(c_1 p(n-1) + c_2 q(n-1)) + t(c_1 p(n-2) + c_2 q(n-2)), \] which confirms that \( c_1 p(n) + c_2 q(n) \) is indeed a solution to the recurrence relation. Now, let's consider when \( r \) is a root of \( \Delta(x) \), meaning \( \Delta(r) = r^2 - s r - t = 0 \). We propose that \( a_n = r^n \) is a solution. Substituting \( a_n = r^n \) into the original recurrence gives us \[ r^n = s r^{n-1} + t r^{n-2} \implies r^n - s r^{n-1} - t r^{n-2} = 0, \] which simplifies to \( r^2 - s r - t = 0 \) confirming \( a_n = r^n \) as a valid solution. Next, if \( r \) is a double root, it implies the characteristic polynomial can be expressed as \( (x - r)^2 = x^2 - 2 r x + r^2 \), thus matching up with \( \Delta(x) \) gives us \( s = 2r \) and \( t = -r^2 \). When substituting \( a_n = n r^n \) into the recurrence, we compute: \[ a_n = n r^n, \quad a_{n-1} = (n-1) r^{n-1}, \quad a_{n-2} = (n-2) r^{n-2}, \] \[ a_n = s a_{n-1} + t a_{n-2} \Rightarrow n r^n = 2r (n-1) r^{n-1} - r^2(n-2) r^{n-2}. \] Through simplification, both sides yield \( n r^n \), confirming that \( n r^n \) is indeed a valid solution as well.