(50g) Nth Fibonacci Number

[Han]

(02-27-2015 01:48 PM)rprosperi Wrote:  

(02-27-2015 05:58 AM)Thomas Klemm Wrote:  A poor man's approach to solve the recurrence would be to use the ansatz
[snip]
PS: I feel a little bit like cheating as there's no explanation for why this ansatz works.

So it appears an ansatz is a postulated theorem for some behavior which works, but without knowing why?

My suspicion is that it is tied to the fact that the Fibonacci sequence is a linear recurrence. All linear recurrences will have rational generating functions (i.e. the \( f(x) \) in my earlier post will always be of the form \( \frac{p(x)}{q(x)} \) for polynomials \( p(x) \) and \( q(x) \)). In the case of lower order recurrences, one can often obtain a partial fraction decomposition of the rational function which then leads to solutions of the aforementioned forms.