Commit4cdc4df

authored

Fibonacci: better motivation for matrix form

1 parent91672f0 commit4cdc4dfCopy full SHA for 4cdc4df

File tree

+41

-2

lines changed

+41

-2

lines changed

Lines changed: 41 additions & 2 deletions

Original file line number	Diff line number	Diff line change
`@@ -116,9 +116,48 @@ In this way, we obtain a linear solution, $O(n)$ time, saving all the values pri`
`116`	`116`
`117`	`117`	`### Matrix form`
`118`	`118`
`119`		`-It is easytoprovethefollowing relation:`
	`119`	`+To go from $(F_n, F_{n-1})$to$(F_{n+1}, F_n)$, we can expressthelinear recurrence as a 2x2 matrix multiplication:`
`120`	`120`
`121`		`-$$\begin{pmatrix} 1 & 1 \cr 1 & 0 \cr\end{pmatrix} ^ n = \begin{pmatrix} F_{n+1} & F_{n} \cr F_{n} & F_{n-1} \cr\end{pmatrix}$$`
	`121`	`+$$`
	`122`	`+\begin{pmatrix}`
	`123`	`+1 & 1 \\`
	`124`	`+1 & 0`
	`125`	`+\end{pmatrix}`
	`126`	`+\begin{pmatrix}`
	`127`	`+F_n \\`
	`128`	`+F_{n-1}`
	`129`	`+\end{pmatrix}`
	`130`	`+=`
	`131`	`+\begin{pmatrix}`
	`132`	`+F_n + F_{n-1} \\`
	`133`	`+F_{n}`
	`134`	`+\end{pmatrix}`
	`135`	`+=`
	`136`	`+\begin{pmatrix}`
	`137`	`+F_{n+1} \\`
	`138`	`+F_{n}`
	`139`	`+\end{pmatrix}`
	`140`	`+$$`
	`141`	`+`
	`142`	`+This lets us treat iterating the recurrence as repeated matrix multiplication, which has nice properties. In particular,`
	`143`	`+`
	`144`	`+$$`
	`145`	`+\begin{pmatrix}`
	`146`	`+1 & 1 \\`
	`147`	`+1 & 0`
	`148`	`+\end{pmatrix}^n`
	`149`	`+\begin{pmatrix}`
	`150`	`+F_1 \\`
	`151`	`+F_0`
	`152`	`+\end{pmatrix}`
	`153`	`+=`
	`154`	`+\begin{pmatrix}`
	`155`	`+F_{n+1} \\`
	`156`	`+F_{n}`
	`157`	`+\end{pmatrix}`
	`158`	`+$$`
	`159`	`+`
	`160`	`+where $F_1 = 1, F_0 = 0$.`
`122`	`161`
`123`	`162`	`Thus, in order to find $F_n$ in $O(log n)$ time, we must raise the matrix to n. (See [Binary exponentiation](binary-exp.md))`
`124`	`163`

Comments

(0)