1
$\begingroup$

This question deals with sequence:

$$a_0 = 0,\ a_1 = 7, \quad a_{n+2} = 14a_{n+1} - a_n + 6$$

The question is about establishing that $a_n$ is a composite number (except some finite cases).

In one of the comments to @Gjergji Zaimi's answer, @joro said:

So $a_n$ is the product of two lower order recurrences.

I am not clear on how this conclusion is reached. Also, I would like to see some recurrent formula in different form than original, that illustrates this.

This is interesting to me since I work on some other problems involving primality, and understanding this approach may greately help me.

I appreciate your help.

Improve this question
$\endgroup$
9
  • 3
    $\begingroup$ Just consider Gjergji Zaimi's formula: each factor is a linear combination of $n$-th powers of $\alpha$ and $\beta$, which are roots of $x^2-4x+1$. So both factors satisfy the same linear recurrence, $f_{n+2}-4f_{n+1}+f_n=0$, just as $\alpha^n$ and $\beta^n$ do. $\endgroup$
    – Pietro Majer
    Commented Jan 5, 2015 at 10:21
  • $\begingroup$ $a_2$ is even. So all next $a_n$ for $n\ge 2$ are even too and so composite. $\endgroup$
    – Sergei
    Commented Jan 5, 2015 at 10:25
  • $\begingroup$ @PietroMajer, the quoted statement is that the sequence is a product of two lower order recurrences. I interpret this as both factors satisfying a first order recurrence relation. Or does lower order mean something else here? $\endgroup$
    – Joonas Ilmavirta
    Commented Jan 5, 2015 at 10:25
  • 1
    $\begingroup$ I think expression "lower order" is confusing, I will delete it from the title. @JoonasIlmavirta $\endgroup$
    – VividD
    Commented Jan 5, 2015 at 10:30
  • $\begingroup$ Linear recurrences with constant coefficients are closed under multiplication. In general this increases the order. $\endgroup$
    – joro
    Commented Jan 5, 2015 at 10:34

2 Answers 2

Reset to default
3
$\begingroup$

From Gjergji Zaimi's answer:

$$ a_n=\left(\frac{\alpha^n-\beta^n}{2\sqrt{3}}\right)\left(\frac{\alpha^{n+1}+\beta^{n+1}}{2}\right)$$.

Both factors are integers and satisfy binary recurrences.

Experimentally the first is https://oeis.org/A001353 and the second is https://oeis.org/A001075.

Numerical data supports this.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Where $\alpha$ and $\beta$ are....? $\endgroup$
    – Gerry Myerson
    Commented Jan 6, 2015 at 2:36
  • $\begingroup$ @GerryMyerson In the answer in the linked question: $\alpha=2+\sqrt{3}$. $\endgroup$
    – joro
    Commented Jan 6, 2015 at 6:01
  • $\begingroup$ Much better, I think, if symbols are explained in situ, rather than by going somewhere else on the page and then to some other page. $\endgroup$
    – Gerry Myerson
    Commented Jan 6, 2015 at 14:30
  • $\begingroup$ @GerryMyerson Thank you, agree with you. This was written in a hurry and currently don't feel like popping the question to the front page... $\endgroup$
    – joro
    Commented Jan 6, 2015 at 15:13
1
$\begingroup$

Look, I want to use the most standard approach: we have $$ X_{n+1}=\begin{pmatrix} a_{n+2} \\ a_{n+1} \end{pmatrix} = \begin{pmatrix} 14&-1 \\ 1&0 \end{pmatrix} \begin{pmatrix} a_{n+1} \\ a_{n} \end{pmatrix} +\begin{pmatrix} 6 \\ 0 \end{pmatrix} =\mathcal A X_n + b,\quad X_0=\begin{pmatrix} 7 \\ 0 \end{pmatrix}. $$ The matrix $\mathcal A$ is invertible and $b=\begin{pmatrix} 6 \\ 0 \end{pmatrix}$. We have thus with an arbitrary vector $c\in \mathbb R^2$, $$ X_{n+1}+c=\mathcal A \bigl(X_n + \mathcal A^{-1}(b+c)\bigr), $$ and we may choose that $c$ such that $ c=\mathcal A^{-1}(b+c), $ i.e. $ (\mathcal A-I)c= b $ which is (uniquely) possible since $1$ is not an eigenvalue of $\mathcal A$. With $Y_n=X_n+c$, we have thus $$ Y_{n+1}=\mathcal A Y_n\Longrightarrow Y_{n}=\mathcal A^n Y_0. $$ The eigenvalues of $\mathcal A$ are (real and) distinct, so we have with a diagonal $\mathcal D$ $$ \mathcal A=P\mathcal D P^{-1}\Longrightarrow\mathcal A^n=P\mathcal D^n P^{-1}, $$ making everything completely explicit.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .