# Is it possible to find an explicit function for any given recursive sequence?

There are problems where we need to find an explicit formula for some recursive sequence such as the Fibonacci sequence, defined by $f_0=0, f_1=1,f_n=f_{n-1}+f_{n-2}$ where we can find $f_n$ in terms of $n$ only, or another example is $a_1=1,a_2=2,a_n=2a_{n-1}+3a_{n-2}$ where we can find $a_n$ in terms of $a_1,a_2,n$. I'm wondering if it is possible to find an explicit function for any given recursive sequence, in terms of at least one term of the set $\{a_1,a_2,...,a_k,n\}$.

• Are you specifically interested in linear recurrences? If so, then yes. See, e.g., this for the examples you discuss. These methods can be generalized (but the linearity is crucial). – lulu Jan 4 '17 at 12:33
• @lulu thanks for the link! – user394255 Jan 4 '17 at 12:46
• @lulu thanks for the link as well. I'll probably have a better look at these in the future. – Michalis P. Jan 4 '17 at 13:18