$a_n = u^n+v^n+(-1)^n$

Question

Anyone has solutions for this problem?
Let $u, v$ are distinct roots of equation: $$x^2-tx+1=0 (t \in \mathbb{N}, t>2)$$ and sequence $$(a_n): a_n = u^n+v^n+(-1)^n$$ Prove that: $$a_{3^m}\mid a_{3^mn} \forall m,n \in \mathbb{N} , gcd(n,3)=1$$ Notes
$S_n=\frac{a_{3^mn}}{a_{3^m}}\\$
$a=u^{3^m}$ then $\frac{1}{a}=v^{3^m}$
+If $n$ is odd
$$S_n = \frac{a^{2n}-a^n+1}{a^{n-1}(a^2-a+1)}$$
Because $gcd(n,6)=1$, polynomial $a^{2n}-a^n+1$ is divided by $a^2-a+1$, then $\frac{a^{2n}-a^n+1}{a^2-a+1}$ is a symmetric polynomial with degree $2(n-1)$
So $S_n=\sum\limits_{i=0}^{n-1}s_i(a^i+\frac{1}{a^i})$
+If $n$ is even, then $n=2^tn'$
$S_n = S_{n'}.a_{\frac{n}{2}}a_{\frac{n}{4}}...a_{\frac{n}{2^t}}$

Answer 1

By either using Vieta's formulas or just expanding $(x - u)(x - v) = x^2 - tx + 1$ and comparing coefficients, we get

$$\begin{equation}\begin{aligned} u + v & = t \\ uv & = 1 \end{aligned}\end{equation}\tag{1}\label{eq1A}$$

For non-negative integers $i$, define $f_i(t)$ to be $u^i + v^i$ expressed as a function of $t$. Thus, $f_0(t) = u^0 + v^0 = 2$ and $f_1(t) = u + v = t$. For any $i \ge 2$, using \eqref{eq1A}, we get

$$\begin{equation}\begin{aligned} (u^{i-1} + v^{i-1})(u + v) & = u^{i} + u^{i-1}(v) + v^{i-1}(u) + v^{i} \\ t(f_{i-1}(t)) & = u^{i} + v^{i} + uv(u^{i-2} + v^{i-2}) \\ t(f_{i-1}(t)) & = f_{i}(t) + f_{i-2}(t) \\ f_{i}(t) & = t(f_{i-1}(t)) - f_{i-2}(t) \end{aligned}\end{equation}\tag{2}\label{eq2A}$$

This confirms $u^{i} + v^{i}$, for all $i \ge 0$, can be expressed as a polynomial in $t$ with integral coefficients and, thus, is an integer. Next, for any odd positive integer $j$, your sequence gives

$$a_j = u^j + v^j - 1 \tag{3}\label{eq3A}$$

For conciseness, with any integer $k \ge 0$, let

$$w_k = u^{kj} + v^{kj} \tag{4}\label{eq4A}$$

With $k = 0$ and $k = 1$, we get

$$\begin{equation}\begin{aligned} & w_0 = u^{0} + v^{0} = 1 + 1 \equiv 2 \pmod{a_j} \\ & w_1 = u^{j} + v^{j} \equiv 1 \pmod{a_j} \end{aligned}\end{equation}\tag{5}\label{eq5A}$$

For $k \ge 2$,

$$\begin{equation}\begin{aligned} (u^{(k-1)j} + v^{(k-1)j})((u^j + v^j) - 1) & \equiv 0 \pmod{a_j} \\ u^{kj} + u^{(k-1)j}(v^{j}) + v^{(k-1)j}(u^j) + v^{kj} & \equiv u^{(k-1)j} + v^{(k-1)j} \pmod{a_j} \\ u^{kj} + v^{kj} + (uv)^{j}(u^{(k-2)j} + v^{(k-2)j}) & \equiv w_{k-1} \pmod{a_j} \\ w_{k} + (u^{(k-2)j} + v^{(k-2)j}) & \equiv w_{k-1} \pmod{a_j} \\ w_k & \equiv w_{k-1} - w_{k-2} \pmod{a_j} \end{aligned}\end{equation}\tag{6}\label{eq6A}$$

This therefore gives

$$\begin{equation}\begin{aligned} & w_2 \equiv w_1 - w_0 \equiv 1 - 2 \equiv -1 \pmod{a_j} \\ & w_3 \equiv w_2 - w_1 \equiv -1 - 1 \equiv -2 \pmod{a_j} \\ & w_4 \equiv w_3 - w_2 \equiv -2 - (-1) \equiv -1 \pmod{a_j} \\ & w_5 \equiv w_4 - w_3 \equiv -1 - (-2) \equiv 1 \pmod{a_j} \\ & w_6 \equiv w_5 - w_4 \equiv 1 - (-1) \equiv 2 \pmod{a_j} \\ & w_7 \equiv w_6 - w_5 \equiv 2 - 1 \equiv 1 \pmod{a_j} \end{aligned}\end{equation}\tag{7}\label{eq7A}$$

Due to \eqref{eq6A} showing $w_k$ depends only on the previous $2$ smaller indice values, then since $w_6 \equiv w_0 \pmod{a_j}$ and $w_7 \equiv w_1 \pmod{a_j}$, the congruence values will repeat cyclically with a period of $6$. Thus, using \eqref{eq5A} and \eqref{eq7A}, for all non-negative integers $r$,

$$\begin{equation}\begin{aligned} & a_{(6r)j} \equiv w_0 + 1 \equiv 3 \pmod{a_j} \\ & a_{(6r + 1)j} \equiv w_1 - 1 \equiv 0 \pmod{a_j} \\ & a_{(6r + 2)j} \equiv w_2 + 1 \equiv 0 \pmod{a_j} \\ & a_{(6r + 3)j} \equiv w_3 - 1 \equiv -3 \pmod{a_j} \\ & a_{(6r + 4)j} \equiv w_4 + 1 \equiv 0 \pmod{a_j} \\ & a_{(6r + 5)j} \equiv w_5 - 1 \equiv 0 \pmod{a_j} \end{aligned}\end{equation}\tag{8}\label{eq8A}$$

For all $n \in \mathbb{N}$ with $\gcd(n, 3) = 1$, \eqref{eq8A} shows $a_{nj} \equiv 0 \pmod{a_j} \implies a_j \mid a_{nj}$. Since $j$ was any odd positive integer, this includes your question's specific case of $j = 3^m$. In addition, apart from the one case of $t = 4$ and $j = 1$, since in all other cases $a_j \gt 1$ and $a_j \neq 3$, we also have for $\gcd(n, 3) = 3$ that $a_{j} \not\mid a_{nj}$.