What methods can I use, beyond simple recursion, for computing recurrence relations of the form:
$s_1 = A$
$s_2 = B$
$s_n = s_{n-2}s_{n-1}$
where A and B are strings and n is given?
This is a disorder of the Fibonacci word, for which there is a closed form to determine the $n^{th}$ digit. How would I go about finding the closed form on the $n^{th}$ digit for my recurrence?
If $A$ or $B$ equals zero then $s_n=0$ for all $n\ge 2$. Otherwise we can assume that $s_n=(-1)^{\varepsilon_n} e^{t_n}$ for all $n$.
Depending of the signs $\varepsilon_1$ and $\varepsilon_2$ of $A$ and $B$, respectively, the sequence $\varepsilon_n$ is one of the four sequences of period $3$ below $$1,1,1,1,1,1,\dots$$ $$1,-1,-1,1,-1,-1,\dots$$ $$-1,1,-1,-1,1,-1,\dots$$ $$-1,-1,1,-1,-1,1,\dots$$
The sequence $\{t_n\}$ satisfies an order two homogeneous linear recurrence $t_{n}=t_{n-1}+t_{n-2}$ with constant coefficients, which can be solved by via the standard way. We obtain, $t_n=C_1\varphi^{n}+ C_2\varphi^{n}$, where $\varphi=\tfrac{\sqrt{5}+1}2$ is a golden ration which is a root of the characteristic equation of the recurrence and $C_1$ and $C_2$ are constants which can be found from the following system of linear equations. $$\cases{C_1\varphi+C_2\varphi^{-1}=\ln|A|\\ C_1\varphi^2+e^C_2\varphi^{-2}=\ln |B|}.$$
That is $$C_1=\varphi^{-1} \ln |B|-\varphi^{-2}\ln|A|,$$
$$C_2=\varphi^2\ln |A|-\varphi\ln|B|.$$