Does recursively replacing $\frac1n$ by $\frac1n(\frac12+\dots+\frac1{n+1})$ really converge to $\frac1e$?

Liam Lutton 08/17/2018. 2 answers, 445 views
real-analysis sequences-and-series convergence

I was thinking of a problem and have an answer through computer programming, but am unable to prove it mathematically. Start with the following: $$\frac{1}{2}\bigg(\frac{1}{2} + \frac{1}{3}\bigg)\approx 0.41666$$ Replace every unit fraction being summed in the parentheses (in this case, the inner 1/2 and 1/3) with $$\frac{1}{n}\bigg(\frac{1}{2} + \frac{1}{3} + ... + \frac{1}{n+1}\bigg)$$ where $n$ is the denominator of the unit fraction. If we apply this process once, we get $$\frac{1}{2}\bigg(\frac{1}{2}\bigg(\frac{1}{2} + \frac{1}{3}\bigg)+\frac{1}{3}\bigg(\frac{1}{2} + \frac{1}{3}+\frac{1}{4}\bigg)\bigg)\approx 0.3888$$ and if we apply it again, we get $$\frac{1}{2}\bigg(\frac{1}{2}\bigg(\frac{1}{2}\bigg(\frac{1}{2} + \frac{1}{3}\bigg) + \frac{1}{3}\bigg(\frac{1}{2} + \frac{1}{3}+ \frac{1}{4}\bigg)\bigg)+\frac{1}{3}\bigg(\frac{1}{2}\bigg(\frac{1}{2} + \frac{1}{3}\bigg) + \frac{1}{3}\bigg(\frac{1}{2} + \frac{1}{3}+ \frac{1}{4}\bigg)+\frac{1}{4}\bigg(\frac{1}{2} + \frac{1}{3}+ \frac{1}{4}+ \frac{1}{5}\bigg)\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!

2 Answers

Milo Brandt 08/18/2018.

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}^{\infty}\frac{1}{\ell}\cdot 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=\frac{p_2}2x^2+\frac{p_3}3x^3+\ldots$$ Then, noting $\frac{1}{1-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)=\frac{x\int_0^x f(t)\,dt}{1-x}=\frac{p_2}2x^3+\left(\frac{p_2}2+\frac{p_3}3\right)x^4+\left(\frac{p_2}2+\frac{p_3}3+\frac{p_4}4\right)x^5+\ldots.$$ Why do this? Because if we let $C=\frac{p_2}2+\frac{p_3}3+\ldots$ - that is, $C$ is exactly the quantity we're looking for - we note that $$\frac{Cx}{1-x}-g(x)=\sum_{m=1}^{\infty}\sum_{\ell=m}^{\infty}\frac{1}{\ell}\cdot p_{\ell}\cdot x^m$$ Which we recognize as $f(x)$. Thus, we get an equation: $$(1-x)f(x)=Cx-x\int_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_1\cdot xe^x+c_2\cdot \frac{e+xe^x\operatorname{Ei}(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=\frac{1}e$.

Thus $f(x)=\frac{1}exe^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=\frac{1}{e(n-2)!}$ for $2\leq 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)=\frac{1}exe^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 $\frac{1}{n_k}$)

Markus Scheuer 08/19/2018.

We provide a recurrence relation for the numbers converging to $\frac{1}{e}$. 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, n\geq 2$ and derive for small $n$

