# A recurrence that wiggles?

Consider the following sequence $a_n$:

$a_1 = 0$

$a_n = 1 + \frac{1}{2^n-2} \sum_{i=1}^{n-1} \binom{n}{i} a_i$

The first few terms are $0,1,\frac{3}{2},\frac{13}{7},\frac{15}{7}$.

The sequence comes out of the analysis of a certain process, whose asymptotics we expect to be about $\log_2 n$. Numerical computations show that indeed $a_n \approx \log_2 n - C$, where $C \approx 0.318$. It should be easy to show that $a_n = \log_2 n + O(1)$.

Is it true that $a_n = \log_2 n - C + o(1)$ for some constant $C$?

There are some sequences defined by similar recurrence relations for which the "constant" part actually wiggles (unfortunately the reference escapes me).

-
(this may be tangential but) the "wiggle" part reminds me of an anecdote from one of Peter Winkler's books: n people stand in a circle, and each person shoots some random other person every second. What is the probability that eventually all people are dead? the answer p(n) does not tend to a limit as n tends to infinity; it surprisingly wiggles. p(n) is obviously some kind of sum over p(k) for k<n, of a form that is perhaps not very different from yours. – Alon Amit Sep 10 '10 at 5:59

This is the Erdos-Renyi "20 Questions" problem. You want to guess an integer in a set of N elements by selecting subsets and asking questions of the form "and is it in this subset?". For the question to provide information the subset cannot be empty or the entire set of uneliminated possibilities, and if an informative question (subset) is chosen at random one gets the above recursion for the expected length of the game.

Erdos and Renyi showed that the expected number of questions is $\log_2(n)$ plus a non-constant periodic function of $\log_2(n)$. I don't remember if they allowed uninformative questions, so the problem could be slightly different, but similar log-periodic behavior should appear in both versions of the problem. (added: the reason it should be the same is that the dominant $\log_2(n)$ term comes from the concentration of the size of the random subset around $k/2$ where $k$ is the number of remaining possibilities, and the log-periodic part comes from the $O(\sqrt{k})$ dispersion of the subset size near $k/2$. What happens at the very extremes of the distribution is much less influential.)

-
Does anyone know a reference for this? – Yuval Filmus Sep 10 '10 at 14:34

Not really an answer, but too long for a comment.

A recurrence with a wiggle

The following was proposed by Lennart Rade in a 1991 issue of the American Mathematical Monthly, and the solution appears in the January 1994 issue, on page 78.

Begin with $n$ fair coins all showing tails. Toss them all and pick up only the coins with tails. Repeat this procedure until all coins show heads.

The number of coins showing tails is a Markov chain that starts in state $n$ and ends up at 0. The transition probabilities are binomial: $p_{n,i}={n \choose i}\left({1\over 2}\right)^n \mbox{ for }0\leq i\leq n$.

The sequence $u_n=P_{n+1}(\mbox{chain hits }1)$ satisfies $u_0=1$ and for $n\geq1$ $$u_n=\sum_{j=0}^n{n+1\choose j}2^{-(n+1)} u_{n-j},$$ or $$u_n=\sum_{j=1}^n{n+1\choose j}{2^{-(n+1)}\over 1-2^{-(n+1)}} u_{n-j}.$$

In fact, this problem can be solved explicitly giving $$u_n={n+1\over2}\sum_{k=0}^\infty 2^{-k}(1-2^{-k})^n.$$

Analysis of this expression shows that, despite appearances, the sequence $u_n$ does not converge.

It slowly oscillates about the pseudo limit $${1\over2\ln(2)}=.72134$$ with an amplitude of about $${|\Gamma(1-2\pi i/\ln(2))|\over2\ln(2)}=.00000356.$$
It's a fun example to show students as the oscillations are invisible graphically.

For related examples see The asymptotic probability of a tie for first place, by B. Eisenberg, G. Stengle, and G. Strang, Annals of Applied Probability 3, 731-745 (1993).

-
For another example of such an analysis, search for a post by Noam Elkies on sci.math.research from January 30 2003. The title of the post is "Finite differences of 1/(B^i-A)". – Byron Schmuland Sep 10 '10 at 16:26

Noam Elkies gives an example here.

-