Solve

\[ \begin{aligned} C_N &= N + 1 + \frac{2}{N}\sum_{1 \le k \le N} C_{k-1} \\ \end{aligned} \]

\[ \begin{aligned} N C_N &= N(N + 1) + 2 \sum_{1 \le k \le N} C_{k-1} & \text{multiply by } N\\ \sum_{N \ge 1} N C_N z^N &= \sum_{N \ge 1} N(N + 1) z^N + 2 \sum_{N \ge 1} \sum_{1 \le k \le N} C_{k-1} z^N & \text{multiply by } z^N \text{ and sum over all N} \\ \end{aligned} \]

Let \(\displaystyle C(z) = \sum_{N \ge 0} C_N z^N\). So,

\[ \begin{aligned} C'(z) &= \sum_{N \ge 1} N C_N z^{N-1} \\ \color{blue}{z C'(z)} &\color{blue}{= \sum_{N \ge 1} N C_N z^N} \\ \sum_{N \ge 1} N(N + 1) z^N &= \sum_{N \ge 2} (N - 1) N z^{N-1} & \text{re-index} \\ &= \frac{1}{z} \sum_{N \ge 2} (N - 1) N z^N \\ &= \frac{2}{z} \sum_{N \ge 2} \frac{N(N - 1)}{2} z^N \\ &= \frac{2}{z} \sum_{N \ge 2} {N \choose 2} z^N \\ &= \frac{2}{z} \cdot \frac{z^2}{(1-z)^3} & \text{corresponding OGF} \\ \color{blue}{\sum_{N \ge 1} N(N + 1) z^N} &\color{blue}{= \frac{2z}{(1-z)^3}} \\ 2 \sum_{N \ge 1} \sum_{1 \le k \le N} C_{k-1} z^N &= 2z \sum_{N \ge 1} \sum_{1 \le k \le N} C_{k-1} z^{N-1} \\ &= 2z \sum_{N \ge 0} \sum_{1 \le k \le N+1} C_{k-1} z^N & \text{re-index } N \\ &= 2z \sum_{N \ge 0} \sum_{0 \le k \le N} C_k z^N & \text{re-index } k \\ \color{blue}{2 \sum_{N \ge 1} \sum_{1 \le k \le N} C_{k-1} z^N} &\color{blue}{= 2z \frac{C(z)}{1-z}} & \text{convolve simple OGF} \\ \end{aligned} \]

Recall

\[ \begin{aligned} \sum_{N \ge 1} N C_N z^N &= \sum_{N \ge 1} N(N + 1) z^N + 2 \sum_{N \ge 1} \sum_{1 \le k \le N} C_{k-1} z^N \\ z C'(z) &= \frac{2z}{(1-z)^3} + 2z \frac{C(z)}{1-z} \\ C'(z) &= \frac{2}{(1-z)^3} + 2 \frac{C(z)}{1-z} \\ \end{aligned} \]

But this is a linear 1st order differential equation, which can be readily solved! In general, if

\[ \begin{aligned} x'(t) - A x(t) = B(t) \qquad &\text{standar form} \\ \end{aligned} \]

then

\[ \begin{aligned} x(t) &= e^{\int A} \cdot \int B e^{\int -A} & \text{see PennCalc wiki} \\ \end{aligned} \]

Now

\[ \begin{aligned} C'(z) - 2 \frac{C(z)}{1-z} &= \frac{2}{(1-z)^3} &\text{rewrite into standard form} \\ A &= \frac{2}{1-z} \\ B &= \frac{2}{(1-z)^3} \\ e^{\int A} &= e^{\int\frac{2}{1-z}} = e^{-2\ln(1-z)} = \frac{1}{(1-z)^2} \\ e^{\int - A} &= (1-z)^2 \\ C(z) &= e^{\int A} \cdot \int B e^{-\int A} = \frac{1}{(1-z)^2} \int \frac{2}{(1-z)^3} (1-z)^2 \\ &= \frac{1}{(1-z)^2} \int \frac{2}{(1-z)} \\ &= \frac{1}{(1-z)^2} \ln\frac{1}{(1-z)^2} \\ C(z) &= \frac{2}{(1-z)^2} \ln\frac{1}{(1-z)} \\ \end{aligned} \]

But we saw earlier

\[ \begin{aligned} \text{[}z^N]\frac{1}{(1-z)^2} \ln\frac{1}{(1-z)} &= (N+1)(H_{N+1} - 1) \\ [z^N]C(z) &= [z^N]\frac{2}{(1-z)^2} \ln\frac{1}{(1-z)} = 2 (N+1)(H_{N+1} - 1) \\ \therefore C_N &= 2 (N+1)(H_{N+1} - 1) \\ \end{aligned} \]

\(\Box\)

Source: Analysis of Algorithm

# posted by rot13(Unafba Pune) @ 8:23 PM