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.

$\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$ 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$ 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$ 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$ 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$ Nov 6, 2014 at 20:00

1 Answer 1

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).

$\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$ 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$ Nov 7, 2014 at 7:36
  • $\begingroup$ By the factorization a_n is composite, except for finite exceptions? $\endgroup$
    – joro
    Nov 7, 2014 at 8:57
  • $\begingroup$ @joro: indeed both factors diverge, and satisfy a linear recurrence $\endgroup$ Nov 7, 2014 at 9:06
  • $\begingroup$ @PietroMajer Indeed. so a_n is the product of two lower order recurrences. $\endgroup$
    – joro
    Nov 7, 2014 at 9:17

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.