Vtyjkyuk

I was thinking of a problem and have an answer through computer programming, but am unable to prove it mathematically. Start with the following:
$$frac12bigg(frac12 + frac13bigg)approx 0.41666$$
Replace every unit fraction being summed in the parentheses (in this case, the inner 1/2 and 1/3) with
$$frac1nbigg(frac12 + frac13 + ... + frac1n+1bigg)$$
where $n$ is the denominator of the unit fraction. If we apply this process once, we get
$$frac12bigg(frac12bigg(frac12 + frac13bigg)+frac13bigg(frac12 + frac13+frac14bigg)bigg)approx 0.3888$$
and if we apply it again, we get
$$frac12bigg(frac12bigg(frac12bigg(frac12 + frac13bigg) + frac13bigg(frac12 + frac13+ frac14bigg)bigg)+frac13bigg(frac12bigg(frac12 + frac13bigg) + frac13bigg(frac12 + frac13+ frac14bigg)+frac14bigg(frac12 + frac13+ frac14+ frac15bigg)bigg)bigg)approx 0.37754$$

As we repeat this process, the result seems to approach $e^-1$.

If anyone could prove this or direct me to a proof of this, that would be wonderful!

Consider the following random process:

• Start with a natural number $n_0$.


• Choose a new number $n_1$ from $2,3,ldots,n_0+1$ uniformly at random.


• Choose a new number $n_2$ from $2,3,ldots,n_1+1$ uniformly at random.

and repeat for however many steps. Your expression is $mathbb E[1/n_k]$ - that is, it is the expected value of $1/n_k$. This is a Markov process and we can apply our typical analysis tools to it*.

In particular, as $k$ increases, irrespective of our starting position, the distribution of $n_k$ approaches a unique steady state distribution - that is, a distribution invariant under the step.

Let $p_m$ be the probability that, for large $k$ (i.e. in the limit), we have $n_k=m$. It must be a steady state in the sense that
$$p_m=sum_ell=m-1^inftyfrac1ellcdot p_ell$$
which just says that, if we started in this distribution, we would stay in it.

Now, we can construct a probability generating function for the steady state; we'll mess up the indexing slightly for convenience. Let:
$$f(x)=p_2x+p_3x^2+p_4x^3+ldots.$$
Note that we can use formal integration to get
$$int_0^x f(t),dt=fracp_22x^2+fracp_33x^3+ldots$$
Then, noting $frac11-x=1+x+x^2+ldots$ and slipping in an extra $x$ for fun, we can define a new function $g(x)$ as follows:
$$g(x)=fracxint_0^x f(t),dt1-x=fracp_22x^3+left(fracp_22+fracp_33right)x^4+left(fracp_22+fracp_33+fracp_44right)x^5+ldots.$$
Why do this? Because if we let $C=fracp_22+fracp_33+ldots$ - that is, $C$ is exactly the quantity we're looking for - we note that
$$fracCx1-x-g(x)=sum_m=1^inftysum_ell=m^inftyfrac1ellcdot p_ellcdot x^m$$
Which we recognize as $f(x)$. Thus, we get an equation:
$$(1-x)f(x)=Cx-xint_0^x f(t),dt$$
Now, I'll leave out the details, because I'm not good at calculus, but if you differentiate both sides of the equation twice, you get a degree two differential equation, and if you plug it into Mathematica, you get a solution:
$$f(x)=c_1cdot xe^x+c_2cdot frace+xe^xoperatornameEi(x)e$$
where $c_1,c_2$ are as of yet unknown constants. However, we know that $f(0)=0$ from definition of $f$ and $f(1)=1$ since $p_2+p_3+ldots=1$ since these are probabilities. This fixes $c_2=0$ and $c_1=frac1e$.

Thus $f(x)=frac1exe^x$. This looks promising already! Then, observe that $int_0^1 f(t),dt=C=mathbb E[1/n]$ just by looking at the series we derived earlier for the integral! So, then we just integrate that expression and we see $C=1/e$. Hurray! It worked! As a bonus, we know the steady state probabilities are just $p_n=frac1e(n-2)!$ for $2leq n$.

