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
    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
    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
    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
    Jan 5, 2015 at 10:30
  • $\begingroup$ Linear recurrences with constant coefficients are closed under multiplication. In general this increases the order. $\endgroup$
    – joro
    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
    Jan 6, 2015 at 2:36
  • $\begingroup$ @GerryMyerson In the answer in the linked question: $\alpha=2+\sqrt{3}$. $\endgroup$
    – joro
    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
    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
    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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.