Editing Lucas number (section)

==Generating function==

Let

:<math>\Phi(x) = 2 + x + 3x^2 + 4x^3 + \cdots = \sum_{n = 0}^\infty L_nx^n</math>

be the [[generating function]] of the Lucas numbers. By a direct computation,

:<math>\begin{align}
  \Phi(x) &= L_0 + L_1x + \sum_{n = 2}^\infty L_nx^n \\
          &= 2 + x + \sum_{n = 2}^\infty (L_{n - 1} + L_{n - 2})x^n \\
          &= 2 + x + \sum_{n = 1}^\infty L_nx^{n + 1} + \sum_{n = 0}^\infty L_nx^{n + 2} \\
          &= 2 + x + x(\Phi(x) - 2) + x^2 \Phi(x)
\end{align}</math>

which can be rearranged as

:<math>\Phi(x) = \frac{2 - x}{1 - x - x^2}</math>

<math>\Phi\!\left(-\frac{1}{x}\right)</math> gives the generating function for the [[#Extension_to_negative_integers|negative indexed Lucas numbers]], <math>\sum_{n = 0}^\infty (-1)^nL_nx^{-n} = \sum_{n = 0}^\infty L_{-n}x^{-n}</math>, and

:<math>\Phi\!\left(-\frac{1}{x}\right) = \frac{x + 2x^2}{1 - x - x^2}</math>

<math>\Phi(x)</math> satisfies the [[functional equation]]

:<math>\Phi(x) - \Phi\!\left(-\frac{1}{x}\right) = 2</math>

As the [[Fibonacci number#Generating function|generating function for the Fibonacci numbers]] is given by

:<math>s(x) = \frac{x}{1 - x - x^2}</math>

we have

:<math>s(x) + \Phi(x) = \frac{2}{1 - x - x^2}</math>

which [[mathematical proof|proves]] that

:<math>F_n + L_n = 2F_{n+1},</math>

and

:<math>5s(x) + \Phi(x) = \frac2x\Phi(-\frac1x) = 2\frac{1}{1 - x - x^2} + 4\frac{x}{1 - x - x^2}</math>

proves that

:<math>5F_n + L_n = 2L_{n+1}</math>

The [[partial fraction decomposition]] is given by

:<math>\Phi(x) = \frac{1}{1 - \phi x} + \frac{1}{1 - \psi x}</math>

where <math>\phi = \frac{1 + \sqrt{5}}{2}</math> is the golden ratio and <math>\psi = \frac{1 - \sqrt{5}}{2}</math> is its [[conjugate (square roots)|conjugate]].

This can be used to prove the generating function, as

:<math>\sum_{n = 0}^\infty L_nx^n = \sum_{n = 0}^\infty (\phi^n + \psi^n)x^n = \sum_{n = 0}^\infty \phi^nx^n + \sum_{n = 0}^\infty \psi^nx^n = \frac{1}{1 - \phi x} + \frac{1}{1 - \psi x} = \Phi(x)</math>