Solve the recurrence

\[ \begin{aligned} a_n &= 3a_{n-1} - 3a_{n-2} + a_{n-3} & \text{ for } n > 2 \text{ with } a_0 = a_1 = 0 \text{ and } a_2 = 1 \\ \end{aligned} \]

\[ \begin{aligned} a_{n+3} &= 3a_{n+2} - 3a_{n+1} + a_{n} & n \text{ to } n+3 \\ \sum_{n \ge 0} a_{n+3} z^n &= \sum_{n \ge 0} 3a_{n+2} z^n - \sum_{n \ge 0} 3a_{n+1} z^n + \sum_{n \ge 0} a_{n} z^n & \text{ multiply by }z^n \text{ and sum over all } n \\ \color{blue}{\frac{1}{z^3} \sum_{n \ge 3} a_{n} z^n} &\color{blue}{= \frac{1}{z^2} \sum_{n \ge 2} 3a_{n} z^n - \frac{1}{z} \sum_{n \ge 1} 3a_{n} z^n + \sum_{n \ge 0} a_{n} z^n} &\text{re-index} \\ \frac{1}{z^3} \left(\sum_{n \ge 0} a_{n} z^n - z^2 \right) &= \frac{3}{z^2} \sum_{n \ge 0} a_{n} z^n - \frac{3}{z} \sum_{n \ge 0} a_{n} z^n + \sum_{n \ge 0} a_{n} z^n \\ \frac{1}{z^3} \left(a(z) - z^2 \right) &= \frac{3}{z^2} a(z) - \frac{3}{z} a(z) + a(z) \\ a(z) \left(\frac{1}{z^3} -\frac{3}{z^2} + \frac{3}{z} - 1 \right) &= \frac{1}{z} \\ a(z) \frac{1 - 3z + 3z^2 -z^3}{z^3} &= \frac{1}{z} \\ a(z) &= \frac{z^2}{(1-z)^3} \\ [z^n] a(z) &\equiv a_n = {n \choose 2} &\text{OGF table lookkup} \\ \end{aligned} \]

\(\Box\)

Solve the same recurrence with the initial condition on \(a_1\) changed to \(a_1 = 1\).

\[ \begin{aligned} \color{blue}{\frac{1}{z^3} \sum_{n \ge 3} a_{n} z^n} &\color{blue}{= \frac{1}{z^2} \sum_{n \ge 2} 3a_{n} z^n - \frac{1}{z} \sum_{n \ge 1} 3a_{n} z^n + \sum_{n \ge 0} a_{n} z^n} \\ \frac{1}{z^3} \left(\sum_{n \ge 0} a_{n} z^n - z - z^2 \right) &= \frac{3}{z^2} \left(\sum_{n \ge 0} a_{n} z^n - z\right) - \frac{3}{z} \sum_{n \ge 0} a_{n} z^n + \sum_{n \ge 0} a_{n} z^n \\ \frac{1}{z^3} \left(a(z) - z - z^2 \right) &= \frac{3}{z^2} \left(a(z) - z\right) - \frac{3}{z} a(z) + a(z) \\ a(z) \left(\frac{1}{z^3} -\frac{3}{z^2} + \frac{3}{z} - 1 \right) &= \frac{1}{z^2} - \frac{2}{z} \\ a(z) \left(1 - 3z + 3z^2 -z^3\right) &= z-2z^2 \\ a(z) &= \frac{z}{(1-z)^3} - \frac{2z^2}{(1-z)^3} \\ &= z \sum_{n \ge 0} {n+2 \choose 2} z^n - 2 \sum_{n \ge 2} {n \choose 2} z^n &\text{OGF expansion} \\ &= \sum_{n \ge 0} {n+2 \choose 2} z^{n+1} - 2 \sum_{n \ge 2} {n \choose 2} z^n \\ &= \sum_{n \ge 1} {n+1 \choose 2} z^n - 2 \sum_{n \ge 2} {n \choose 2} z^n \\ &= \left(z + {3 \choose 2}z^2 + \sum_{n \ge 3} {n+1 \choose 2} z^n\right) - 2\left(z^2 + \sum_{n \ge 3} {n \choose 2} z^n\right) \\ &= z + z^2 + \sum_{n \ge 3} \left({n+1 \choose 2} -2 {n \choose 2} \right)z^n \\ [z^n]a(z) &\equiv a_n = {n+1 \choose 2} - 2 {n \choose 2} &\text{for } n \ge 3 \\ \end{aligned} \]

\(\Box\)

Source: Analysis of Algorithm

