Binet Form

From ProofWiki
Jump to: navigation, search

Theorem

First Form

The recursive sequence:

$U_n = m U_{n-1} + U_{n-2}$

where:

\(\displaystyle U_0\) \(=\) \(\displaystyle 0\) $\quad$ $\quad$
\(\displaystyle U_1\) \(=\) \(\displaystyle 1\) $\quad$ $\quad$

has the closed-form solution:

$U_n = \dfrac {\alpha^n - \beta^n} {\Delta}$

where:

\(\displaystyle \Delta\) \(=\) \(\displaystyle \sqrt {m^2 + 4}\) $\quad$ $\quad$
\(\displaystyle \alpha\) \(=\) \(\displaystyle \frac {m + \Delta} 2\) $\quad$ $\quad$
\(\displaystyle \beta\) \(=\) \(\displaystyle \frac {m - \Delta} 2\) $\quad$ $\quad$


Second Form

The recursive sequence:

$V_n = m V_{n-1} + V_{n-2}$

where:

\(\displaystyle V_0\) \(=\) \(\displaystyle 2\) $\quad$ $\quad$
\(\displaystyle V_1\) \(=\) \(\displaystyle m\) $\quad$ $\quad$

has the closed-form solution:

$V_n = \alpha^n + \beta^n$

where $\Delta, \alpha, \beta$ are as for the first form.


Relation Between First and Second Form

For any given value of $m$:

$U_{n-1} + U_{n+1} = V_n$


Proof


Source of Name

This entry was named for Jacques Philippe Marie Binet.


Sources