Finding a recursion

Question

I am supposed to find a recursion for the following sequence: $$a_{n} = (1+\sqrt{s})^{n} + (1-\sqrt{s})^{n}$$ where $s \in \mathbb{N}$ fixed. I tried playing around with it using the binomial theorem, however, I was not able to find a solution! I'd greatly appreciate help/hints/solutions! Thanks in advance

Answer 1

$$\begin{align}a_{n+2}&=(1+\sqrt s)^{n+2}+(1-\sqrt s)^{n+2}\\&=(1+\sqrt s)^n(1+\sqrt s)^2+(1-\sqrt s)^n(1-\sqrt s)^2\\&=(1+\sqrt s)^n(1+2\sqrt s+s)+(1-\sqrt s)^n(1-2\sqrt s+s)\\&=(1+\sqrt s)^n(2(1+\sqrt s)+s-1)+(1-\sqrt s)^n(2(1-\sqrt s)+s-1)\\&=2(1+\sqrt s)^{n+1}+(s-1)(1+\sqrt s)^{n}+2(1-\sqrt s)^{n+1}+(s-1)(1-\sqrt s)^n\\&=2a_{n+1}+(s-1)a_{n}\end{align}$$

Answer 2

Lemma: if $a_{n}=Ax^n+By^n$,then we have $$a_{n+2}=(x+y)a_{n+1}-xya_{n}$$ It is clear

Answer 3

$a_n$ is the trace of the matrix $M^n$, where $M$ is the companion matrix of the polynomial: $$ p(t) = (t-1-\sqrt{s})(t-1+\sqrt{s}) = t^2-2t+(1-s)\tag{1}$$ hence the Cayley-Hamilton theorem applied to: $$ a_n = \text{Tr}\left(\begin{array}{cc}0 & s-1\\ 1 & 2 \end{array}\right)^n \tag{2}$$ gives:

$$ a_{n+2} = 2\, a_{n+1} + (s-1)\, a_n. \tag{3} $$