I'm trying to understand the analysis of Quick Select algorithm that I found on StackOverflow: https://stackoverflow.com/a/25796762/3356218
Case 1 of proof:
I understand it but the first transition, when he changes the indices.
He passes from $\sum\limits_{i=1}^{k-1} \sum\limits_{j=i+1}^k \frac{2}{j-i+1}$ to $\sum\limits_{d=1}^{k-1} \sum\limits_{i=1}^{k-d} \frac{2}{d+1}$. Conceptually, I understand that this is right, but I would like to know which precise rules he used.
Case 3
Could you briefly explain me every pass of the proof from the second pass?
In your first question let $d=j-i$; then
$$\sum_{i=1}^{k-1}\sum_{j=i+1}^k\frac2{j-i+1}=\sum_{i=1}^{k-1}\sum_{d=1}^{k-i}\frac2{d+1}\;.$$
Now let $\ell=k-i$, and note that as $i$ runs from $1$ up to $k-1$, $\ell$ runs from $k-1$ down to $i$. Thus,
$$\sum_{i=1}^{k-1}\sum_{d=1}^{k-i}\frac2{d+1}=\sum_{\ell=1}^{k-1}\sum_{d=1}^\ell\frac2{d+1}\;.$$
This last double summation is a summation over all pairs $\langle\ell,d\rangle$ such that $1\le d\le\ell\le k-1$, the pairs marked with a $\bullet$ in the following chart:
$$\begin{array}{c|c|c} \ell\backslash d&1&2&3&\ldots&k-2&k-1\\ \hline 1&\bullet&&&\ldots\\ \hline 2&\bullet&\bullet&&\ldots\\ \hline 3&\bullet&\bullet&\bullet&\ldots\\ \hline \vdots&\vdots&\vdots&\vdots&\ddots\\ \hline k-2&\bullet&\bullet&\bullet&\ldots&\bullet\\ \hline k-1&\bullet&\bullet&\bullet&\ldots&\bullet&\bullet \end{array}$$
That double summation divides these pairs up by their first component, $\ell$: it sums the terms in each row, and then takes the sum of those row sums. We could instead sum the terms in each column and then take the sum of those column sums:
$$\sum_{\ell=1}^{k-1}\sum_{d=1}^\ell\frac2{d+1}=\sum_{d=1}^{k-1}\sum_{\ell=d}^{k-1}\frac2{d+1}\;.$$
This is entirely analogous to reversing the order of integration of an iterated integral: we’re just chopping up the triangular region in the opposite direction.
Now let $i=\ell-d+1$; as $\ell$ runs from $d$ to $k-1$, $i$ runs from $1$ to $k-d$, and we have
$$\sum_{d=1}^{k-1}\sum_{\ell=d}^{k-1}\frac2{d+1}=\sum_{d=1}^{k-1}\sum_{i=1}^{k-d}\frac2{d+1}\;.$$
In Case $\mathbf{3}$ we first set $d=j-i$, so that
$$\sum_{i<k<j}\frac2{j-i+1}=\sum_{i=1}^{k-1}\sum_{d=k+1-i}^{n-i}\frac2{d+1}=2\sum_{i=1}^{k-1}\sum_{d=k+1-i}^{n-i}\frac1{d+1}\;:$$
since $j>k$, the smallest possible value of $j$ is $k+1$, and therefore the smallest possible value of $d=j-i$ is $k+1-i$. Similarly, the nature of the problem ensures that $j\le n$, so $d\le n-i$.
Now
$$\begin{align*} \sum_{d=k+1-i}^{n-i}\frac1{d+1}&=\frac1{k+2-i}+\frac1{k+3-i}+\ldots+\frac1{n+1-i}\\ &=\sum_{\ell=1}^{n+1-i}\frac1\ell-\sum_{\ell=1}^{k+1-i}\frac1\ell\\ &=H_{n+1-i}-H_{k+1-i}\;, \end{align*}$$
so
$$\sum_{i<k<j}\frac2{j-i+1}=2\sum_{i=1}^{k-1}(H_{n+1-i}-H_{k+1-i})\;.$$
By looking at the upper Riemann sum for $\int_1^n\frac1x\,dx=\ln n$, it’s not hard to see that $\ln(n+1)\le H_n$, and by looking at the lower Riemann sum we can see that
$$H_n-1=\sum_{k=2}^n\frac1k\le\int_1^n\frac1x\,dx=\ln n\;,$$
so that $H_n\le 1+\ln n$. Thus, $H_{n+1-i}\le 1+\ln(n+1-i)$, and $H_{k+1-i}\ge\ln(k+2-i)$, so
$$H_{n+1-i}-H_{k+1-i}\le 1+\ln(n+1-i)-\ln(k+2-i)\;.$$
And $\ln(k+2-i)\ge\ln(k-i)$, so
$$\ln(n+1-i)-\ln(k+2-i)\le\ln(n+1-i)-\ln(k-i)\;.$$
Next, $n+1-i$ runs from $n$ down to $n-k+2$ as $i$ runs from $1$ to $k-1$, and $k+1-i$ runs from $k$ down to $2$, so
$$\begin{align*} \sum_{i=1}^{k-1}\Big(1+\ln(n+1-i)-\ln(k+1-i)\big)&=k-1+\sum_{i=1}^{k-1}\Big(\ln(n+1-i)-\ln(k+1-i)\big)\\ &=k-1+\sum_{i=1}^{k-1}\ln\left(\frac{n+1-i}{k+1-i}\right)\\ &=k-1+\ln\left(\prod_{i=1}^{k-1}\frac{n+1-i}{k+1-i}\right)\\ &=k-1+\ln\left(\frac{\prod_{i=n-k+2}^ni}{\prod_{i=2}^ki}\right)\\ &=k-1+\ln\left(\frac{n!/(n-k+1)!}{k!}\right)\\ &=k-1+\ln\left(\frac{n!}{k!(n-k+1)!}\right)\\ &<k+\ln\left(\frac{n!}{(k-1)!(n-(k-1))!}\right)\\ &=k+\ln\binom{n}{k-1}\;. \end{align*}$$
Finally, $\binom{n}{k-1}$ is the number of subsets of $\{1,\ldots,n\}$ of size $k-1$, and $\{1,\ldots,n\}$ has $2^n$ subsets altogether, so $\binom{n}{k-1}\le2^n$, and
$$k+\ln\binom{n}{k-1}\le k+\ln 2^n=k+n\ln 2\le n+n\ln 2=(1+\ln 2)n\in O(n)\;.$$