# The Recursive Form of Binet's Formula

The generalized Fibonacci sequence $$U_n$$ is defined by the recurrence relation $$U_n = pU_{n-1} + qU_{n-2}$$ where $$p,q \in \mathbb{Z}^+$$ and for all non-negative integers $$n$$ with initial condition $$U_0 = 0$$ and $$U_1 = 1$$ [1].

Let us begin with the Jacobsthal numbers $$J_n$$ which is a type of generalized Fibonacci sequence for which $$p := 1$$ and $$q := 2$$, with initial conditions $$J_0=0$$ and $$J_1=1$$:

$$J_n = \left\{ \begin{array}{c1} 0 & \mbox{if } n = 0 \\ 1 & \mbox{if } n = 1 \\ J_{n-1} + 2 J_{n-2} & \mbox{if } n > 1 \end{array} \right. \text.$$

The characteristic equation for the Jacobsthal numbers is $$x^2 - x - 2 = 0$$ with distinct real roots $$a = 2$$ and $$b = -1$$. Per Wikipedia, there are two recursive formulae that will give the next Jacobsthal number:

$$J_{n+1} = 2^n - J_n \hspace{12mm} \mbox{and} \hspace{12mm} J_{n+1} = 2J_n + (-1)^n \text,$$

both of which can be re-written with $$a$$ and $$b$$ respectively:

$$J_{n+1} = a^n + b J_n \hspace{12mm} \mbox{and} \hspace{12mm} J_{n+1} = b^n + a J_n \text.$$

Both recursive formulae utilize both roots and the current number to give the next number but can the formulae be generalized for any generalized Fibonacci sequence?

First the characteristic equation for the generalized Fibonacci sequence is defined as $$x^2-px-q=0$$ with distinct real roots: $$\alpha = \frac{p+\sqrt{p^2+4q}}{2}$$

and:

$$\beta = \frac{p-\sqrt{p^2+4q}}{2} \text.$$

We then introduce Binet's formula a closed-form solution for the nth term of a generalized Fibonacci sequence utilizing the distinct real roots $$\alpha$$ and $$\beta$$:

$$U_{n} = \frac{\alpha^n - \beta^n}{\alpha - \beta} \text.$$

From Binet's formula we can derive recursive formulae for any generalized Fibonacci sequence.

#### Proposition

$$\begin{array}{rl} U_{n+1} = & \alpha^n + \beta U_n \\ = & \beta^n + \alpha U_n \\ \end{array}$$

#### Proof

$$U_n = \frac{\alpha^n - \beta^n}{\alpha - \beta}$$ $$(\alpha - \beta) U_n = \alpha^n - \beta^n$$ $$\beta^n + \alpha U_n = \alpha^n + \beta U_n$$

Substitute $$\frac{\alpha^n - \beta^n}{\alpha - \beta}$$ for $$U_n$$:

$$\alpha^n + \beta \left( \frac{\alpha^n - \beta^n}{\alpha - \beta} \right) = \frac{\alpha^{n+1} - \alpha^n\beta + \alpha^n\beta - \beta^{n+1}}{\alpha-\beta} = \frac{\alpha^{n+1} - \beta^{n+1}}{\alpha - \beta} = U_{n+1}$$

and:

$$\beta^n + \alpha \left( \frac{\alpha^n - \beta^n}{\alpha-\beta} \right) = \frac{\alpha\beta^n - \beta^{n+1} + \alpha^{n+1} - \alpha\beta^n}{\alpha-\beta} = \frac{\alpha^{n+1} - \beta^{n+1}}{\alpha - \beta} = U_{n+1} \text.$$

#### Examples

Let $$p = 1$$ and we have $$\alpha = \frac{1+\sqrt{5}}{2} = 1.618033$$ and $$\beta = \frac{1-\sqrt{5}}{2} = -0.618033$$ and we confirm the Fibonacci numbers as expected. \begin{align} U_{n+1} &= \alpha^n+\beta U_n \\ U_0 &= 1.618033^{-1}-0.618033(1) = 0 \\ U_1 &= 1.618033^0-0.618033(0) = 1 \\ U_2 &= 1.618033^1-0.618033(1) = 1 \\ U_3 &= 1.618033^2-0.618033(1) = 2.618033-0.618033 = 2 \\ U_4 &= 1.618033^3-0.618033(2) = 4.236067-1.236067 = 3 \\ U_5 &= 1.618033^4-0.618033(3) = 6.854101-1.854101 = 5 \\ U_6 &= 1.618033^5-0.618033(5) = 11.090169-3.090169 = 8 \\[10pt] U_{n+1} &= \beta^n+\alpha U_n \\ U_0 &= (-0.618033)^{-1}+1.618033(1) = 0 \\ U_1 &= (-0.618033)^{0}+1.618033(0) = 1 \\ U_2 &= (-0.618033)^{1}+1.618033(1) = 1 \\ U_3 &= (-0.618033)^{2}+1.618033(1) = 0.381966+1.618033 = 2 \\ U_4 &= (-0.618033)^{3}+1.618033(2) = -0.236067+3.236067 = 3 \\ U_5 &= (-0.618033)^{4}+1.618033(3) = 0.145898+4.854101 = 5 \\ U_6 &= (-0.618033)^{5}+1.618033(5) = -0.090169+8.090169 = 8 \\ \end{align}

Let $$p = 2$$ and we have $$\alpha = 1+\sqrt{2} = 2.414213$$ and $$\beta = 1-\sqrt{2} = -0.414213$$ and we confirm the Pell numbers as expected. \begin{align} U_{n+1} &= \alpha^n+\beta U_n \\ U_0 &= 2.414213^{-1}-0.414213(1) = 0 \\ U_1 &= 2.414213^0-0.414213(0) = 1 \\ U_2 &= 2.414213^1-0.414213(1) = 2 \\ U_3 &= 2.414213^2-0.414213(2) = 5.828427-0.828427 = 5 \\ U_4 &= 2.414213^3-0.414213(5) = 14.071067-2.071067 = 12 \\ U_5 &= 2.414213^4-0.414213(12) = 33.970562-4.970562 = 29 \\ U_6 &= 2.414213^5-0.414213(29) = 82.012193-12.012193 = 70 \\[10pt] U_{n+1} &= \beta^n+\alpha U_n \\ U_0 &= (-0.414213)^{-1}+2.414213(1) = 0 \\ U_1 &= (-0.414213)^0+2.414213(0) = 1 \\ U_2 &= (-0.414213)^1+2.414213(1) = 2 \\ U_3 &= (-0.414213)^2+2.414213(2) = 0.171572+4.828427 = 5 \\ U_4 &= (-0.414213)^3+2.414213(5) = -0.071067+12.071067 = 12 \\ U_5 &= (-0.414213)^4+2.414213(12) = 0.029437+28.970562 = 29 \\ U_6 &= (-0.414213)^5+2.414213(29) = -0.012193+70.012193 = 70 \\ \end{align}

#### References

[1] AIP Conference Proceedings 1605, 661 (2014); https://doi.org/10.1063/1.4887668