If $a_{n+1} = u a_n+v a_{n-1}$, what recurrence does $a_{n+1}a_n$ satisfy?

Question

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.

Answer 1

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.

Answer 2

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$.