\[ \begin{aligned} F_{n+2} &= F_{n+1} + F_n & \text{ where } F_0 = 0 \text{ and } F_1 = 1 \\ \sum_{n \ge 0} F_{n+2} z^n &= \sum_{n \ge 0} F_{n+1} z^n + \sum_{n \ge 0} F_n z^n & \text{multiply by }z^n\text{ and sum over all } n \\ \frac{1}{z^2} \sum_{n \ge 2} F_{n} z^n &= \frac{1}{z} \sum_{n \ge 1} F_{n} z^n + \sum_{n \ge 0} F_n z^n & \text{re-index}\\ \frac{1}{z^2} \left(\sum_{n \ge 0} F_{n} z^n\right) - \frac{F_1 z + F_0 z^0}{z^2} &= \frac{1}{z} \sum_{n \ge 0} F_{n} z^n - \frac{F_0 z^0}{z} + \sum_{n \ge 0} F_n z^n \\ \frac{F(z)}{z^2} - \frac{z}{z^2} &= \frac{1}{z} F(z) + F(z) \\ F(z) - z &= z F(z) + z^2 F(z) \\ F(z) &= \frac{z}{1 - z - z^2} & \text{OGF of Fibonacci sequence!} \\ \end{aligned} \]

Observe

\[ \begin{aligned} 1-z-z^2 &= - \left( z + \frac{\sqrt{5}+1}{2} \right) \left( z - \frac{\sqrt{5}-1}{2} \right) \\ &= \left( \frac{\sqrt{5}+1}{2} + z \right) \left( \frac{\sqrt{5}-1}{2} - z \right) \\ \end{aligned} \]

Let

\[ \begin{aligned} \varphi &= \frac{\sqrt{5}+1}{2} \\ \hat \varphi &= \frac{\sqrt{5}-1}{2} \\ \end{aligned} \]

So

\[ \begin{aligned} \frac{z}{1-z-z^2} &= \frac{z}{\left( \varphi + z \right) \left( \hat\varphi - z \right)} \\ \frac{A}{\left( \varphi + z \right)} + \frac{B}{\left( \hat\varphi - z \right)} &= \frac{z}{\left( \varphi + z \right) \left( \hat\varphi - z \right)} &\text{partial fractions} \\ A \left( \hat\varphi - z \right) + B \left( \varphi + z \right) &= z \\ B \left( \varphi + \hat\varphi \right) &= \hat\varphi \\ B & = \frac{\hat\varphi}{\varphi + \hat\varphi} = \frac{\sqrt{5}-1}{2\sqrt{5}} = \frac{1}{\sqrt{5}} \hat\varphi \\ A \left( \hat\varphi + \varphi \right) &= -\varphi \\ A &= \frac{-\varphi}{\hat\varphi + \varphi } = -\frac{\sqrt{5}+1}{2\sqrt{5}} = -\frac{1}{\sqrt{5}} \varphi \\ \end{aligned} \]

Therefore

\[ \begin{aligned} F(z) &= \frac{z}{1 - z - z^2} = \frac{-\varphi}{\sqrt{5} \left( \varphi + z \right)} + \frac{\hat\varphi}{\sqrt{5} \left( \hat\varphi - z \right)} \\ &= \frac{-1}{\sqrt{5} \left( 1 - (- \frac{z}{\varphi}) \right)} + \frac{1}{\sqrt{5} \left( 1 - \frac{z}{\hat\varphi} \right)} \\ &= \frac{1}{\sqrt{5} \left( 1 - \frac{z}{\hat\varphi} \right)} - \frac{1}{\sqrt{5} \left( 1 - (- \frac{z}{\varphi}) \right)} \\ &= \frac{1}{\sqrt{5}} \sum_{N \ge 0} (\hat\varphi^{-1} z)^N - \frac{1}{\sqrt{5}} \sum_{N \ge 0} (- \varphi^{-1} z)^N & \text{expand OGF} \\ &= \frac{1}{\sqrt{5}} \sum_{N \ge 0} \hat\varphi^{-N} z^N + \frac{1}{\sqrt{5}} \sum_{N \ge 0} (-1)^{N+1} \varphi^{-N} z^N \\ &= \sum_{N \ge 0} \frac{1}{\sqrt{5}} \left( \hat\varphi^{-N} + (-1)^{N+1} \varphi^{-N}\right) z^N \\ F_N \equiv [z_N]F(z) &= \frac{1}{\sqrt{5}} \left( \hat\varphi^{-N} + (-1)^{N+1} \varphi^{-N}\right) \\ &= \frac{1}{\sqrt{5}} \left( (\frac{2}{\sqrt{5}-1})^{N} + (-1)^{N+1} (\frac{2}{\sqrt{5}+1})^N\right) \\ &= \frac{1}{\sqrt{5}} \left( (\frac{2(\sqrt{5}+1)}{4})^{N} + (-1)^{N+1} (\frac{2(\sqrt{5}-1)}{4})^N\right) \\ &= \frac{1}{\sqrt{5}} \left( (\frac{2(\sqrt{5}+1)}{4})^{N} + (-1)^{2N+1} (\frac{2(1 - \sqrt{5})}{4})^N\right) \\ F_N &= \frac{1}{\sqrt{5}} \left( (\frac{1+\sqrt{5}}{2})^{N} - (\frac{1-\sqrt{5}}{2})^N\right) \\ \end{aligned} \]

\(\Box\)

Source: Analysis of Algorithm

