Given a function $f(x)$ that is define by $f(x-1)$, by knowing $f(0)$ is it possible to rewrite $f(x)$ without using $f(x-1)$

Question

Let a function $f(x)$ that is written using the function itself. Something like Fibonacci sequence $f(x)=f(x-2)+f(x-1)$. Now given enough result of $f(x)$ (in the example of Fibonacci sequence, $f(1)$ and $f(2)$), is it possible to rewrite the function so that it doesn’t require calling itself again, but only uses the input $x$ and the pre-given results (again for Fibonacci sequence it can be written as $f(x)=\frac{\phi^x-(1-\phi)^x}{\sqrt 5}$? Is it possible to prove that any of these self-calling function could be rewritten?

Answer 1

Let me start by saying that expressions such as recursive definition of the Fibonacci sequence you mentioned are usually called recurrence relations. From what I gathered, you ask the question of whether or not such recurrence relations always admit closed form solutions. Indeed this is not the case as explained e.g. here, however for large classes of recurrence relations it can be shown that closed form solutions exist. One particular such class is linear recurrence relations with constant coefficients like the Fibonacci recurrence where one can use linear algebra to obtain a closed form solution by defining a linear function $T$ which given some vector consisting of $k$ values of the sequence described by the recurrence and some initial values (which is what you call $f(0)$) produces another such vector containing elements of the aforementioned sequence further along the index. One can then find a formula for the $n$th sequence element by repeatedly applying $T$ to the initial values, which really boils down to multiplying a matrix $A_T$ representing $T$ to the vector of initial values a bunch. A closed form solution for the powers of $A_T$ needed for this can be obtained using Eigendecompositions.