2
$\begingroup$

Let $(a_n)$ be the A001921 sequence

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

Let $(b_k)$ be the (almost)"tower-of-squares" sequence defined by

$$ b_0=2, \quad b_{k+1}=2b_k^2-1 $$

Is it true that $a_{2^kn+2^{k-1}-1}$ is always divisible by $b_k$, for any $k,n\geq 0$ ?

I have checked this up to $k=6$. For example :

  • $a_{2n}$ is always divisible by $b_0=2$.

  • $a_{4n+1}$ is always divisible by $b_1=7$.

  • $a_{8n+3}$ is always divisible by $b_2=97$.

  • Etc. Up to : $a_{128n+65}$ is always divisible by $b_6=2011930833870518011412817828051050497$.

    This is a cross-post from a MSE question.

Improve this question
$\endgroup$
9
  • $\begingroup$ Does any enlightenment occur when you write the a-recurrence in matrix form? Gerhard "Or Maybe Tilt Your Head" Paseman, 2014.11.06 $\endgroup$
    – Gerhard Paseman
    Commented Nov 6, 2014 at 18:28
  • $\begingroup$ @GerhardPaseman When I write $X_n=(1,a_n,a_{n+1})$ and $X_{n+1}=\left(\begin{array}{ccc} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 6 & -1 & 14 \end{array}\right)X_n$, no flash occurs in my brain. But maybe I am being blind on this one … $\endgroup$
    – Ewan Delanoy
    Commented Nov 6, 2014 at 19:46
  • $\begingroup$ OK. I was thinking 2x2 matrices with a' = (6 0) + Aa, and then calling this operation Va and trying V iterated to a high power. I haven't followed it up though. Gerhard "Maybe Smaller Will Be Better" Paseman, 2014.11.06 $\endgroup$
    – Gerhard Paseman
    Commented Nov 6, 2014 at 19:56
  • $\begingroup$ @GerhardPaseman The closed-form formula for $a_n$ is of the form $-\frac{1}{2}+c(7- 4\sqrt{3})^n+d(7+ 4\sqrt{3})^n$. Not very helpful for integer divisibility properties it seems $\endgroup$
    – Ewan Delanoy
    Commented Nov 6, 2014 at 20:00
  • 1
    $\begingroup$ Some thoughts that can be helpful: 1) you perhaps prefer to consider the sequence $d_n=2a_n+1$, as it satisfies a homogeneous linear recurrence $d_{n+1}=14d_n-d_{n-1}$ -- and prove the congruence to 1 modulo the sequence $c_n=2b_n$ ; 2) for the latter, the recurrence relation is also simplified: $c_{n+1}=c_n^2-2$. 3) It would be natural to expect that $A^{2^n}=id$ mod $c_n$, where $A=\left(\begin{smallmatrix} 14 & -1 \\ 1 & 0 \end{smallmatrix}\right) $ is the corresponding transition matrix. $\endgroup$
    – Victor Kleptsyn
    Commented Nov 6, 2014 at 20:00

1 Answer 1

Reset to default
10
$\begingroup$

The elements of your sequence are $$a_n=\left(\frac{\alpha^n-\beta^n}{2\sqrt{3}}\right)\left(\frac{\alpha^{n+1}+\beta^{n+1}}{2}\right)$$ where $\alpha=2+\sqrt{3}$ and $\beta=2-\sqrt{3}$. Notice that both factors are integers. We can also compute that $$b_n=\frac{\alpha^{2^n}+\beta^{2^n}}{2}.$$ Now your statement that $b_k$ always divides $a_{2^{k+1}n+2^k-1}$ follows from the fact that $\frac{\alpha^{2^k}+\beta^{2^k}}{2}$ divides $\frac{\alpha^{2^k(2n+1)}+\beta^{2^k(2n+1)}}{2}$, which is very easy to check (the ratio is a polynomial in $\alpha, \beta$ and symmetric in both).

Improve this answer
$\endgroup$
5
  • $\begingroup$ Very nice. May I ask how you discovered the factorization of $a_n$ ? Did you use some sort of systematic method ? $\endgroup$
    – Ewan Delanoy
    Commented Nov 7, 2014 at 7:32
  • $\begingroup$ I think I see already : the initial recurrence has eigenvalues that happen to be fourth powers. So, one looks for factor sequences that satisfy a reccurence whose eigenvalues are the fourth roots of the initial roots. $\endgroup$
    – Ewan Delanoy
    Commented Nov 7, 2014 at 7:36
  • $\begingroup$ By the factorization a_n is composite, except for finite exceptions? $\endgroup$
    – joro
    Commented Nov 7, 2014 at 8:57
  • $\begingroup$ @joro: indeed both factors diverge, and satisfy a linear recurrence $\endgroup$
    – Pietro Majer
    Commented Nov 7, 2014 at 9:06
  • $\begingroup$ @PietroMajer Indeed. so a_n is the product of two lower order recurrences. $\endgroup$
    – joro
    Commented Nov 7, 2014 at 9:17

You must log in to answer this question.

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