Alon Levy points that equation I’m interested in,

x^{2}+7=2^{n},

is called Ramanujan equation. (You *must *know who Ramanujan was.) He also gives a full solution (which I haven’t verified yet) and a link to alternative solution. I’ve checked in Alan Baker’s *Concise introduction to the theory of numbers* that indeed it was one of Ramanujan’s many conjectures that above equation has solutions only for n=3,4,5,7 and 15. It was proved by T. Nagell in 1948. (Precise references are given here.)

However, I still have an impression that something funny is going on.

*

Namely, it’s rather straightforward to verify that above has a solution for given n iff sequence b_{k} defined by

b_{1}=b_{2}=1, b_{k+2 }= b_{k+1 }– 2b_{k}

takes value +-1 for k=n-2. This sequence can be also, by a standard method, put in a closed form:

b_{k}=1/√7 ∙ (ω^{n}^{ }– ψ^{n}),

where ω and ψ are roots of X^{2}+2X-1.

So, to be happy we need to prove that |b_{k}| > 1 for k>13. ‘Till recently I thought that it’s an arithmetical problem, but yesterday I ordered my computer to give me first 5000 b_{k}‘s. This is what he gave me, on horizontal axis is *k* and on vertical is *ln**|b*_{k}*|.*

* *

Evidently, that b_{k} is rarely equal to +-1 is not a matter of hard arithmetics of **Z**[ω], but rather of the fact that |b_{k}| are roughly equal to const∙e^{k}, which rarely is a number around +-1! Still, I have a quite explicit and quite simple formula for b_{k}, a strong numerical evidence that it goes to infinity but can’t prove nothing about this sequence! Moreover, even Ramanujan apparently didn’t know much about it. This is funny :-). If you have any guts, you should try to prove that b_{k} goes to infinity by some simple method ;-).

And general question: is it true that any Fibonnaci-like sequence is either bounded or its norm goes exponentially to infinity?

*

Maxim Kontsevitch was giving a lecture today. I hope to write what I understood tomorrow.

## 6 comments

Comments feed for this article

February 8, 2007 at 2:14 pm

Alon LevyTrivially, it’s not true. Every arithmetic sequence is Fibonacci-type with the rule a(n+2) = 2a(n+1) – a(n). Less trivially, every polynomial sequence is Fibonacci-type, by letting the associated polynomial be (x – 1)^k (e.g. a(n+3) = 3a(n+2) – 3a(n+1) + a(n)).

February 9, 2007 at 2:45 pm

mirkaoho, what a nice topic! I like number theory (less I like math/cs/physics-only nerds). some easy, yet from time to time really smartly and nicely solvable number theoretical problems are here: http://www.fen.bilkent.edu.tr/~cvmath/Problem/problem.htm

just if you really get bored.

February 9, 2007 at 2:47 pm

sirixOh. Shame on me. But let’s say it’s because associated polynomial has double zero. In this case basic solutions are alfa^n and n*alfa^n (where alfa is a root of associated polynomial) so these solutions “interfere” poorly (poorly = easy to understood :-).

So my “new” question: is it true that if characteristic polynomial has two distinc roots than…

Or, to avoid any other trivialities :-), give a simple criterion of when given sequence goes to infinity exponentially (that is, there exist k>1, l> 0 such that b_n/k^n > l for almost all n).

February 18, 2007 at 2:55 am

Alon LevySorry for not checking back earlier… the growth rate of a Fibonacci-type sequence is dominated by the highest (n^k)r^n with respect to the lexicographic order on (r, k). If the highest (r, k) is unique, then the criterion is simple: you want to have |r| > 1. Otherwise, things get really muddy, because you could have a sequence like 2^n + (-2)^n, which has no limit.

February 18, 2007 at 11:43 pm

sirixAlon: Or which is what I’m really curious about…

June 17, 2007 at 6:20 pm

David SpeyerHave you seen Terry Tao’s post on the Skolem-Mahler-Lech theorem? This is about exactly this question. The really hard case is not something like 2^n+(-2)^n, where you can just pass to even and odd subsequences, but something like (3+4i)^n+(3-4i)^n. The argument of 3+4i is irrational, so this is arbitraily smaller than 5^n infinitely often without actually being zero. It turns out that this sequence only takes each integer value finitely often, and hence approaches infinity, but lower bounds are hard to come by.