Computing Fibonacci Numbers

Yes we can! You can see the expression we get for $F(2n + 1)$ opposite. This only uses $F(n)^2$ and $F(n - 1)^2$ , so when combined with our other identity this lets us go from $n$ to $2n$ with only two squares and some addition/subtraction.

There's something in this set of manipulations, however, that gnaws at me. How would you find this without knowing it already existed?

Yes we can! You can see the expression we get for $F(2n + 1)$ opposite. This only uses $F(n)^2$ and $F(n - 1)^2$ , so when combined with our other identity this lets us go from $n$ to $2n$ with only two squares and some addition/subtraction.

There's something in this set of manipulations, however, that gnaws at me. How would you find this without knowing it already existed?