0

If I have a linear recurrence relation such as $f_n=f_{n+1}+f_{n+2}$ or $f_n=f_{n+1}+k$, how can I find a formula that will give me a function to represent these relations in a non-recursive way?

Is there a generic approach to solving these, assuming you have something of the form $f_n=Af_a + Bf_b + Cf_c + ... + K$, where $a,b,c...<n$ and $A,B,C,...$ and $K$ are constants?

Kvass
  • 367

1 Answers1

2

In some cases, if the recurrence is linear, you can use a matrix to express it and then you may be able to diagonalize the representing matrix; this is done, e.g., with the Fibonnaci series, which can be expressed in closed form in precisely this way.

BFD
  • 56