\(T\):	set of all binary trees.
\(|t|\):	the number of internal nodes of binary tree \(t\).
leaves(\(t\)):	number of leaves in \(t\).
\(T_N\):	number of binary tree of size \(N\).
\(C_N\):	total number of leaves in all binary trees of size \(N\).

We saw earlier that

\[ \begin{aligned} T(z) &= \sum_{t \in T} z^{|t|} = \sum_{N \ge 0} T_N z^N = \frac{1}{2z} \left(1 - \sqrt{1-4z} \right) \\ T_N &= \frac{1}{N+1} {2N \choose N} \\ \end{aligned} \]

The key is to find the cumulative GF (generating function), \(C(z)\), for the leaves:

\[ \begin{aligned} C(z) &= \sum_{t \in T} \text{leaves}(t) z^{|t|} \\ &= z + \sum_{t_L \in T} \sum_{t_R \in T} \left(\text{leaves}(t_L) + \text{leaves}(t_R)\right) z^{|t_L| + |t_R| + 1} \\ &= z + z \sum_{t_L \in T} \text{leaves}(t_L) z^{|t_L|} \sum_{t_R \in T} z^{|t_R|} + z \sum_{t_R \in T} \text{leaves}(t_R) z^{|t_R|} \sum_{t_L \in T} z^{|t_L|} \\ &= z + 2 z C(z) T(z) \\ C(z) &= \frac{z}{1-2z T(z)} \\ &= \frac{z}{1-2z \frac{1}{2z} \left(1 - \sqrt{1-4z} \right)} \\ &= \frac{z}{\sqrt{1-4z}} \\ &= z \sum_{N \ge 0} {-\frac{1}{2} \choose N} (-4z)^N & \text{binomial theorem} \\ &= z \sum_{N \ge 1} {-\frac{1}{2} \choose N-1} (-4z)^{N-1} & N \text{ to } N-1 \\ &= \sum_{N \ge 1} {-\frac{1}{2} \choose N-1} (-4)^{N-1} z^N \\ \therefore C_N &= {-\frac{1}{2} \choose N-1} (-4)^{N-1} \\ &= \frac{-\frac{1}{2} (-\frac{1}{2}-1) (-\frac{1}{2}-2) \cdots (-\frac{1}{2}-(N-1)+1) }{(N-1)!} (-4)^{N-1} \\ &= \frac{-\frac{1}{2} (-\frac{1}{2}-1) (-\frac{1}{2}-2) \cdots (-\frac{1}{2}-N+2) }{(N-1)!} (-2)^{N-1} 2^{N-1} \\ &= \frac{1 \cdot 3 \cdot 5 \cdots (2N-3) }{(N-1)!} 2^{N-1} & \text{distribute }(-2)^{N-1} \\ &= \frac{1 \cdot 3 \cdot 5 \cdots (2N-3) }{(N-1)!} \frac{2 \cdot 4 \cdots (2N-2)}{1 \cdot 2 \cdots (N-1)} \\ &= \frac{(2N-2)!}{(N-1)!(N-1)!} \\ &= {2N-2 \choose N-1} & \text{!} \\ \end{aligned} \]

Therefore

\[ \begin{aligned} \frac{C_N}{T_N} &= {{2N-2 \choose N-1} \over \frac{1}{N+1} {2N \choose N}} \\ &= {\frac{(2N-2)!}{(N-1)!(2N-2-N+1)!} \over \frac{1}{N+1} \frac{(2N)!}{N!N!}} \\ &= \frac{(2N-2)!}{(N-1)!(N-1)!} \frac{(N+1)N!N!}{(2N)!} \\ &= \frac{N^2(N+1)}{2N(2N-1)}\\ &= \frac{N(N+1)}{2(2N-1)} \\ \frac{C_N}{T_N} &\thicksim \frac{N}{4} \\ \end{aligned} \]

\(\Box\)

Source: Analysis of Algorithm

Simplify

\[ \begin{aligned} f_n &= \sum_k {n \choose k} \frac{f_k}{2^k} \\ \end{aligned} \]

This example showcases the power of EGF, Exponential Generating Functions.

\[ \begin{aligned} f(z) &= \sum_{n \ge 0} \sum_k {n \choose k} \frac{f_k}{2^k} \frac{z^n}{n!} & \text{multiply by } \frac{z_n}{n!} \text{ and sum over all }n \\ &= \sum_{k \ge 0} \sum_{n \ge k} {n \choose k} \frac{f_k}{2^k} \frac{z^n}{n!} & \text{reorder} \\ &= \sum_{k \ge 0} \sum_{n \ge 0} {n+k \choose k} \frac{f_k}{2^k} \frac{z^{n+k}}{(n+k)!} & \text{re-index }n \text{ to } n+k \\ &= \sum_{k \ge 0} \sum_{n \ge 0} \frac{f_k}{2^k} \frac{z^{n+k}}{n! k!} = \sum_{k \ge 0} \sum_{n \ge 0} f_k \frac{(z/2)^k}{k!} \frac{z^{n}}{n!} \\ &= \big(\sum_{k \ge 0} f_k \frac{(z/2)^k}{k!}\big) \big(\sum_{n \ge 0} \frac{z^{n}}{n!}\big) & \text{distribute} \\ &= f(z/2) e^z & \text{!}\\ \end{aligned} \]

