If $a_{n+1} = u a_n+v a_{n-1}$, what recurrence does $a_{n+1}a_n$ satisfy? If $a_{n+1} = u a_n+v a_{n-1}$
, what recurrence does $a_{n+1}a_n$ satisfy?
You can assume that
$u^2+4v > 0$.
A starter question,
which I have done some work on:
If $a_{n+1} = 3 a_n - a_{n-1}$
, what recurrence does $a_{n+1}a_n$ satisfy?
My results show that,
if $d_n = a_{n+1}a_n$
for this particular recurrence,
$d_{n+1} = 7 d_n - d_{n-1} + c$
where $c$ is a constant depending
on $a_0$ and $a_1$.
I am currently working on
deriving the general recurrence
and the form of $c$,
but it is enough of a pain
that I have decided to
ask the question at this point.
For extra credit,
find the recurrence that
$a_n^2$ satisfies.
I have no idea what the answer is.
 A: Consider the characteristic equation $X^2 - uX - v$, which has roots $\alpha, \beta$. We have $\alpha+\beta = u$ and $\alpha\beta = -v$. Then the general solution is $a_n = A \alpha^n + B \beta^n$, where $A, B$ depend on the initial values $a_o, a_1$.
Hence, $d_n=a_n a_{n+1} = A^2 \alpha^{2n+1} + AB\alpha^n\beta^n(\alpha + \beta) + B^2 \beta^{2n+1} = (A^2\alpha) (\alpha^2)^n + AB(-v)^nu + (B^2\beta)(\beta^2) ^n $
Hence $d_n$ satisfies the characteristic equation $X^3 + UX^2 + VX+W$, where $ U = -(\alpha^2 + \beta^2-v) = - (u^2 +v)$ and $V = \alpha^2\beta^2+(-v)\alpha^2  + \beta^2(-v) = v^2 - v(u^2+2v)=-v^2-u^2v$ and $W = - \alpha^2\beta^2 \times (-v) = v^3$.
If $v = -1$, then we can get a recurrence relation for $d_n-ABu$, similar to the above method. This reduces the terms it to 2 terms, like what OP has above.
A: Here's a way to do it without the general solution.  Write your original
recurrence as
$$X_{n+1} = U X_{n}\ \text{where}\ X_n = \pmatrix{a_{n+1}\cr a_n\cr},\
U = \pmatrix{u & v\cr 1& 0\cr}$$
Now if $s_{n} = a_n^2$ and $d_n = a_{n+1} a_n$, take $$Y_n = X_n X_n^T = \pmatrix{s_{n+1} & d_n\cr d_n & s_n\cr}$$
We have $Y_{n+1} = X_{n+1} X_n^T = U X_n X_n^T U^T = U Y_n U^T$
which says $$\eqalign{s_{n+2} &= u^2 s_{n+1}+2 u v d_n+v^2 s_n\cr
      d_{n+1} &= u s_{n+1}+v d_n\cr}$$
Solve the second equation for $s_{n+1}$ and substitute (with corresponding expressions for $s_n$ and $s_{n+2}$ into the first, and after some simplification I get
$$ d_{n+2} =  (u^2 + v) d_{n+1} + (u^2 v + v^2) d_n - v^3 d_{n-1} $$
Similarly, solve the first equation for $d_n$ and substitute in the second, and you should get the same third-order recurrence for $s$. 
