If $a_{n}$ is a prime number, is $n$ is also a prime number?

Question

Let $a_{n}$ be the $n^\text{th}$ term of a sequence. Let $a_{n}$ be defined as follows:

$$a_n=\begin{cases} 1 & n = 1 \\ 2 & n = 2 \\ 2a_{n-1}+a_{n-2} & n \ge 3 \end{cases}$$

Can we say that "if $a_{n}$ is a prime number, then $n$ is also a prime number"?

Answer 1

Hint $ $ Just as here they are a strong divisibility sequence, i.e. $\,\gcd(a_m,a_n) = a_{\gcd(m,n)}.\,$ In particular $\, m\mid n\,\Rightarrow\, a_m\mid a_n,\,$ so $\,n\,$ composite $\,\Rightarrow\, a_n\,$ composite so, contra+, $\, a_n\,$ prime $\,\Rightarrow\, n\,$ prime.

Answer 2

Here is an outline of a proof that if $m|n$ then $a_m|a_n;$ from there, it is easy to argue your claim.

Let $n=km.$ It suffices to show $a_m|a_{km}$ for $k=2$ and $k$ odd.

As alluded in comments, $a_n=\dfrac{\alpha^n-\dfrac1{(-\alpha)^n}}{2\sqrt2}$, where $\alpha=1+\sqrt2$.

Define another sequence $b_n$ the same way as $a_n$ except $b_2=3$. Then $b_n=\dfrac{\alpha^n+\dfrac1{(-\alpha)^n}}{2}.$

It is easy to show that $a_{2m}=2a_mb_m$; thus $a_m|a_{2m},$ and we are done with the case $\dfrac nm=2$.

To prove $a_m|a_{(2l-1)m},$ use strong induction on $l$.

The base case ($l=1$) is trivial.

Now assume $a_m|a_{(2i-1)m}$ for $i=1$ to $l.$ To show $a_m|a_{(2l+1)m}$,

note $a_m^{2l+1}=\left(\dfrac{\alpha^m+\dfrac{(-1)^{m+1}}{\alpha^m}}{2\sqrt2}\right)^{2l+1}=\dfrac{\left(\alpha^m+\dfrac{(-1)^{m+1}}{\alpha^m}\right)^{2l+1}}{2^{3l}2\sqrt2}.$

Therefore, using the binomial expansion, $2^{3l}a_m^{2l+1}=\dfrac{\left(\alpha^{m(2l+1)}-\dfrac1{(-\alpha)^{m(2l+1)}}\right)}{2\sqrt2}+...$

$=a_{m(2l+1)}+ $ sum of terms that are binomial coefficients times $a_{(2i-1)m}, 1\le i\le l.$

The left side of this equation $(2^{3l}a_m^{2l+1})$ is a multiple of $a_m$,

and the sum of terms is a multiple of $a_m$ (due to the induction hypothesis),

so $a_{m(2l+1)}$ is a multiple of $a_m$.

Answer 3

Let $S$ be the shift operator on sequences ($Sa_n=a_{n+1})$. Then $$ (S^2-2S-1)a_n=0\tag1 $$ By induction, we also have $$ \left(S^{2k}-d_kS^k+(-1)^k\right)a_n=0\tag2 $$ where $d_k$ is defined by $d_0=2$, $d_1=2$, $d_k=2d_{k-1}+d_{k-2}$. Furthermore, by induction on $m$, $$ \left(S^{km}-e_{k,m}S^k+(-1)^ke_{k,m-1}\right)a_n=0\tag3 $$ where $e_{k,m}$ is defined by $e_{k,0}=0$, $e_{k,1}=1$, $e_{k,m}=d_ke_{k,m-1}-(-1)^ke_{k,m-2}$. Then, since $a_0=0$, $$ a_{km}=e_{k,m}a_k\tag4 $$ Thus, if $k\mid n$, then $a_k\mid a_n$. Contrapositive, if $a_n$ is prime, then $n$ is prime.

Answer 4

If your'e as unfamiliar with this material as I am, you might find this 'foray' into Bill Dubuque's matrix techniques a useful way of putting your toe in the water.

Monkey see, monkey do (just scratching the surface):

$$ A_n := \begin{bmatrix} a_{n+1} &\!\! a_{n}\\ a_{n} &\!\!\! a_{n-1}\end{bmatrix} = \begin{bmatrix}2 &1\\ 1 & 0\end{bmatrix}^n\! =\, A_1^n $$

$$\,A_{m+n} = A_1^{m+n} = A_1^m A_1^n = A_m A_n,\ $$

$$\ a_{m+n} =\, a_{m+1} a_n +a_m a_{n-1}$$

Divisibility Example:

$ a_6 \;= a_4 a_3 + a_3 a_2$
$ a_9 \;= a_7 a_3 + a_6 a_2$
$ a_{12} = a_{10} a_3 + a_9 a_2$
etc.

So $a_3 \mid a_{3k}$ for all $k \ge 1$.

With this example in mind, a proof can be constructed showing that whenever $\, m\mid n$,
it must follow that $\, a_m\mid a_n$.

---

It is of interest to compare this sequence to the topic

Generating all coprime pairs

The OP's sequence corresponds to using $\text{[Branch 2]}$ to define a recursion that starts with $(2,1)$.
So any two adjacent terms $a_n$ and $a_{n+1}$ are coprime.