Number of calls with length 2 array in quick-sort I need to find average number of recursive calls in quick-sort with array of length 2. I established and solved the following recursion:

$$T_N = \frac{1}{N}\sum_{k=1}^N\left(T_{k-1}+N_{N-k}\right) = \frac{N+1}{N}T_{N-1} = \frac{N+1}{3}.$$

Where $T_0 = T_1 = 0, T_2 = 1$. But:

\begin{align*}
T_3 &amp;= 1/3(1 + 1) &amp;= 2/3\\
T_4 &amp;= 1/4(2/3 + 1 + 1 + 2/3) &amp;= 5/6\\
T_5 &amp;= 1/5 (5/4 + 2/3 + 2 + 2/3 + 5/4) &amp;= 7/6\\
T_6 &amp;= 1/6(7/6 + 5/6 + (1+2/3) + (1+2/3) + 5/6 + 7/6) &amp;= 11/9
\end{align*}

The results are different. How to do it right?

EDIT: The code for quick-sort in question is:

void quicksort(int[] a, int lo, int hi)
{
  if (hi &lt;= lo) return;
  int i = lo-1, j = hi;
  int t, v = a[hi];
  while (true) {
    while (a[++i] &lt; v) ;
    while (v &lt; a[--j]) if (j == lo) break;
    if (i &gt;= j) break;
    t = a[i]; a[i] = a[j]; a[j] = t;
  }
  t = a[i]; a[i] = a[hi]; a[hi] = t;
  quicksort(a, lo, i-1);
  quicksort(a, i+1, hi);
}
First, note that you can write your recurrence as
$$
T_N = \frac{2}{N}\sum_{i=0}^{N-1} T_i.
$$
Consider now the generating function
$$
T(x) = \sum_{N=0}^\infty T_N x^N.
$$
We calculate
$$
\frac{T(x)}{1-x} = \sum_{N=0}^\infty \sum_{i=0}^N T_i x^N =
\frac{1}{2} \sum_{N=2}^\infty (N+1)T_{N+1}x^N = \frac{1}{2} \sum_{N=3}^\infty NT_Nx^{N-1}.
$$
On the other hand,
$$
\frac{d}{dx} T(x) = \sum_{N=0}^\infty NT_Nx^{n-1}.
$$
We conclude that $T(x)$ satisfies the differential equation
$$
\frac{d}{dx} T(x) = \frac{2T(x)}{1-x} + 2x.
$$
Additionally, $T(0) = 0$. Plugging this into Wolfram alpha, we obtain the solution
$$
T(x) = \frac{x^2(3x^2-8x+6)}{6(1-x)^2}.
$$
Using $1/(1-x)^2 = \sum_{N=0}^\infty (N+1)x^N$, we obtain for $N \geq 3$ that
$$
T_N = \frac{6(N-1)-8(N-2)+3(N-3)}{6} = \frac{N+1}{6}.
$$



Having computed the solution by brute force, it is easy to prove by induction. Suppose that $N \geq 3$. Then
$$
T_N = \frac{2}{N} \sum_{i=0}^{N-1} T_i =
\frac{2}{N} \left(1 + \sum_{i=3}^{N-1} \frac{i+1}{6}\right) =
\frac{2}{N} \left(1 + \frac{(N-3)(N+4)}{12} \right) = \frac{N+1}{6}.
$$