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

# posted by rot13(Unafba Pune) @ 11:14 AM