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

# posted by rot13(Unafba Pune) @ 10:12 PM