[andrewp123]

A powerful method in math is to assume the thing you're looking for is continuous, in which case you can write it F(n) = a0 + a1 n + a2 n^2 + ... .

You can solve Fibonacci by writing it as

a0 + a1 n + a2 n^2 + ...

= a0 + a1 (n-1) + a2 (n-1)^2 + ...

+ a0 + a1 (n-2) + a2 (n-2)^2 + ...

Expand terms, then match the n, n^2, n^3 etc terms and solve for a0, a1, a2, etc. This works in solving differential equations too - it's called "Method of Frobenius" (easier in diffeq because you don't have to do annoying binomial coefficient math).