\begin{align*} \alpha_2&=\frac{1}{2}\\ \alpha_3&=\frac{1}{2}\sum_{j_1=2}^3\frac{1}{j_1}\tag{i}\\ &=\frac{1}{2}\left(\frac{1}{2}+\frac{1}{3}\right)=\frac{5}{12}=0,41\dot{6}\\ \alpha_4&=\frac{1}{2}\sum_{j_1=2}^3\frac{1}{j_1}\sum_{j_2}^{j_1+1}\frac{1}{j_2}\tag{ii}\\ &=\frac{1}{2}\left(\frac{1}{2}\sum_{j_2=2}^3\frac{1}{j_2}+\frac{1}{3}\sum_{j_2=2}^4\frac{1}{j_2}\right)\\ &=\frac{1}{2}\left(\frac{1}{2}\left(\frac{1}{2}+\frac{1}{3}\right)+\frac{1}{3}\left(\frac{1}{2}+\frac{1}{3}+\frac{1}{4}\right)\right) =\frac{7}{18}=0,3\dot{8}\\ \alpha_5&=\frac{1}{2}\sum_{j_1=2}^3\frac{1}{j_1}\sum_{j_2}^{j_1+1}\frac{1}{j_2}\sum_{j_3=2}^{j_2+1}\frac{1}{j_3}\tag{iii}\\ &=\frac{1}{2}\left(\frac{1}{2}\sum_{j_2=2}^3\frac{1}{j_2}\sum_{j_3=2}^{j_2+1}\frac{1}{j_3}+\frac{1}{3}\sum_{j_2=2}^4\frac{1}{j_2}\sum_{j_3=2}^{j_2+1}\frac{1}{j_3}\right)\\ &=\frac{1}{2}\left(\frac{1}{2}\left(\frac{1}{2}\sum_{j_3=2}^3\frac{1}{j_3}+\frac{1}{3}\sum_{j_3=2}^4\frac{1}{j_3}\right)\right.\\ &\qquad \left.+\frac{1}{2}\left(\frac{1}{2}\sum_{j_3=2}^3\frac{1}{j_3}+\frac{1}{3}\sum_{j_3=2}^4\frac{1}{j_3}+\frac{1}{4}\sum_{j_3=2}^5\frac{1}{j_3}\right)\right)\\ &=\frac{1}{2}\left(\frac{1}{2}\left(\frac{1}{2}\left(\frac{1}{2}+\frac{1}{3}\right)+\frac{1}{3}\left(\frac{1}{2}+\frac{1}{3}+\frac{1}{4}\right)\right)\right.\\ &\qquad\left.+\frac{1}{3}\left(\frac{1}{2}\left(\frac{1}{2}+\frac{1}{3}\right)+\frac{1}{3}\left(\frac{1}{2}+\frac{1}{3}+\frac{1}{4}\right) +\frac{1}{4}\left(\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}\right)\right)\right)\\ &=\frac{1\,631}{4\,320}=0,377\,54\overline{629} \end{align*} in accordance with OP's calculation.

From (i),(ii),(iii) we obtain for general $n$: \begin{align*} \color{blue}{\alpha_n=\frac{1}{2}\sum_{j_1=2}^3\frac{1}{j_1}\sum_{j_2=2}^{j_1+1}\frac{1}{j_2}\sum_{j_3=2}^{j_2+1}\frac{1}{j_3} \cdots\sum_{j_{n-2}=2}^{j_{n-3}+1}\frac{1}{j_{n-2}}\sum_{j_{n-1}=2}^{j_{n-2}+1}\frac{1}{j_{n-1}}\qquad\qquad n\geq 3}\tag{1} \end{align*}

Note: The ubiquitous Catalan numbers occur here also. If we write $\alpha_n$ as \begin{align*} \alpha_2&=\frac{1}{2},&C_1=1\\ \alpha_3&=\frac{1}{\color{blue}{2}\cdot 2}+\frac{1}{\color{blue}{2}\cdot 3},&C_2=2\tag{2}\\ \alpha_4&=\frac{1}{\color{blue}{2\cdot 2}\cdot 2}+\frac{1}{\color{blue}{2\cdot 2}\cdot 3}+\frac{1}{\color{blue}{2\cdot 3}\cdot 2}+\frac{1}{\color{blue}{2\cdot 3}\cdot 3}+\frac{1}{\color{blue}{2\cdot 3}\cdot 4},&C_3=5\\ &\ \,\vdots \end{align*} 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 $$ \begin{array}{r|cccc} n&w_{\alpha_2}&w_{\alpha_3}&w_{\alpha_4}&w_{\alpha_5}\\ \hline\\ 5&&&&\frac{1}{5}\\\\ 4&&&\frac{1}{4}&\frac{1}{4}\\\\ 3&&\frac{1}{3}&\frac{1}{3}&\frac{1}{3}\\\\ 2&\frac{1}{2}&\frac{1}{2}&\frac{1}{2}&\frac{1}{2}\\ \\ \hline\\ \\ \end{array} \qquad\qquad\qquad \begin{array}{r|rrrr} n&\alpha_2&\alpha_3&\alpha_4&\alpha_5\\ \hline\\ 5&&&&\frac{1}{120}\\\\ 4&&&\frac{1}{4}&\frac{12}{288}\\\\ 3&&\frac{1}{6}&\frac{5}{36}&\frac{7}{54}\\\\ 2&\frac{1}{2}&\frac{1}{4}&\frac{5}{24}&\frac{7}{36}\\ \\ \hline\\ \alpha_n&\frac{1}{2}&\frac{5}{12}&\frac{7}{18}&\frac{1\,631}{4\,320} \end{array} $$

