On the distribution of distances in recursive trees

Recursive trees have been used to model such things as the spread of epidemics, family trees of ancient manuscripts, and pyramid schemes. A tree T-n with n labeled nodes is a recursive tree if n=1, or n>1 and T-n can be constructed by joining node n to a node of some recursive tree T-n-1. For arbitrary nodes i<n in a random recursive tree we give the exact distribution of X(i,n), the distance between nodes i and n. We characterize this distribution as the convolution of the law of X(i,i+1) and n-i-1 Bernoulli distributions. We further characterize the law of X(i,i+1) as a mixture of sums of Bernoullis. For i=i(n) growing as a function of n, we show that X(in,n) is asymptotically normal in several settings.