8
$\begingroup$

The sequence in question is the Lucas or Generalized Fibonacci sequence A088137. It's easy to write down its generating function $\frac{x}{1-2x+3x^2}$ and an explicit formula

$a_n = \frac{\sqrt{2}}{2}\mbox{Im}\left( (1+\sqrt{-2})^n\right)$.

The absolute values $|a_n|$ seem to grow quite rapidly, but I'm unable to rule out the possibility that a high power of $1+\sqrt{-2}$ will conspire to have an incredibly small argument.

Is it true that $|a_n|=1$ only for $n=1,3$?

EDIT: $a_n=-1$ never occurs and this can easily be verified by reducing mod 11.

$\endgroup$
3
  • 2
    $\begingroup$ $\frac{1}{\sqrt 2} (\sqrt 3)^n \sin n\theta$ where $\theta = \arctan \sqrt 2$. And there were extensive discussions about these type of problems. Check this math.stackexchange.com/questions/705877/an-exotic-sequence $\endgroup$ – Sungjin Kim Aug 6 '15 at 6:55
  • $\begingroup$ First part: yes, I understand the formula, but does it help answer the question? Second part: I couldn't find those discussions by searching, I'm afraid, but thanks for the link - it is fascinating. I'm not sure I can adapt the methods there to my needs but I'll try. $\endgroup$ – Alon Amit Aug 6 '15 at 7:14
  • $\begingroup$ The first part will help you understanding and applying the method by achille hui in the link. I have not thought deeply about applying Noam Elkies' method, but I believe that the method should apply. $\endgroup$ – Sungjin Kim Aug 6 '15 at 7:20
5
$\begingroup$

Method 1 - Bilu-Hanrot-Voutier theorem on Lucas sequences.

First some definitions,

  • Lucas pair - A Lucas pair is a pair $(\alpha,\beta)$ of algebraic integers such that $\alpha + \beta$ and $\alpha\beta$ are non-zero coprime rational integers and $\frac{\alpha}{\beta}$ is not a root of unity.

  • Lucas numbers - Given a Lucas pair, the corresponding sequence of Lucas numbers is the sequence defined by $$u_n = u_n(\alpha,\beta) = \frac{\alpha^n - \beta^n}{\alpha - \beta}, \quad \text{ for } n = 0, 1, 2, \ldots$$

  • Primitive divisor - Given a Lucas pair $(\alpha, \beta)$ and corresponding Lucas numbers $(u_n)$, a primitive divisor for $u_n$ is a prime divisor $p$ of $u_n$ such that $$p | u_n \quad\text{ and }\quad p \not| (\alpha-\beta)^2 u_1 u_2\dots u_{n-1}$$

In 2001, Bilu, Hanrot and Voutier has proved$\color{blue}{^{[1]}}$ in general, for any sequence of Lucas numbers $(u_n)$ and any $n > 30$, $u_n$ has a primitive divisor. As a consequence, $|u_n| > 1$ for $n > 30$.

For our sequence at hand, we have

$$a_n = \frac{\alpha^n - \beta^n}{\alpha - \beta}\quad\text{ with }\quad \begin{cases} \alpha &= 1 + \sqrt{-2}\\ \beta &= 1 - \sqrt{-2} \end{cases} $$ and it is easy to check this pair of $(\alpha,\beta)$ is a Lucas pair. This implies $|a_n| \ne 1$ for $n > 30$.

By brute force, one can verify for the remaining $n \le 30$, $|a_n| = 1$ when and only when $n = 1,3$. From this, wee can conclude $|a_n| \ne 1$ except for $n = 1, 3$.

Method 2 - Modular arithmetic.

Since OP asks for an easier approach, here is an elementary one. The idea is extracted from a paper by B.Sury$\color{blue}{^{[2]}}$ on a related equation $x^2 + 2 = y^n \color{blue}{^{[3]}}$.

The OP has handled the case $a_n = -1$ already and it is simple to check $a_n \ne \pm 1$ for small $n$ other than $n = 1,3$. We will limit our proof to the case $n > 5$ and $a_n = 1$.

Let's say there is a $n > 5$ such that

$$a_n = \sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor} (-2)^k \binom{n}{2k+1} = 1$$

Compare the parity of both sides, we get $1 = n \pmod 2$. This implies $n$ is an odd number.

Rewrite $n$ as $2^a b + 1$ where $a > 0$, $b$ odd. We will first look at everything modulo $2^{a+1}$.

Let $\nu_2 : \mathbb{Q} \to \mathbb{Z}$ be the 2-adic order of rational numbers. Notice for $k \ge 3$,
$$\nu_2(k) \le \lfloor\log_2 k \rfloor < k - 1 \quad\implies\quad \nu_2\left(\frac{2^k}{2k}\right) > 0$$ This leads to $$\nu_2\left((-2)^k \binom{n}{2k+1}\right) =\nu_2\left(\frac{(-2)^k n(n-1)}{(2k+1)(2k)}\binom{n-2}{2k-1}\right) > \nu_2(n-1) = a$$ whenever $k \ge 3$. As a result,

