In chapter 2.2 of Concrete Mathematics, the authors introduced the usage of summation factor to convert recurrence to summation. The idea is to multiply $s_n$ on both sides of the recurrence relation of the form $a_n T_n = b_n T_{n-1} + c_n$ to obtain $s_n a_n T_n = s_n b_n T_{n-1} + s_n c_n$. If we select $s_n b_n = s_{n-1} a_{n-1}$, and let $S_n = s_n a_n T_n$, then we get $S_n = S_{n-1} + s_n c_n$, which can be expressed in terms of a sum easily.
Here's my question. When they are solving for the quick sort recurrence $C_0 = C_1 = 0$ and $C_n = n + 1 + \frac{2}{n} \sum_{k=0}^{n-1} C_k$, the final closed form formula have a restriction of $n > 1$. Why?
More general, how can we figure out the restriction of $n$ while using such technique?
EDIT
In order to solve for $C_n = n + 1 + \frac{2}{n} \sum_{k=0}^{n-1} C_k$, first multiply both sides by $n$ to obtain $nC_n = n^2 + n + 2 \sum_{k=0}^{n-1} C_k$. If you replace $n$ by $n-1$, we get $(n-1)C_{n-1} = (n-1)^2 + (n-1) + 2 \sum_{k=0}^{n-2} C_k$. Take note this is only valid if $n>2$. Subtract both equations, we get $nC_n =(n+1)C_{n-1}+2n$ for $n>2$, and $C_0 = C_1 = 0$ and $C_2 = 3$. From this point, the recurrence will only be valid for $n>2$, but the final solution is valid for $n>1$. Why?
The summation factor is $\frac2{n(n+1)}$, so we get $S_n=\frac2{n+1}C_n$ and $S_n=S_{n-1}+\frac4{n+1}$ for $n\ge 3$. $C_2=3$, so $S_2=\frac23C_2=2$, and
$$S_n=2+\sum_{k=3}^n\frac4{k+1}=2+4(H_{n+1}-H_3)=4H_{n+1}-\frac{16}3$$
for $n\ge 3$. Thus,
$$\begin{align*} C_n&=2(n+1)H_{n+1}-\frac83(n+1)\\ &=2(n+1)\left(H_n+\frac1{n+1}\right)-\frac83n-\frac83\\ &=2(n+1)H_n-\frac83n-\frac23\tag{1} \end{align*}$$
for $n\ge 3$.
The derivation is valid only for $n\ge 3$, but the expression $(1)$ might by good fortune be valid for smaller values of $n$, and one should always test. Here we find that for $n=2$ it evaluates to
$$2\cdot3\cdot\frac32-\frac{16}3-\frac23=9-6=3\;,$$
which actually is $C_2$. However, at $n=1$ it evaluates to
$$2\cdot2\cdot1-\frac83-\frac23=4-\frac{10}3\ne 0=C_1\;,$$
so the closed form
$$C_n=2(n+1)H_n-\frac83n-\frac23$$
is valid precisely for $n\ge 2$. Its validity for $n=2$ doesn’t follow from the derivation: it follows from an independent verification after the fact.