I have this recurrence relation that I've been trying to solve,
$$g_m = g_{m-1} + a_m \, g_{m-2}$$
with $g_1=g_0=1$ and $m\geq 0$. Here, $a_m$ is the $m$-th term of a known sequence. Any ideas?
If it helps, $a_m= \frac{1}{L^2}(m-1)(r-m+2)$ where $L^2 \in \mathbb{Z}, L^2 \neq0 $, $r \in \mathbb{N}_0$ and $r \geq |L|$, but other than that, $L$ and $r$ are free. So, if I were to be extremely precise, $g_m$ and $a_m$ would actually be $g_{mrL}$ and $a_{mrL}$.
Brute-forcing the problem reveals a pattern, but I don't see how to write it in closed form. Perhaps someone with greater pattern-recognition skills than mine could see a closed form:
- $g_2 = 1 + a_2$
- $g_3 = 1 + a_2 + a_3$
- $g_4= 1 + a_2 + a_3 + a_4 + a_2 a_4$
- $g_5= 1 + a_2+ a_3+a_4+a_5+a_2a_4+a_2a_5+a_3a_5$
- $g_6= 1 + a_2+ a_3+a_4+a_5+a_6+a_2a_4+a_2a_5+a_2a_6+a_3 a_5 + a_3 a_6 + a_4 a_6 + a_2 a_4 a_6 $
- $g_7= 1 + a_2+ a_3+a_4+a_5+a_6+ a_7 + a_2 a_4 + a_2 a_5 + a_2 a_6 + a_2 a_7 + a_3 a_5 + a_3 a_6 +a_3 a_7 + a_4 a_6 + a_4 a_7 + a_5 a_7 + a_2 a_4 a_6 + a_2 a_4 a_7 + a_2 a_5 a_7 + a_3 a_5 a_7$
- $g_8 = 1 + a_2 + a_3 + a_4 + a_5 +a_6 + a_7 + a_8 + a_2 a_4 + a_2 a_5 + a_2 a_6 + a_2 a_7 + a_2 a_8 +a_3 a_5 + a_3 a_6 + a_3 a_7 + a_3 a_8 + a_4 a_6 + a_4 a_7 +a_4 a_8 + a_5 a_7 + a_5 a_8 + a_6 a_8 + a_2 a_4 a_6 + a_2 a_4 a_7+a_2 a_4 a_8 + a_2 a_5 a_7 + a_2 a_5 a_8 + a_2 a_6 a_8 + a_3 a_5 a_7 + a_3 a_5 a_8 + a_3 a_6 a_8 + a_4 a_6 a_8 + a_2 a_4 a_6 a_8$
You can often rewrite these problems like: \begin{equation} \begin{bmatrix} g_m\\g_{m-1} \end{bmatrix} = \begin{bmatrix} 1&a_m\\1&0 \end{bmatrix} \begin{bmatrix} g_{m-1}\\g_{m-2} \end{bmatrix} \end{equation}
In vector and matrix notation, this becomes: $$G_m = A_m G_{m-1}$$
For example, $a_m=1$ would provide the Fibonacci numbers, for $g_0=g_1=1$.
If $A_m$ doesn't depend on $m$ then you can diagonalize it and get an explicit answer (by multiplying it $n$ times): $$G_m = PD^nP^{-1} G_0$$
If $a_m$ is more general then it's not obvious if this works.