Binet Form

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $m \in \R$.

Define:

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

First Form

The recursive sequence:

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

where:

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

has the closed-form solution:

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


Second Form

The recursive sequence:

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

where:

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

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

Proof by induction:

Let $\map P n$ be the proposition:

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

Basis for the Induction

We have:

\(\displaystyle U_0 + U_2\) \(=\) \(\displaystyle 0 + m U_1 + U_0\)
\(\displaystyle \) \(=\) \(\displaystyle m \times 1 + 0\)
\(\displaystyle \) \(=\) \(\displaystyle m\)
\(\displaystyle \) \(=\) \(\displaystyle V_1\) From definition
\(\displaystyle U_1 + U_3\) \(=\) \(\displaystyle 1 + m U_2 + U_1\)
\(\displaystyle \) \(=\) \(\displaystyle m \times m + 2\)
\(\displaystyle \) \(=\) \(\displaystyle m \times V_1 + V_0\)
\(\displaystyle \) \(=\) \(\displaystyle V_2\) From definition

Therefore $\map P 1$ and $\map P 2$ are true.

This is the basis for the induction.


Induction Hypothesis

This is our induction hypothesis:

For some $k \in \N_{> 0}$, both $\map P k$ and $\map P {k + 1}$ are true.

That is:

$U_{k - 1} + U_{k + 1} = V_k$
$U_k + U_{k + 2} = V_{k + 1}$


Now we need to show true for $n = k + 2$:

$\map P {k + 2}$ is true.

That is:

$U_{k + 1} + U_{k + 3} = V_{k + 2}$


Induction Step

This is our induction step:

\(\displaystyle V_{k + 2}\) \(=\) \(\displaystyle m V_{k + 1} + V_k\) Definition of the recursive sequence
\(\displaystyle \) \(=\) \(\displaystyle m \paren {U_k + U_{k + 2} } + \paren {U_{k - 1} + U_{k + 1} }\) Induction Hypothesis
\(\displaystyle \) \(=\) \(\displaystyle \paren {m U_k + U_{k - 1} } + \paren {m U_{k + 2} + U_{k + 1} }\)
\(\displaystyle \) \(=\) \(\displaystyle U_{k + 1} + U_{k + 3}\)

This show that $\map P {k + 2}$ is true.

By principle of mathematical induction, $\map P n$ is true for all $n \in \N _{> 0}$.

$\blacksquare$


Source of Name

This entry was named for Jacques Philippe Marie Binet.


Sources