(*I'm ignoring convergence issues, which are relevant since this Markov chain has infinitely many states. The generating function stuff can be justified after the fact, despite involving serious convergence problems - uniqueness of a solution is not so hard to establish - the usual argument of uniqueness and existence of a steady state still gives us uniqueness for infinite Markov processes - and the fact that $f(x)=frac1exe^x$ is a solution is also not too hard to show. Convergence of the chain to its steady state brings more serious issues - I think they can be solved by bounding the probability that $n_k$ is large, which shouldn't be too hard, since the probability that $n_k+1>n_k$ given $n_k$ is just $frac1n_k$)

We provide a recurrence relation for the numbers converging to $frac1e$. We start with some introductory aspects.

Representation via sums

We denote the elements of the sequence which are iteratively generated by OPs rule with $alpha_n, ngeq 2$ and derive for small $n$

beginalign*
alpha_2&=frac12\
alpha_3&=frac12sum_j_1=2^3frac1j_1tagi\
&=frac12left(frac12+frac13right)=frac512=0,41dot6\
alpha_4&=frac12sum_j_1=2^3frac1j_1sum_j_2^j_1+1frac1j_2tagii\
&=frac12left(frac12sum_j_2=2^3frac1j_2+frac13sum_j_2=2^4frac1j_2right)\
&=frac12left(frac12left(frac12+frac13right)+frac13left(frac12+frac13+frac14right)right)
=frac718=0,3dot8\
alpha_5&=frac12sum_j_1=2^3frac1j_1sum_j_2^j_1+1frac1j_2sum_j_3=2^j_2+1frac1j_3tagiii\
&=frac12left(frac12sum_j_2=2^3frac1j_2sum_j_3=2^j_2+1frac1j_3+frac13sum_j_2=2^4frac1j_2sum_j_3=2^j_2+1frac1j_3right)\
&=frac12left(frac12left(frac12sum_j_3=2^3frac1j_3+frac13sum_j_3=2^4frac1j_3right)right.\
&qquad left.+frac12left(frac12sum_j_3=2^3frac1j_3+frac13sum_j_3=2^4frac1j_3+frac14sum_j_3=2^5frac1j_3right)right)\
&=frac12left(frac12left(frac12left(frac12+frac13right)+frac13left(frac12+frac13+frac14right)right)right.\
&qquadleft.+frac13left(frac12left(frac12+frac13right)+frac13left(frac12+frac13+frac14right)
+frac14left(frac12+frac13+frac14+frac15right)right)right)\
&=frac1,6314,320=0,377,54overline629
endalign*
in accordance with OP's calculation.

From (i),(ii),(iii) we obtain for general $n$:
beginalign*
colorbluealpha_n=frac12sum_j_1=2^3frac1j_1sum_j_2=2^j_1+1frac1j_2sum_j_3=2^j_2+1frac1j_3
cdotssum_j_n-2=2^j_n-3+1frac1j_n-2sum_j_n-1=2^j_n-2+1frac1j_n-1qquadqquad ngeq 3tag1
endalign*

Note: The ubiquitous Catalan numbers occur here also. If we write $alpha_n$ as
beginalign*
alpha_2&=frac12,&C_1=1\
alpha_3&=frac1colorblue2cdot 2+frac1colorblue2cdot 3,&C_2=2tag2\
alpha_4&=frac1colorblue2cdot 2cdot 2+frac1colorblue2cdot 2cdot 3+frac1colorblue2cdot 3cdot 2+frac1colorblue2cdot 3cdot 3+frac1colorblue2cdot 3cdot 4,&C_3=5\
& ,vdots
endalign*
we see the number of summands of $alpha_n$ is $C_n-1$. The blue marked factors in $alpha_n$ come from the factors of $alpha_n-1$.

Recurrence relation

In order to find a recurrence relation we would like to reverse the order of summation in (1). Alas this is somewhat cumbersome since the upper limit of an inner sum does not nicely correspond with the lower limit of the next outer sum. We will instead show the relationship with the help of number triangles which might also provide additional insight
$$
beginarraycccc
n&w_alpha_2&w_alpha_3&w_alpha_4&w_alpha_5\
hline\
5&&&&frac15\\
4&&&frac14&frac14\\
3&&frac13&frac13&frac13\\
2&frac12&frac12&frac12&frac12\
\
hline\
\
endarray
qquadqquadqquad
beginarrayr
n&alpha_2&alpha_3&alpha_4&alpha_5\
hline\
5&&&&frac1120\\
4&&&frac14&frac12288\\
3&&frac16&frac536&frac754\\
2&frac12&frac14&frac524&frac736\
\
hline\
alpha_n&frac12&frac512&frac718&frac1,6314,320
endarray
$$

