Revisiting an earlier question

David Wilson davidwwilson at comcast.net
Fri Mar 28 17:41:59 CET 2008


This has to do with sequences, and arguably belongs in math-fun, but I'm not 
sure I'm still a member.

At any rate, not long ago I posed the following question:

Let there be two integer sequences S and T exhibiting exponential growth. 
Should we expect their intersection to be finite or infinite?

I remember that someone argued the intersection should be infinite, which 
argument I took at face value and never analyzed, and unfortunately I did 
not save the message. However, I am at the moment convinced that the 
intersection should be finite, and here is my argument:

Let log(n) be the natural logaritm of n. Suppose S grows as a^n and T as b^n 
(a, b > 1). Then there are about n elements of S <= a^n, hence about 
log(n)/log(a) elements <= n, so the probability that n is in S is about 1/(n 
log(a)). Simiarly, the probability that n is in T is about 1/(n log(b)). 
Assuming S and T are probabilistically independent, the probability that n 
is in S intersect T is about 1/(log(a) log(b) n^2). This means that S and T 
should share about pi^2/(6 log(a) log(b)) elements, and their intersection 
should be finite.

Obviously sketchy, but any glaring problems?






More information about the SeqFan mailing list