The left table shows a triangular region of weights $\frac{1}{2},\frac{1}{3},\ldots$ with weight $\frac{1}{n}$ 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}=\frac{1}{2}$ while the top right-most element is $a_{55}=\frac{1}{5!}=\frac{1}{120}$. We have \begin{align*} \color{blue}{\alpha_2}&=a_{22}\color{blue}{=\frac{1}{2}}\\ \color{blue}{\alpha_3}&=a_{32}+a_{33}\\ &=\frac{1}{2}a_{22}+\frac{1}{3}a_{22}\\ &=\frac{1}{4}+\frac{1}{6}\color{blue}{=\frac{5}{12}}\\ \color{blue}{\alpha_4}&=a_{42}+a_{43}+a_{44}\\ &=\frac{1}{2}\left(a_{32}+a_{33}\right)+\frac{1}{3}\left(a_{32}+a_{33}\right)+\frac{1}{4}a_{33}\\ &=\frac{5}{24}+\frac{5}{36}+\frac{1}{24}\color{blue}{=\frac{7}{18}}\\ \color{blue}{\alpha_5}&=a_{52}+a_{53}+a_{54}+a_{55}\\ &=\frac{1}{2}\left(a_{42}+a_{43}+a_{44}\right)+\frac{1}{3}\left(a_{42}+a_{43}+a_{44}\right) +\frac{1}{4}\left(a_{43}+a_{44}\right)+\frac{1}{5}a_{55}\\ &=\frac{7}{36}+\frac{7}{54}+\frac{13}{288}+\frac{1}{120}\color{blue}{=\frac{1\,631}{4\,320}} \end{align*}

From the calculations above we derive the rule to build the entries $a_{k,l}$:

  • Take $\frac{1}{k}$ times the sum of all entries of column $k-1$ and row greater or equal $\max\{l-1,2\}$.

  • The recurrence relation is \begin{align*} a_{n,j}&=\frac{1}{j}\sum_{k=\max\{j-1,2\}}^{n-1}a_{n-1,k}\qquad\qquad\qquad\qquad\qquad n\geq 3,j=2,\ldots,n\\ \color{blue}{\alpha_2}&\color{blue}{=\frac{1}{2}}\\ \color{blue}{\alpha_n}&=\sum_{j=2}^na_{n,j}\color{blue}{=\sum_{j=2}^n\frac{1}{j}\sum_{k=\max\{j-1,2\}}^{n-1}a_{n-1,k}\qquad\qquad n\geq 3,j=2,\ldots,n}\tag{3} \end{align*}

We can show the validity of (3) by successively applying the recurrence relation to obtain \begin{align*} \color{blue}{\alpha_n}&=\sum_{j_1=2}^na_{n,j_1}\\ &=\sum_{j_1=2}^n\frac{1}{j_1}\sum_{j_2=\max\{j_1-1,2\}}^{n-1}a_{n-1,j_2}\\ &=\sum_{j_1=2}^n\frac{1}{j_1}\sum_{j_2=\max\{j_1-1,2\}}^{n-1}\frac{1}{j_2}\sum_{j_3=\max\{j_2-1,2\}}^{n-2}a_{n-2,j_3}\\ &\ \,\vdots\\ &=\sum_{j_1=2}^n\frac{1}{j_1}\sum_{j_2=\max\{j_1-1,2\}}^{n-1}\frac{1}{j_2} \cdots\sum_{j_{n-2}=max\{j_{n-3}-1,2\}}^{3}\frac{1}{j_{n-2}}\sum_{j_{n-1}=\max\{j_{n-2}-1,2\}}^{2}a_{2,j_{n-1}}\\ &\,\,\color{blue}{=\frac{1}{2}\sum_{j_1=2}^n\frac{1}{j_1}\sum_{j_2=\max\{j_1-1,2\}}^{n-1}\frac{1}{j_2} \cdots\sum_{j_{n-2}=max\{j_{n-3}-1,2\}}^{3}\frac{1}{j_{n-2}}}\tag{3} \end{align*} and (3) is the same as (1) with the summation in reverse order.


  • It is interesting, that summing up the columns in the right table above gives a monotonically increasing sequence converging to $\frac{1}{e}$. \begin{align*} \lim_{n\to\infty} \alpha_n=\frac{1}{e} \end{align*} What I find amazing is the usage of the weights $\frac{1}{j}$ used in the expression of $\alpha_n$ (see e.g. (2)) which makes them similar looking to \begin{align*} \sum_{j=0}^n(-1)^j\frac{1}{j!} \end{align*} 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 $\frac{1}{n}$ and different boundary values $a_{2,n}=1$ instead of $\frac{1}{2}$ and $a_{n,n}=n-1$ instead of $\frac{1}{n}$ is archived as A185423 in OEIS denoting the number of Ordered forests of $k$ increasing plane unary-binary trees with $n$ nodes. $$ \begin{array}{r|cccc} n&&&&\\ \hline\\ 5&&&&3\\\\ 4&&&3&3\\\\ 3&&2&2&2\\\\ 2&1&1&1&1\\ \end{array} \qquad\qquad\qquad \begin{array}{r|rrrr} A185423&&&&\\ \hline\\ 5&&&&24\\\\ 4&&&6&36\\\\ 3&&2&6&30\\\\ 2&1&1&3&9\\ \end{array} $$ - Download Hi-Res Songs