Why ? Observe

\[ \begin{aligned} \sum_{k \ge 0} f_k \frac{(z/2)^k}{k!} &= \sum_{n \ge 0} f_n \frac{(z/2)^n}{n!} \\ &= \sum_{n \ge 0} \big(\sum_k {n \choose k} \frac{f_k}{2^k}\big) \frac{(z/2)^n}{n!} \\ &= f(z/2) \\ \end{aligned} \]

Moving on,

\[ \begin{aligned} f(z) &= f(z/2) e^z \\ &= e^z e^{z/2} e^{z/4} \cdots = e^{z + z/2 + z/4 + \cdots} & \text{telescope} \\ &= e^{z \frac{1}{1-\frac{1}{2}}} & \text{geometric series} \\ &= e^{2z} \\ f(z) &= \sum_{n \ge 0} \frac{2^n z^n}{n!} & \text{Talyor series expansion} \\ [z^n]f(z) \equiv f_n &= 2^n \\ \end{aligned} \]

\(\Box\)

Source: Analysis of Algorithm

Solve

\[ \begin{aligned} T_N &= \sum_{1 \le k < N} T_k T_{N-1-k} + \delta_{N0} \\ T(z) \equiv \sum_{N \ge 0} T_N z_N &= \sum_{N \ge 0} \sum_{1 \le k < N} T_k T_{N-1-k}\, z^N + 1 & \text{multiply by }z^N \text{ and sum over all }N \\ &= 1 + \sum_{k \ge 0} \sum_{N > k} T_k T_{N-1-k}\, z^N & \text{switch summation order} \\ &= 1 + \sum_{k \ge 0} \sum_{N \ge 0} T_k T_{N}\, z^{N+k+1} & \text{change }N \text{ to } N+k+1 \\ &= 1 + z\big(\sum_{k \ge 0} T_k z^k\big) \big(\sum_{N \ge 0} T_{N} z^N\big) & \text{distribute} \\ T(z) &= 1 + z T(z)^2 \\ T(z)^2 - \frac{T(z)}{z} &= -\frac{1}{z} \\ \big(T(z) - \frac{1}{2z}\big)^2 &= -\frac{1}{z} + \frac{1}{4z^2} = \frac{1-4z}{4z^2} \\ T(z) - \frac{1}{2z} &= \frac{\pm \sqrt{1-4z}}{2z} \\ \therefore zT(z) &= \frac{1}{2} ( 1 \pm \sqrt{1-4z}) \\ &= \frac{1}{2} ( 1 \pm (1-4z)^{1/2}) \\ &= \frac{1}{2} \big( 1 \pm \sum_{N \ge 0} {\frac{1}{2} \choose N} (-4z)^N \big) & \text{binomial theorem} \\ &= \frac{1}{2} \big( 1 \pm (1 + \sum_{N \ge 1} {\frac{1}{2} \choose N} (-4z)^N ) \big) \\ zT(z) &= -\frac{1}{2} \sum_{N \ge 1} {\frac{1}{2} \choose N} (-4z)^N & \text{pick the minus sign} \\ T(z) &= -\frac{1}{2} \sum_{N \ge 1} {\frac{1}{2} \choose N} (-4)^N z^{N-1} \\ &= -\frac{1}{2} \sum_{N \ge 0} {\frac{1}{2} \choose N+1} (-4)^{N+1} z^{N} & \text{re-index} \\ [z^N]T(z) \equiv T_N &= -\frac{1}{2} {\frac{1}{2} \choose N+1} (-4)^{N+1} \\ T_N &= -\frac{1}{2} \frac{\frac{1}{2} (\frac{1}{2}-1) (\frac{1}{2}-2) \cdots (\frac{1}{2}-N)}{(N+1)!} (-4)^{N+1} &\text{expand via definition} \\ &= -\frac{1}{2} \frac{\frac{1}{2} (\frac{1}{2}-1) (\frac{1}{2}-2) \cdots (\frac{1}{2}-N)}{(N+1)!} (-2)^{N+1} 2^{N+1} \\ &= \frac{(-\frac{1}{2}) (\frac{1}{2}-1) (\frac{1}{2}-2) \cdots (\frac{1}{2}-N)}{(N+1)!} (-2)^{N+1} 2^N \\ &= \frac{1 \cdot 3 \cdot 5 \cdots (2N-1)}{(N+1)!} 2^N &\text{distribute } (-2)^{N+1} \text{ among factors} \\ &= \frac{1 \cdot 3 \cdot 5 \cdots (2N-1)}{(N+1)!} \cdot \frac{2 \cdot 4 \cdot 6 \cdots 2N}{1 \cdot 2 \cdot 3 \cdots N} &\text{expand out }2^N \\ &= \frac{1}{N+1}\cdot \frac{1 \cdot 3 \cdot 5 \cdots (2N-1)}{N!} \cdot \frac{2 \cdot 4 \cdot 6 \cdots 2N}{1 \cdot 2 \cdot 3 \cdots N} \\ &= \frac{1}{N+1}\cdot \frac{2N!}{N!\, N!} \\ T_N &= \frac{1}{N+1} {2N \choose N} & \text{the Catalan number}\\ \end{aligned} \]

