Editing Fibonacci sequence (section)

== Generating function ==
The [[generating function]] of the Fibonacci sequence is the [[power series]]

<math display=block>
s(z) = \sum_{k=0}^\infty F_k z^k = 0 + z + z^2 + 2z^3 + 3z^4 + 5z^5 + \dots.
</math>

This series is convergent for any [[complex number]] <math>z</math> satisfying <math>|z| < 1/\varphi \approx 0.618,</math> and its sum has a simple closed form:<ref>{{Citation | last = Glaister | first = P | title = Fibonacci power series | journal = The Mathematical Gazette | year = 1995 | doi = 10.2307/3618079 | volume = 79 | issue = 486| pages = 521–25 | jstor = 3618079 | s2cid = 116536130 }}</ref>

<math display=block>s(z)=\frac{z}{1-z-z^2}.</math>

This can be proved by multiplying by <math display="inline">(1-z-z^2)</math>:
<math display=block>\begin{align}
(1 - z- z^2) s(z)
  &= \sum_{k=0}^{\infty} F_k z^k - \sum_{k=0}^{\infty} F_k z^{k+1} - \sum_{k=0}^{\infty} F_k z^{k+2} \\
  &= \sum_{k=0}^{\infty} F_k z^k - \sum_{k=1}^{\infty} F_{k-1} z^k - \sum_{k=2}^{\infty} F_{k-2} z^k \\
  &= 0z^0 + 1z^1 - 0z^1 + \sum_{k=2}^{\infty} (F_k - F_{k-1} - F_{k-2}) z^k \\
  &= z,
\end{align}</math>

where all terms involving <math>z^k</math> for <math>k \ge 2</math> cancel out because of the defining Fibonacci recurrence relation.

The [[partial fraction decomposition]] is given by
<math display=block>s(z) = \frac{1}{\sqrt5}\left(\frac{1}{1 - \varphi z} - \frac{1}{1 - \psi z}\right)</math>
where <math display=inline>\varphi = \tfrac12\left(1 + \sqrt{5}\right)</math> is the golden ratio and <math>\psi = \tfrac12\left(1 - \sqrt{5}\right)</math> is its [[Conjugate (square roots)|conjugate]].

The related function <math display=inline>z \mapsto -s\left(-1/z\right)</math> is the generating function for the [[negafibonacci]] numbers, and <math>s(z)</math> satisfies the [[functional equation]]

<math display=block>s(z) = s\!\left(-\frac{1}{z}\right).</math>

Using <math>z</math> equal to any of 0.01, 0.001, 0.0001, etc. lays out the first Fibonacci numbers in the decimal expansion of <math>s(z)</math>.  For example, <math>s(0.001) = \frac{0.001}{0.998999} = \frac{1000}{998999} = 0.001001002003005008013021\ldots.</math>