Editing Fibonacci sequence (section)

=== Decomposition of powers ===
Since the golden ratio satisfies the equation
<math display=block>\varphi^2 = \varphi + 1,</math>

this expression can be used to decompose higher powers <math>\varphi^n</math> as a linear function of lower powers, which in turn can be decomposed all the way down to a linear combination of <math>\varphi</math> and 1. The resulting [[recurrence relation]]ships yield Fibonacci numbers as the linear [[coefficient]]s:
<math display=block>\varphi^n = F_n\varphi + F_{n-1}.</math>
This equation can be [[Mathematical proof|proved]] by [[Mathematical induction|induction]] on {{math|''n'' ≥ 1}}:
<math display=block>\begin{align}
\varphi^{n+1} &= (F_n\varphi + F_{n-1})\varphi = F_n\varphi^2 + F_{n-1}\varphi \\
&= F_n(\varphi+1) + F_{n-1}\varphi = (F_n + F_{n-1})\varphi + F_n = F_{n+1}\varphi + F_n.
\end{align}</math>
For <math>\psi = -1/\varphi</math>, it is also the case that <math>\psi^2 = \psi + 1</math> and it is also the case that
<math display=block>\psi^n = F_n\psi + F_{n-1}.</math>

These expressions are also true for {{math|''n'' < 1}} if the Fibonacci sequence ''F<sub>n</sub>'' is [[Generalizations of Fibonacci numbers#Extension to negative integers|extended to negative integers]] using the Fibonacci rule <math>F_n = F_{n+2} - F_{n+1}.</math>