\(\Box\)

Source: Analysis of Algorithm

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

Prove that

\[ \begin{aligned} \sum_{1 \le k \le N} H_k = (N+1)(H_{N+1} - 1) \\ \end{aligned} \]

This proof showcases the power of OGF, ordinary generating function. Starting with the Talyer series expansion at around zero:

\[ \begin{aligned} OGF_1 = \frac{1}{1 - z} = \sum_{N \ge 0}z^N \end{aligned} \]

In other words, the ordinary generating function (OGF) of the sequence (\(1, 1, \cdots, 1\)), which are the coefficients of \(\displaystyle \sum_{N \ge 0}z^N\), is \(\displaystyle \frac{1}{1 - z}\).

Differentiating both sides of \(OGF_1\):

\[ \begin{aligned} \frac{1}{(1 - z)^2} &= \sum_{N \ge 0}N z^{N-1} = \sum_{N \ge 1}N z^{N-1}\\ \color{teal}{\frac{1}{(1 - z)^2}} &\color{teal}{= \sum_{N \ge 0}(N+1)z^N} & \text{re-index} \\ \end{aligned} \]

Integrating both sides of \(OGF_1\):

\[ \begin{aligned} - \ln (1-z) &= \ln \frac{1}{1 - z} = \sum_{N \ge 0} \frac{z^{N+1}}{N+1} \\ \color{teal}{\ln \frac{1}{1 - z}} &\color{teal}{= \sum_{N \ge 1} \frac{1}{N} z^N} & \text{re-index} \\ \end{aligned} \]

which means \(\displaystyle \ln (\frac{1}{1 - z})\) is the OGF for the harmonic sequence (\(\displaystyle 1, \frac{1}{2}, \cdots, \frac{1}{N}\)). Recall, in general, if \(\displaystyle A(z) = \sum_{k \ge 0} a_k z^k \) is the OGF of (\(a_0, a_1, \cdots, a_k, \cdots\)), then \(\displaystyle \frac{1}{1-z} A(z) \) is the OGF of (\(a_0, a_0+a_1, a_0+a_1+a_2, \cdots \)). So

\[ \begin{aligned} \frac{1}{1-z} \ln \frac{1}{1 - z} &= \sum_{N \ge 1} \big( \sum_{1 \le k \le N} \frac{1}{N} \big) z^N = \sum_{N \ge 1} H_N z^N \\ \frac{1}{(1-z)^2} \ln \frac{1}{1 - z} &= \sum_{N \ge 1} \big( \color{blue}{\sum_{1 \le k \le N} H_k} \big) z^N & \text{ applying } \frac{1}{1-z} \text{ again!} \\ \color{blue}{[z^N] \frac{1}{(1-z)^2} \ln \frac{1}{1 - z}} &\color{blue}{= \sum_{1 \le k \le N} H_k} & \text{extract coefficient of } z^N \\ \end{aligned} \]

But recall from above

\[ \begin{aligned} \color{teal}{\frac{1}{(1 - z)^2} \ln \frac{1}{1 - z}} &\color{teal}{= \big(\sum_{N \ge 0}(N+1)z^N\big) \big(\sum_{k \ge 1} \frac{1}{k} z^k\big)} \\ &= \sum_{N \ge 0} \sum_{k \ge 1} (N+1) \frac{1}{k} z^{N+k} \\ &= \sum_{N \ge k} \sum_{k \ge 1} (N-k + 1) \frac{1}{k} z^{N} & \text{re-index} \\ &= \sum_{N \ge 1} \big( \sum_{1 \le k \le N} (N+1-k) \frac{1}{k} \big) z^{N} \\ &= \sum_{N \ge 1} \big( \sum_{1 \le k \le N} (\frac{1}{k}(N + 1) - 1) \big) z^{N} \\ &= \sum_{N \ge 1} \big( \color{blue}{H_N (N + 1) - N} \big) z^{N} \\ \color{blue}{[z^N] \frac{1}{(1 - z)^2} \ln \frac{1}{1 - z}} &\color{blue}{= H_N (N + 1) - N} & \text{extract coefficient of } z^N \\ \therefore \sum_{1 \le k \le N} H_k &= H_N (N + 1) - N \\ \end{aligned} \]

Now