1 The Chainsmokers

Beach House flac

The Chainsmokers. 2018. Writer: Andrew Taggart.
2 (G)I-DLE


(G)I-DLE. 2018. Writer: Riot Music Team;Harloe.
3 Ariana Grande

​Thank U, Next flac

Ariana Grande. 2018. Writer: Crazy Mike;Scootie;Victoria Monét;Tayla Parx;TBHits;Ariana Grande.
4 Anne-Marie

Rewrite The Stars flac

Anne-Marie. 2018. Writer: Benj Pasek;Justin Paul.
5 Clean Bandit

Baby flac

Clean Bandit. 2018. Writer: Jack Patterson;Kamille;Jason Evigan;Matthew Knott;Marina;Luis Fonsi.
6 Nicki Minaj

No Candle No Light flac

Nicki Minaj. 2018. Writer: Denisia “Blu June” Andrews;Kathryn Ostenberg;Brittany "Chi" Coney;Brian Lee;TJ Routon;Tushar Apte;ZAYN;Nicki Minaj.
7 BlackPink

Kiss And Make Up flac

BlackPink. 2018. Writer: Soke;Kny Factory;Billboard;Chelcee Grimes;Teddy Park;Marc Vincent;Dua Lipa.
8 Imagine Dragons

Bad Liar flac

Imagine Dragons. 2018. Writer: Jorgen Odegard;Daniel Platzman;Ben McKee;Wayne Sermon;Aja Volkman;Dan Reynolds.

Waste It On Me flac

BTS. 2018. Writer: Steve Aoki;Jeff Halavacs;Ryan Ogren;Michael Gazzo;Nate Cyphert;Sean Foreman;RM.
10 Halsey

Without Me flac

Halsey. 2018. Writer: Halsey;Delacey;Louis Bell;Amy Allen;Justin Timberlake;Timbaland;Scott Storch.
11 Little Mix

Woman Like Me flac

Little Mix. 2018. Writer: Nicki Minaj;Steve Mac;Ed Sheeran;Jess Glynne.
12 Brooks

Limbo flac

Brooks. 2018.
13 Fitz And The Tantrums

HandClap flac

Fitz And The Tantrums. 2017. Writer: Fitz And The Tantrums;Eric Frederic;Sam Hollander.
14 Backstreet Boys

Chances flac

Backstreet Boys. 2018.
15 Lady Gaga

I'll Never Love Again flac

Lady Gaga. 2018. Writer: Benjamin Rice;Lady Gaga.
16 Diplo

Close To Me flac

Diplo. 2018. Writer: Ellie Goulding;Savan Kotecha;Peter Svensson;Ilya;Swae Lee;Diplo.
17 Rita Ora

Velvet Rope flac

Rita Ora. 2018.
18 Bradley Cooper

Always Remember Us This Way flac

Bradley Cooper. 2018. Writer: Lady Gaga;Dave Cobb.
19 Imagine Dragons

Machine flac

Imagine Dragons. 2018. Writer: Wayne Sermon;Daniel Platzman;Dan Reynolds;Ben McKee;Alex Da Kid.
20 Erika Sirola

Speechless flac

Erika Sirola. 2018. Writer: Teemu Brunila;Stefan Dabruck;Jürgen Dohr;Guido Kramer;Dennis Bierbrodt;Chris Braide;Robin Schulz.

Related questions

Hot questions


Popular Tags