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