\[ \begin{aligned} H_{N+1} &= H_N + \frac{1}{N+1} \\ H_N &= H_{N+1} - \frac{1}{N+1} \\ \sum_{1 \le k \le N} H_k &= (H_{N+1} - \frac{1}{N+1}) (N + 1) - N \\ &= (N + 1) H_{N+1} - 1 - N = (N + 1) H_{N+1} - (N+1) \\ \sum_{1 \le k \le N} H_k &= (N+1)(H_{N+1} - 1) \\ \end{aligned} \]

\(\Box\)

Source: Analysis of Algorithm

Solve the recurrence

\[ \begin{aligned} A_N &= A_{N-1} - \frac{A_{N-1}}{N} + 2\big(1 - \frac{2A_{N-1}}{N} \big) & \text{for } N > 0 \text{ with } A_0 = 0.\\ \end{aligned} \]

Attempt:

\[ \begin{aligned} N A_N &= N A_{N-1} - 2A_{N-1} + 2N - 4A_{N-1} \\ &= (N - 6) A_{N-1} + 2N \\ A_N &= \frac{N - 6}{N} A_{N-1} + 2 \\ \frac{N!}{(N-6)!} A_N &= \frac{N!}{(N-6)!} \big(\frac{N - 6}{N} A_{N-1} + 2\big) & \text{divide by summation factor of }\frac{(N-6)!}{N!} \\ &= \frac{(N-1)!}{(N-7)!} A_{N-1} + 2 \frac{N!}{(N-6)!} \\ \frac{N!}{(N-6)!6!} A_N &= \frac{(N-1)!}{(N-7)!6!} A_{N-1} + 2 \frac{N!}{(N-6)!6!} & \text{divide by }6! \\ {N \choose 6} A_N &= {N-1 \choose 6} A_{N-1} + 2 {N \choose 6} & \text{note } N \text{ must be }> 6\\ &= {7 \choose 6} A_{7} + 2 {8 \choose 6} + \cdots + 2 {N \choose 6} & \text{telescope} \\ &= 7 A_{7} + 2 \sum_{k=8}^N {k \choose 6} \\ &= 7 A_{7} + 2 \sum_{k=0}^N {k \choose 6} - 2 \sum_{k=0}^7 {k \choose 6} \\ &= 7 A_{7} + 2 {N+1 \choose 6+1} - 2 {7+1 \choose 6+1} & \text{sum of binomial coefficients over upper index} \\ A_N &= \frac{1}{{N \choose 6}} \big(7 A_{7} + 2 {N+1 \choose 7} - 16 \big) \\ \end{aligned} \]

Recall \(A_N = \frac{N - 6}{N} A_{N-1} + 2\), and \(A_0 = 0\). So

\[ \begin{aligned} A_1 &= \frac{1 - 6}{1} A_0 + 2 = 2 \\ A_2 &= \frac{2 - 6}{2} A_1 + 2 = -2 \\ A_3 &= \frac{3 - 6}{3} A_2 + 2 = 4 \\ A_4 &= \frac{4 - 6}{4} A_3 + 2 = 0 \\ A_5 &= \frac{5 - 6}{5} A_4 + 2 = 2 \\ A_6 &= \frac{6 - 6}{6} A_5 + 2 = 2 \\ A_7 &= \frac{7 - 6}{7} A_6 + 2 = \frac{16}{7} \\ \therefore A_N &= \frac{1}{{N \choose 6}} \big(16 + 2 {N+1 \choose 7} - 16 \big) = \frac{2}{{N \choose 6}} {N+1 \choose 7} \\ &= \frac{2 (N+1)!}{7! (N+1-7)!}\cdot \frac{6! (N-6)!}{N!} \\ A_N &= \frac{2}{7}(N+1) & \text{!} \\ \end{aligned} \]

\(\Box\)

See: Sum of Binomial Coefficients over Upper Index

Source: Analysis of Algorithm

Number of comparisons in mergesort:

\[ \begin{aligned} C_N &= C_{\lfloor N/2 \rfloor} + C_{\lceil N/2 \rceil} + N & \text{ for } N > 1 \text{ with } C_1 = 0 \\ \end{aligned} \]

How do we solve for \(C_N\) ?

\[ \begin{aligned} C_{N+1} &= C_{\lfloor (N+1)/2 \rfloor} + C_{\lceil (N+1)/2 \rceil} + N + 1 \\ &= C_{\lceil N/2 \rceil} + C_{\lfloor N/2 \rfloor + 1} + N + 1 & \text{!}\\ C_{N+1} - C_N &= C_{\lfloor N/2 \rfloor + 1} - C_{\lfloor N/2 \rfloor} + 1 \\ \end{aligned} \]

Now, let

\[ \begin{aligned} D_N &= C_{N+1} - C_N \\ &= C_{\lfloor N/2 \rfloor + 1} - C_{\lfloor N/2 \rfloor} + 1 \\ \therefore D_N &= D_{\lfloor N/2 \rfloor} + 1 \\ \end{aligned} \]

Note