$$1 = a_n \equiv \sum_{k=0}^2 (-2)^k \binom{n}{2k+1} = n - 2\binom{n}{3} + 4\binom{n}{5} \pmod{2^{a+1}}\tag{*1}$$ It is not hard to see $$n \equiv 2^a + 1 \pmod {2^{a+1}}\quad\text{ and }\quad 2\binom{n}{3} = \frac{n(n-1)(n-2)}{3}\equiv 2^a \pmod {2^{a+1}}$$ For the third term, $$\begin{align} \nu_2\left(4\binom{n}{5}\right) &= \nu_2\left(\frac{n(n-1)(n-2)(n-3)(n-4)}{30}\right) = \nu_2\left(\frac{(n-1)(n-3)}{2}\right)\\ &= \nu_2\left(2^a b(2^{a-1}b - 1)\right) \quad\rightarrow\quad \begin{cases} = a,& a > 1\\ > a, &a = 1\end{cases} \end{align}\\ {\Large\Downarrow}\\ 4\binom{n}{5} \equiv \begin{cases} 2^a,& a > 1\\ 0,& a = 1\end{cases} \pmod {2^{a+1}} $$ Combine these three terms, $(*1)$ becomes

$$1 \equiv 1 + 2^a + 2^a + \begin{cases}2^a,& a > 1\\0, & a = 1\end{cases} \equiv \begin{cases} 1 + 2^a, & a > 1\\1, & a = 1\end{cases} \pmod {2^{a+1}} $$ This forces $a = 1$. As a result, $n$ has the form $2^c d + 3$ for some $c > 1$ and $d$ odd.

Next, let us look at everything modulo $2^{c+1}$. Once again, we can show that for $k \ge 3$, $$\nu_2(k(k-1)) < k - 1\quad\implies\quad \nu_2\left(\frac{2^k}{2k(k-1)}\right) > 0$$ For such $k$, we have $$\begin{align}\nu_2\left((-2)^k\binom{n}{2k+1}\right) &= \nu_2\left(\frac{(-2)^k n (n-1)(n-2)(n-3)}{(2k+1)(2k)(2k-1)(2k-2)}\binom{n-4}{2k-3}\right)\\ &= \nu_2\left(\left(\frac{2^k}{2k(k-1)}\right)\left(\frac{(2^c d + 2)(2^c d)}{2}\right) \binom{n-4}{2k-3}\right) > c \end{align} $$ As a consequence,

$$1 = a_n \equiv \sum_{k=0}^2 (-2)^k \binom{n}{2k+1} = n - 2\binom{n}{3} + 4\binom{n}{5} \pmod{2^{c+1}}\tag{*2}$$

With a little bit of algebra, one can check that

$$\begin{array}{rclcl} n &=& 2^c d + 3 &\equiv& 2^c + 3 & \pmod {2^{c+1}}\\ 2\binom{n}{3} &=& \frac13 (2^c d + 3)(2^c d + 2)(2^c d + 1) &\equiv& 2^c + 2 & \pmod {2^{c+1}}\\ 4\binom{n}{5} &=& \frac{1}{30}(2^c d + 3)(2^c d + 2)(2^c d + 1)(2^c d)(2^c d -1) &\equiv& 2^c & \pmod {2^{c+1}} \end{array}$$ This leads to a contradiction that $$1 \equiv (2^c + 3 ) - (2^c + 2) + 2^c \equiv 2^c + 1 \pmod {2^{c+1}}$$

As a result, there is no $n > 5$ such that $a_n = 1$.

Notes

  • $\color{blue}{[1]}$ Y. Bilu, G. Hanrot, P.M. Voutier, Existence of primitive divisors of Lucas and Lehmer numbers, J. Reine Angew. Math. 539 (2001), 75-122. (a copy for an earlier version can be found here)

  • $\color{blue}{[2]}$ B. Sury, On the Diophantine equation $x^2 + 2 = y^n$, Arch. Math. (Basel) 74 (2000), 350–355.

  • $\color{blue}{[3]}$ Equation of the form $x^2 + C = y^n$ is a special case of something known as Lebesgue-Nagell equation. Notice $$a_n = \frac{\alpha^n - \beta^n}{\alpha - \beta} = \pm 1 \quad\implies\quad \begin{cases} \alpha^n &= x \pm \sqrt{-2}\\ \beta^n &= x \mp \sqrt{-2} \end{cases} \quad\text{ for some } x \in \mathbb{Z}\\ {\Large\Downarrow}\\ x^2 + 2 = (x \pm \sqrt{-2})(x \mp \sqrt{-2}) = \alpha^n\beta^n = 3^n$$ Every solution of $a_n = \pm 1$ corresponds to a solution for the equation $x^2 + 2 = y^n$.

$\endgroup$
6
  • $\begingroup$ This is great, though a lot more complicated than I had expected. Do you expect there's an easier approach that doesn't insist on primitive divisors? Since I only need to show that $a_n \neq 1$ I can do with any prime divisor. $\endgroup$ – Alon Amit Aug 6 '15 at 14:42
  • $\begingroup$ @AlonAmit I suspect there are easier approach but I can't come up any right now. In any event, if we know there are no such $n$, it will help people stop wasting time to look for a counterexample. $\endgroup$ – achille hui Aug 6 '15 at 15:20
  • $\begingroup$ @AlonAmit added an elementary approach. I hope this is easier to understand. $\endgroup$ – achille hui Aug 8 '15 at 9:57
  • $\begingroup$ Great solution! By the way, the $\nu_2$ right after the downward arrow should be removed. $\endgroup$ – Sungjin Kim Aug 9 '15 at 8:47
  • $\begingroup$ @i707107 fixed that, thanks for catching that. $\endgroup$ – achille hui Aug 9 '15 at 8:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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