The limit of an averaging sequence

Consider this sequence of length $n$: $P_n=(p_0,p_1,p_2,\dots ,p_{n-1})$, where $p_0=2$, and each time the next number $p_k$ can be any number within $[2,1+p_{k-1}]$ for $k\in [1,n-1]$. Consider the set of all such sequences of length $n$, $\{P_n\}$. The first few sets are:
$$\begin{array}{rl}n=1:& (2)\\ n=2:& (2,2),(2,3)\\ n=3:& (2,2,2),(2,2,3),(2,3,2),(2,3,3),(2,3,4)\\ n=4:& (2,2,2,2),(2,2,2,3),(2,2,3,2),(2,2,3,3),(2,2,3,4),(2,3,2,2),(2,3,2,3),(2,3,3,2),\\ & (2,3,3,3),(2,3,3,4),(2,3,4,2),(2,3,4,3),(2,3,4,4),(2,3,4,5)\end{array}$$
Let $P_{nj}$ be any path in $\{P_n\}$, and $\prod P_{nj}$ be the product of all the numbers in that path. The question is, what is this limit: ${\text{lim}}_{n\to \mathrm{\infty }}\sum _{P_{nj}\in \{P_n\}}(\prod P_{nj}{)}^{-1}$?

The first few sums are

$$\begin{array}{cc}n=1:& \frac{1}{2}\\ n=2:& \frac{1}{2}\frac{1}{2}+\frac{1}{2}\frac{1}{3}\\ n=3:& \frac{1}{2}\frac{1}{2}\frac{1}{2}+\frac{1}{2}\frac{1}{2}\frac{1}{3}+\frac{1}{2}\frac{1}{3}\frac{1}{2}+\frac{1}{2}\frac{1}{3}\frac{1}{3}+\frac{1}{2}\frac{1}{3}\frac{1}{4}\end{array}$$


Answer:
The limit is $e^{-1}$.


How do you prove that it converges to this value?



This question is inspired by this stackexchange post. The original form of the question and the proof is in the following:


The original sequence:
Consider this initial sequence, $f(0,k)={\delta }_{0k},k=0,\dots ,\mathrm{\infty }$, where $\delta$ is the Kronecker delta.

Next, we define $f(n,k)=\frac{1}{k+2}\sum _{i=0}^{k+1}f(n-1,i)$, which is the average of the first $k+2$ numbers in the previous sequence. Thus, the first few sequences are,

$$1,0,0,0,\dots$$
$$\frac{1}{2},\frac{1}{3},\frac{1}{4},\dots$$
$$\frac{5}{12},\frac{13}{36},\frac{77}{240},\dots$$

The question is, what is ${\text{lim}}_{n\to \mathrm{\infty }}f(n,0)$?
(This is why I decided to call it "The averaging sequence".)


Other forms:
If we write the sequence as a vector $v_n$, the vector of the next sequence is the previous one multiplied by a matrix $M$, $v_{n+1}=M{v}_n$, where
$$M=\left[\begin{array}{ccccccc}\frac{1}{2}& \frac{1}{2}& 0& 0& 0& 0& \dots \\ \frac{1}{3}& \frac{1}{3}& \frac{1}{3}& 0& 0& 0& \dots \\ \frac{1}{4}& \frac{1}{4}& \frac{1}{4}& \frac{1}{4}& 0& 0& \dots \\ \frac{1}{5}& \frac{1}{5}& \frac{1}{5}& \frac{1}{5}& \frac{1}{5}& 0& \dots \\ & & & \dots & & & \end{array}\right]$$
We start from the vector $v_0=(1,0,0,\dots )$, thus the first element of $v_n$ is just the top left element of $M^n$. Thus the question becomes if ${\text{lim}}_{n\to \mathrm{\infty }}[M^n{]}_{00}=e^{-1}$.


Another way to see it is thinking backwards. Consider the first element of the $n$th sequence. It equals $\frac{1}{2}$ of the sum of the first two elements of the $(n-1)$th sequence. We can continue to write it as the weighted sum of the previous sequence, and so on. Let's write the weight on each element for each sequence, starting from the $n$th sequence.
$$\begin{array}{ccccc}1& & & & \\ \frac{1}{2}& \frac{1}{2}& & & \\ \frac{1}{2}\frac{1}{2}+\frac{1}{2}\frac{1}{3}& \frac{1}{2}\frac{1}{2}+\frac{1}{2}\frac{1}{3}& \frac{1}{3}\frac{1}{2}& & \\ \frac{1}{2}\frac{1}{2}\frac{1}{2}+\frac{1}{2}\frac{1}{3}\frac{1}{2}+\frac{1}{3}\frac{1}{2}\frac{1}{2}+\frac{1}{3}\frac{1}{3}\frac{1}{2}+\frac{1}{4}\frac{1}{3}\frac{1}{2}& \dots & & & \end{array}$$
We can express the denominators as products of paths. Consider the sequences of length $n$, $\{P_n\}$, which start with $p_0=2$, and each time the next number $p_k$ can be any number within $[2,1+p_{k-1}]$ for $k\in [1,n-1]$. The first few sets are:

$$\begin{array}{rl}n=1:& (2)\\ n=2:& (2,2),(2,3)\\ n=3:& (2,2,2),(2,2,3),(2,3,2),(2,3,3),(2,3,4)\\ n=4:& (2,2,2,2),(2,2,2,3),(2,2,3,2),(2,2,3,3),(2,2,3,4),(2,3,2,2),(2,3,2,3),(2,3,3,2),\\ & (2,3,3,3),(2,3,3,4),(2,3,4,2),(2,3,4,3),(2,3,4,4),(2,3,4,5)\end{array}$$

Let $P_{nj}$ be any path in $\{P_n\}$, and $\prod P_{nj}$ be the product of all the numbers in that path. The question is equivalent to ${\text{lim}}_{n\to \mathrm{\infty }}\sum _{P_{nj}\in \{P_n\}}(\prod P_{nj}{)}^{-1}=e^{-1}$.

Notice that these sequences of weights are exactly the first row of $M^n$, thus they are totally equivalent. Relating them to the "product of paths" seems like an interesting connection.


Proof:

Consider the eigenvectors of the matrix, $M$. An obvious one is an all one vector, $u=(1,1,1,\dots )$. Apparently $Mu=u$, thus, $M^{n}u=u$, which implies that every row of $M^n$ must sum to 1. Can we use this to find $[M^n{]}_{00}$?

Suppose the first row of $M^{n-1}$ is $(a_{n-1,0},a_{n-1,1},a_{n-1,2},\dots )$. Multiply $M^{n-1}$ to $M$, the elements of the first row of $M^n$ are:
$$\begin{array}{rl}{a}_{n0}=& \frac{1}{2}{a}_{n-1,0}+\frac{1}{3}{a}_{n-1,1}+\frac{1}{4}{a}_{n-1,2}+\dots \\ a_{n1}=& \frac{1}{2}{a}_{n-1,0}+\frac{1}{3}{a}_{n-1,1}+\frac{1}{4}{a}_{n-1,2}+\dots \\ a_{n2}=& \frac{1}{3}{a}_{n-1,1}+\frac{1}{4}{a}_{n-1,2}+\dots \\ a_{n3}=& \frac{1}{4}{a}_{n-1,2}+\dots \end{array}$$
Evidently,
$$\begin{array}{rl}{a}_{n1}& =a_{n0},\\ a_{n2}& =a_{n1}-\frac{1}{2}{a}_{n-1,0},\\ a_{n3}& =a_{n2}-\frac{1}{3}{a}_{n-1,1},\\ \dots \end{array}$$

Assuming that the first row of $M^n$ converges (which will be proved shortly after) to a constant vector $(a_0,a_1,a_2,\dots )$. Then we must have
$$\begin{array}{rl}{a}_1& =a_0\\ a_2& =a_1-\frac{1}{2}{a}_0\\ a_3& =a_2-\frac{1}{3}{a}_1\\ a_4& =a_3-\frac{1}{4}{a}_2\\ \dots \end{array}$$
It's easy to solve for the first few elements as a function of $a_0$, namely
$a_1=a_0,a_2=\frac{1}{2}{a}_0,a_3=\frac{1}{6}{a}_0,a_4=\frac{1}{24}{a}_0$. The pattern is obvious.

It's easy to prove the general formula $a_k=\frac{1}{k!}{a}_0$ by induction, since $\frac{1}{k!}-\frac{1}{k+1}\frac{1}{(k-1)!}=\frac{1}{k!}-\frac{k}{k+1}\frac{1}{k!}=\frac{1}{(k+1)!}$.

Since we must have $\sum a_i=1$, we have $(\sum _{i=0}^{\mathrm{\infty }}\frac{1}{i!})a_0=1$, thus $a_0=e^{-1}$.


To prove that the first row of $M^n$ converges, first we prove that $a_{n0}$ must converge. Consider the original form of the problem. We start with a decreasing sequence, $(1,0,0,0,\dots )$. Each time, the $k$th element of the next sequence is the average of the first $k+2$ elements of the current sequence. If the current sequence is decreasing, it's easy to show that the next sequence must also be decreasing. Thus, $f(n,0)=\frac{1}{2}(f(n-1,0)+f(n-1,1))<f(n-1,0)$ for any $n$. We proved that $f(n,0)$ decreases with $n$. Since $f(n,0)>0$, the limit must exist, thus $a_{n0}$ must converge.

From the updating rule,
$$\begin{array}{rl}{a}_{n1}& =a_{n0},\\ a_{n2}& =a_{n1}-\frac{1}{2}{a}_{n-1,0},\\ a_{n3}& =a_{n2}-\frac{1}{3}{a}_{n-1,1},\\ \dots \end{array}$$
If $a_{n0}$ converges, $a_{n1}=a_{n0}$ must also converge, then $a_{n2}$ must converge as well. The same goes for the rest of the elements, thus the sequence must converge. The proof is complete.