\[ \begin{aligned} D_1 &= C_{1+1} - C_1 = C_2 - C_1 = C_2 \\ C_2 &= C_{\lfloor 2/2 \rfloor} + C_{\lceil 2/2 \rceil} + 2 \\ &= C_1 + C_1 + 2 = 2 \\ \therefore D_1 &= 2 \\ D_N &= D_{\lfloor N/2 \rfloor} + 1 \\ &= D_1 + \lfloor \ln N \rfloor & \text{telescope} \\ \therefore D_N &= \lfloor \ln N \rfloor + 2 \\ \end{aligned} \]

Solving for \(C_N\),

\[ \begin{aligned} C_{N+1} &= C_N + D_N & \text{rearranging terms} \\ &= C_N + \lfloor \ln N \rfloor + 2\\ &= C_1 + (\lfloor \ln 1 \rfloor + 2) + \cdots + (\lfloor \ln N \rfloor + 2) & \text{telescope} \\ &= 2N + C_1 + \sum_{k=1}^N \lfloor \ln k \rfloor \\ &= 2N + \sum_{k=1}^N \lfloor \ln k \rfloor \\ C_N &= 2(N-1) + \sum_{k=1}^{N-1} \lfloor \ln k \rfloor \\ &= (N-1) + \sum_{k=1}^{N-1} \big(\lfloor \ln k \rfloor + 1\big) \\ C_N &= N - 1 + \sum_{k=1}^{N-1} \big(\lfloor \ln k \rfloor + 1\big) \\ \end{aligned} \]

Note \(\lfloor \ln k \rfloor + 1\) is the number if bits in the binary representation of k. Here is why.

• Let \(B_N\) be the number if bits in the binary representation of \(N\).
• Obviously, \(B_1 = 1\).
• removing the right most bit of \(N\) gives \(\lfloor N/2 \rfloor \).

Therefore \(B_N = B_{\lfloor N/2 \rfloor} + 1\) is the number of bits in the binary representation of N, for \(N > 1\) with \(B_1 = 1\). Interestingly, this happens to be the same recurrence as binary search. Now

\[ \begin{aligned} B_N &= B_{\lfloor N/2 \rfloor} + 1 \\ &= B_1 + \lfloor \ln N \rfloor & \text{telescope} \\ \therefore B_N &= \lfloor \ln N \rfloor + 1 \\ \end{aligned} \]

Thus the theorem:

\[ \begin{aligned} C_N = N −1 + \text{ number of bits in binary representation of all numbers} < N. \end{aligned} \]

Let \(S_N\) be the number of bits in binary representation of all numbers \(< N\).

\[ \begin{aligned} S_N &= \sum_{k=1}^{N-1} B_k \\ &= \sum_{k=1}^{N-1} \big(\lfloor \ln k \rfloor + 1\big) \\ \end{aligned} \]

When the binary representations of all numbers from \(0\) to \(N-1\) is laid out, all the bits can be viewed as being contained in a rectangle of \(N\) by \(\ln \lfloor N \rfloor + 1\). Subtracting all the leading zeros column by column, we get

\[ \begin{aligned} S_N &= N (\lfloor \ln N \rfloor + 1) - \sum_{k=0}^{\lfloor \ln N \rfloor} 2^k \\ &= N (\lfloor \ln N \rfloor + 1) - (2^{\lfloor \ln N \rfloor + 1} - 1) \\ &= N \lfloor \ln N \rfloor - 2^{\lfloor \ln N \rfloor + 1} + N + 1 \\ \end{aligned} \]

Now, recall

\[ \begin{aligned} C_N &= N − 1 + \text{ number of bits in binary representation of all numbers} < N \\ &= N - 1 + S_N \\ \therefore C_N &= N \lfloor \ln N \rfloor - 2^{\lfloor \ln N \rfloor + 1} + 2N & \text{!} \\ \end{aligned} \]

\(\Box\)

Source: Analysis of Algorithm

Solve the recurrence:

