$$\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

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