Re:Generating Functions and Fibonacci Numbers
by btilly on Saturday November 02, 2013 @06:52PM
(#6661205)
There are actually perfectly routine ways to discover formulas like this one for this type of equation. See http://en.wikipedia.org/wiki/Recurrence_relation for some of the theory behind how to do it.
It's the tip of the iceberg though - generatingfunctionology is worth inspecting thoroughly.