\[ \begin{aligned} A_N &= 1 + \frac{2}{N}\sum_{j=1}^N A_{j-1} &\text{ for } N > 0 \\ N A_N &= N + 2\sum_{j=1}^N A_{j-1} \\ (N-1) A_{N-1} &= (N-1) + 2\sum_{j=1}^{N-1} A_{j-1} &\text{for } N-1 \text{ instead of } N \\ NA_N - (N-1)A_{N-1} &= 1 + 2A_{N-1} &\text{subtract the last two equations}\\ NA_N &= (N+1)A_{N-1} + 1 &\text{note it's now linear time, not quadratic!}\\ \frac{A_N}{N+1} &= \frac{A_{N-1}}{N} + \frac{1}{N(N+1)} &\text{divide both sides by } N(N+1) \\ \frac{A_N}{N+1} &= \frac{A_{1}}{2} + \frac{1}{2 \cdot 3} + \cdots + \frac{1}{N(N+1)} &\text{telescope} \\ &= \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \cdots + \frac{1}{N(N+1)} &\text{note }A_1 = 1 \text{, assuming } A_0 = 0 \\ A_N &= (N+1) \sum_{k=1}^N \frac{1}{k(k+1)} \\ &= (N+1) \sum_{k=1}^N (\frac{1}{k} - \frac{1}{k+1}) & \text{partial fraction} \\ &= (N+1) (1 - \frac{1}{N+1}) & \text{telescoping series} \\ A_N &= N & \Box \\ \end{aligned} \]

Alternatively, instead of using telescoping series,

\[ \begin{aligned} A_N &= (N+1) \sum_{k=1}^N (\frac{1}{k} - \frac{1}{k+1}) \\ A_N &\thicksim N \sum_{k=1}^N (\frac{1}{k} - \frac{1}{k+1}) & f(x) \thicksim g(x) \text{ means} \lim_{x\rightarrow\infty}\frac{f(x)}{g(x)} = 1 \\ &= N \big(\sum_{k=1}^N \frac{1}{k} - \sum_{k=1}^N \frac{1}{k+1}\big) \\ \end{aligned} \]

By the definition of Euler's constant,

\[ \begin{aligned} \gamma &= \lim_{N \rightarrow \infty} \big( \sum_{k=1}^N \frac{1}{k} - \ln N \big) \\ \therefore \lim_{N \rightarrow \infty} \big( \sum_{k=1}^N \frac{1}{k} &= \ln N + \gamma \big) \\ \gamma &= 1 + \lim_{N \rightarrow \infty} \big( \sum_{k=2}^N \frac{1}{k} - \ln N \big) & \text{pull out the 1st term} \\ &= 1 + \lim_{N \rightarrow \infty} \big( \sum_{k=1}^{N-1} \frac{1}{k+1} - \ln N \big) & \text{re-index} \\ \lim_{N \rightarrow \infty} \big( \sum_{k=1}^{N-1} \frac{1}{k+1} &= \ln N + \gamma - 1 \big) \\ \therefore \lim_{N \rightarrow \infty} \big( \sum_{k=1}^{N} \frac{1}{k+1} &= \ln (N+1) + \gamma - 1 \big) & \text{for } N+1 \text{ instead of } N \\ \end{aligned} \]

Hence

\[ \begin{aligned} A_N &\thicksim N \big(\sum_{k=1}^N \frac{1}{k} - \sum_{k=1}^N \frac{1}{k+1}\big) \\ A_N &\thicksim N \big[ \big(\ln N + \gamma\big) - \big(\ln (N+1) + \gamma - 1\big) \big] \\ A_N &\thicksim N \big(\ln N - \ln (N+1) + 1\big) \\ A_N &\thicksim N &\Box \\ \end{aligned} \]

Source: Analysis of Algorithm

Assume array of size \(N\) with entries distinct and randomly ordered. Let \(C_N\) be the expected number of compares used by quicksort. Starting with the recurrence relation:

\[ \begin{aligned} C_N &= N + 1 + \sum_{k=1}^N \frac{1}{N}(C_{k-1} + C_{N-k}) & C_0 = 0\\ &= N + 1 + \frac{2}{N}\sum_{k=1}^N C_{k-1} &\text{by symmetry} \\ NC_N &= N(N + 1) + 2\sum_{k=1}^N C_{k-1} \\ (N-1)C_{N-1} &= (N - 1)N + 2\sum_{k=1}^{N-1} C_{k-1} &\text{for } N-1 \text{ instead of } N \\ NC_N - (N-1)C_{N-1} &= 2N + 2C_{N-1} &\text{subtract the last two equations}\\ NC_N &= (N+1)C_{N-1} + 2N & \text{note it's now linear time, not quadratic!}\\ \frac{C_N}{N+1} &= \frac{C_{N-1}}{N} + \frac{2}{N+1} &\text{divide both sides by } N(N+1) \\ \frac{C_N}{N+1} &= \frac{C_{N-1}}{N} + \frac{2}{N+1} = \frac{C_{N-2}}{N-1} + \frac{2}{N} + \frac{2}{N+1} &\text{telescope} \\ \frac{C_N}{N+1} &= \frac{C_1}{2} + \frac{2}{3} + \cdots + \frac{2}{N} + \frac{2}{N+1} & \text{note } C_1 = 2 \\ C_N &= (N + 1) (1 + \frac{2}{3} + \cdots + \frac{2}{N}) + 2 \\ C_N &\thicksim N (1 + \frac{2}{3} + \cdots + \frac{2}{N}) & f(x) \thicksim g(x) \text{ means} \lim_{x\rightarrow\infty}\frac{f(x)}{g(x)} = 1\\ C_N &\thicksim N + 2N(\frac{1}{3} + \cdots + \frac{1}{N}) \\ C_N &\thicksim N + 2N(1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{N}) - 3N \\ C_N &\thicksim 2N \sum_{k=1}^N \frac{1}{k} - 2N \\ C_N &\thicksim 2N (\int_1^N\frac{1}{x}\,dx + \gamma) - 2N & \gamma = \text{Euler's constant} \approx .57721 \\ &= 2N \ln N - 2(1 - \gamma) N \qquad & \text{Isn't this amazing ?}\\ \end{aligned} \]

Source: Analysis of Algorithm