Generatingfunctionology Chapter 1 Exercise 18.b

Question

Regarding the exercises of the Generatingfunctionology book available at (https://www2.math.upenn.edu/~wilf/DownldGF.html).

In Chapter 1, Exercise 18.(b), one is asked:

What is the average length of the decreasing sequence with which the values of a random n-permutation begin?

To compute this, let $X$ be the R.V. for a sequence starting with exactly $k$ decreasing values, then $$\mathbb{E}[X] = \sum_{k=0}^{n} k \cdot \Pr[X = k]$$ So, the probability to have a sequence with at least starting $k$ decreasing values should be $\Pr[X \geq k] = \frac{1}{k!}$ (also, this is stated in the solution of exercise 18.(a) in the book).

Then, the probability of a sequence starting with exactly $k$ decreasing values should be $\Pr[X = k] = \Pr[X \geq k] - \Pr[X \geq k+1]$ (since there is no $k+1$, for $k=n$ it is clear that there is only $1$ such sequence so $\Pr[X = n] = \frac{1}{n!})$.

Thus, $$\mathbb{E}[X] = \sum_{k=0}^{n} k \cdot \Pr[X = k]$$ $$\mathbb{E}[X] = \sum_{k=0}^{n-1} k \left(\Pr[X \geq k] - \Pr[X \geq k+1]\right) + \frac{n}{n!}$$ $$\mathbb{E}[X] = \sum_{k=0}^{n-1} k \left(\frac{1}{k!} - \frac{1}{(k+1)!}\right)+ \frac{n}{n!} $$

And this is the same result as in the solutions, so this should be correct (?). However, in the solutions this is further stated to be equal to $$\mathbb{E}[X] = \sum_{k=1}^n \frac{1}{k!} \approx e − 1.$$

However, I cannot show that $$\sum_{k=0}^{n-1} k \left(\frac{1}{k!} - \frac{1}{(k+1)!}\right)+ \frac{n}{n!} = \sum_{k=1}^n \frac{1}{k!},$$ and I believe this is incorrect, as for $n=3$, this would mean that $0 + (1-\frac{1}{2}) + (1 - \frac{1}{3}) + \frac{1}{2} = 2 - \frac{1}{3} \neq 1 + \frac{1}{2} + \frac{1}{3}$.

First, am I correct?

Second, is anyone aware of an errata for this book?

Third, if my reasoning is correct, should I deduce anything else from the expression $$\mathbb{E}[X] = \sum_{k=0}^{n-1} k \left(\frac{1}{k!} - \frac{1}{(k+1)!}\right)+ \frac{n}{n!}\quad \text{?}$$

Thanks!

Answer 1

For $n=3$ you get on the right hand side $1+\frac12+\frac16$ not $1+\frac12+\frac13$ so they are equal

More generally $$\sum_{k=0}^{n-1} k \left(\frac{1}{k!} - \frac{1}{(k+1)!}\right)+ \frac{n}{n!} \\=\sum_{k=1}^{n-1} k \left(\frac{1}{k!} - \frac{1}{(k+1)!}\right)+ \frac{n}{n!} \\= \sum_{k=1}^{n-1} \frac{k}{k!} - \sum_{k=1}^{n-1}\frac{k+1}{(k+1)!}+\sum_{k=1}^{n-1}\frac{1}{(k+1)!}+ \frac{n}{n!}\\= \sum_{k=1}^{n-1} \frac{1}{(k-1)!} + \frac{1}{(n-1)!}- \sum_{k=1}^{n-1}\frac{1}{k!}+\sum_{k=1}^{n-1}\frac{1}{(k+1)!} \\ = 1 +\sum_{k=1}^{n-1}\frac{1}{(k+1)!} \\= \sum_{k=1}^{n}\frac{1}{k!}.$$

Answer 2

One can also prove the result using induction. Suppose that $$\sum_{k=0}^{n-1}k\left(\frac{1}{k!} - \frac{1}{(k+1)!}\right)=\sum_{k=1}^n\frac{1}{k!} - \frac{n}{n!}$$ Then \begin{align} \sum_{k=0}^{n}k\left(\frac{1}{k!} - \frac{1}{(k+1)!}\right) &= \sum_{k=0}^{n-1}k\left(\frac{1}{k!} - \frac{1}{(k+1)!}\right) + n\left(\frac{1}{n!} - \frac{1}{(n+1)!}\right)\\ &= \sum_{k=1}^n\frac{1}{k!} - \frac{n}{n!} + \frac{1}{(n-1)!} -\frac{n}{(n+1)!} \\ &=\sum_{k=1}^n\frac{1}{k!} -\frac{n}{(n+1)!} \\ &=\sum_{k=1}^{n+1}\frac{1}{k!} -\frac{1}{(n+1)!} -\frac{n}{(n+1)!} \\ &=\sum_{k=1}^{n+1}\frac{1}{k!} -\frac{n+1}{(n+1)!} \end{align}

I want to, however, mention a nicer way of computing the expected value

$$\mathbb{E}[X]=\sum_{k=1}^{n}k\mathbb{P}(X=k) = \sum_{k=1}^{n}\mathbb{P}(X\geq k) = \sum_{k=1}^{n}\frac{1}{k!}$$ Since $\mathbb{P}(X=z)$ will be counted $z$ times, one for each of $\mathbb{P}(X\geq w)$ for $w=1,2\dots, z$