How to get the Binet-form for the sequence *[1,5,45,441,4361,...]*?

Question

The sequence $[1,5,45,441,4361,...]_{k\ge 0}$ has a relatively simple recursion formula; I got for the recursion $$a_0=1, \qquad a_1=5, \qquad a_{k+2}= 10 a_{k+1} - 1 a_k - 4 $$
I have also found, that the Binet-like expression $$ f(n) = { (5+\sqrt{5^2-1})^n-(5-\sqrt{5^2-1})^n\over \sqrt{5^2-1}} $$ is related to the sequence, however I don't get the correct form - perhaps it is because of the constant term $-4$ in the recursion.

Q1: How must I proceed to get from the known recursion-formula to the correct Binet-type formula?

I have a second sequence, very similar; it is $[1, 8, 105, 1456, 20273, 282360,...]_{k \ge 0}]$ , with the recursion $$b_0=1, \qquad b_1=8, \qquad b_{k+2}= 14 b_{k+1} - 1 b_k - 6 $$

Of course I want the same type of expression here, but if I've understood the way of proceeding I surely can do it myself.

However I have a second intention, perhaps it is not at all doable by this (the problem stems from a self-study on the Pell-equation problem):

Q2: Is there a realistic option to show by this, that except for the first elements the sequences $a_k $ and $b_j$ have no more element in common?

Answer 1

Forget about the initial conditions for a while. The given inhomogeneous equation has as one of its solutions $a_n^\ast=\frac{1}{2}$. This is easily found by letting $a_i=c$ in the recurrence and solving for $c$.

The general solution of the homogeneous recurrence (get rid of the $4$) is $$A \alpha^n +B\beta^n,$$ where $\alpha$ and $\beta$ are the roots of $x^2-10x+1=0$ and $A$ and $B$ are arbitrary constants. Note that $\alpha$ and $\beta$ are close relatives close relatives of numbers in the OP. Finally, the general solution of the inhomogeneous equation is $$a_n=A\alpha^n+B\beta^n+\frac{1}{2}.$$ To find $A$ and $B$, use the initial conditions $a_0=1$, $a_1=5$.

Remark: The same technique will work for the second sequence $(b_n)$. The question about common elements is interesting, and may be difficult. I would guess that the closed forms for $(a_n)$ and $(b_n)$ will not help to answer the question.

Answer 2

$$a_{k+2}-\alpha a_{k+1}-\beta = (10-\alpha)a_{k+1}-a_k - 4-\beta$$ $$\alpha=\frac1{10-\alpha}\space,\space\beta=\alpha(4+\beta)$$ $$\alpha^2-10\alpha+1=0\space,\space\beta=\frac{4\alpha}{1-\alpha}$$ $$a_{k+2}-\alpha a_{k+1}-\beta = \frac1{\alpha}(a_{k+1}-\alpha a_k - \beta)$$ $$a_{k+1}-\alpha a_{k}-\beta=\left(\frac1{\alpha}\right)^k(a_1-a_0-\beta)$$ $$\alpha(a_{k}-\alpha a_{k-1}-\beta)=\alpha\left(\frac1{\alpha}\right)^{k-1}(a_1-a_0-\beta)$$ $$\dots$$ $$\alpha^k(a_{1}-\alpha a_{0}-\beta)=\alpha^k\left(\frac1{\alpha}\right)^{0}(a_1-a_0-\beta)$$ Adding side by side: $$a_{k+1}-\alpha^{k+1}a_0-\frac{1-\alpha^{k+1}}{1-\alpha}\beta=\frac{1}{\alpha^k}(1+\alpha^2+\cdots+\alpha^{2k})(a_1-a_0-\beta)=\frac{1-\alpha^{2k+2}}{\alpha^{k}(1-\alpha^2)}(a_1-a_0-\beta)$$ $$\therefore a_k=\alpha^ka_0+\frac{1-\alpha^{k}}{1-\alpha}\beta+\frac{1-\alpha^{2k}}{\alpha^{k-1}(1-\alpha^2)}(a_1-a_0-\beta)$$