The left table shows a triangular region of weights $frac12,frac13,ldots$ with weight $frac1n$ in row $n$. These weights are used to build the entries in the right table and $alpha_n$ which is the sum of the entries in the $n$-th column. We denote rows and columns starting from $2$ so that the bottom left-most element is $a_22=frac12$ while the top right-most element is $a_55=frac15!=frac1120$. We have
beginalign*
colorbluealpha_2&=a_22colorblue=frac12\
colorbluealpha_3&=a_32+a_33\
&=frac12a_22+frac13a_22\
&=frac14+frac16colorblue=frac512\
colorbluealpha_4&=a_42+a_43+a_44\
&=frac12left(a_32+a_33right)+frac13left(a_32+a_33right)+frac14a_33\
&=frac524+frac536+frac124colorblue=frac718\
colorbluealpha_5&=a_52+a_53+a_54+a_55\
&=frac12left(a_42+a_43+a_44right)+frac13left(a_42+a_43+a_44right)
+frac14left(a_43+a_44right)+frac15a_55\
&=frac736+frac754+frac13288+frac1120colorblue=frac1,6314,320
endalign*

From the calculations above we derive the rule to build the entries $a_k,l$:

• Take $frac1k$ times the sum of all entries of column $k-1$ and row greater or equal $maxl-1,2$.




• The recurrence relation is
  beginalign*
  a_n,j&=frac1jsum_k=maxj-1,2^n-1a_n-1,kqquadqquadqquadqquadqquad ngeq 3,j=2,ldots,n\
  colorbluealpha_2&colorblue=frac12\
  colorbluealpha_n&=sum_j=2^na_n,jcolorblue=sum_j=2^nfrac1jsum_k=maxj-1,2^n-1a_n-1,kqquadqquad ngeq 3,j=2,ldots,ntag3
  endalign*

We can show the validity of (3) by successively applying the recurrence relation to obtain
beginalign*
colorbluealpha_n&=sum_j_1=2^na_n,j_1\
&=sum_j_1=2^nfrac1j_1sum_j_2=maxj_1-1,2^n-1a_n-1,j_2\
&=sum_j_1=2^nfrac1j_1sum_j_2=maxj_1-1,2^n-1frac1j_2sum_j_3=maxj_2-1,2^n-2a_n-2,j_3\
& ,vdots\
&=sum_j_1=2^nfrac1j_1sum_j_2=maxj_1-1,2^n-1frac1j_2
cdotssum_j_n-2=maxj_n-3-1,2^3frac1j_n-2sum_j_n-1=maxj_n-2-1,2^2a_2,j_n-1\
&,,colorblue=frac12sum_j_1=2^nfrac1j_1sum_j_2=maxj_1-1,2^n-1frac1j_2
cdotssum_j_n-2=maxj_n-3-1,2^3frac1j_n-2tag3
endalign*
and (3) is the same as (1) with the summation in reverse order.

Notes:

• It is interesting, that summing up the columns in the right table above gives a monotonically increasing sequence converging to $frac1e$.
  beginalign*
  lim_ntoinfty alpha_n=frac1e
  endalign*
  What I find amazing is the usage of the weights $frac1j$ used in the expression of $alpha_n$ (see e.g. (2)) which makes them similar looking to
  beginalign*
  sum_j=0^n(-1)^jfrac1j!
  endalign*
  but without the alternating sign.




• It would be great if someone could show the convergence of $(alpha_n)$ by solving the recurrence relation (3).




• It might be interesting that the same structure of the recurrence relation (3) but with different weights, namely $n-1$ instead of $frac1n$ and different boundary values $a_2,n=1$ instead of $frac12$ and $a_n,n=n-1$ instead of $frac1n$ is archived as A185423 in OEIS denoting the number of Ordered forests of $k$ increasing plane unary-binary trees with $n$ nodes.
  $$
  beginarraycccc
  n&&&&\
  hline\
  5&&&&3\\
  4&&&3&3\\
  3&&2&2&2\\
  2&1&1&1&1\
  endarray
  qquadqquadqquad
  beginarrayr
  A185423&&&&\
  hline\
  5&&&&24\\
  4&&&6&36\\
  3&&2&6&30\\
  2&1&1&3&9\
  endarray
  $$