Consider the following second-order recurrence relation and its characteristic polynomial Delta(x) : a_{n}=sa_{n-1}+ta_{n-2} 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 solution 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.