Question

Is it always possible to derive an explicit form equation for any recursive sequence?

Answer 1

> It seems likely that any recursive sequence with a single initial condition - specifically, you have an x0, and then every other term f(x) is some function of only the term before it - should be able to get translated into explicit form every time.

Not at all.  As an analogue, do you expect any first-order ODE with an initial condition should have an "explicit" solution formula?  The scope of *any* recursion and *any* ODE is extremely broad.  If you had been speaking about *linear* recursions or *linear* differential equations, that's one thing, but when you allow anything at all, then nonlinear possibilities are going to make things extremely difficult when the goal is explicit solution formulas.

Answer 2

I think you meant something like:

f(0)=1

f(1)=3

f(x)=.25\*f(x-1)+2\*f(x-2)

I don't have a perfect rationale for it, but if you assume that f(x) is roughly exponential, you get:

a^x = 0.25\*a^x-1 + 2\*a^x-2

a^2 = 0.25\*a+2

a^2 -0.25a-2=0

a=(1±√(129))/8

And so let f(x)=c((1+√(129))/8)^x +d((1-√(129))/8)^x, and you can solve for c and d by substituting the known values of x into the equation.
For recursive sequences with more terms, you just have a separate term for each root of the equivalent polynomial. If roots repeat, replace one of the a^x with x*a^x, and so on with higher powers of x(which you would learn in an ordinary differential equations class). You can use this to get a formula for the Fibonacci sequence without any intermediates.

Answer 3

If you allow yourself to argmin over the integers in the explicit formula, I imagine one can just use a Matiyasevich-style reduction to construct one.

Answer 4

Just a note. If you have a recurrence relation based on multiple terms, then you can change it to a vector so that it becomes a recurrence relation based on just one vector term only.

What allows you to "solve" recurrence relation algebraically is the same thing that allow you to solve an ODE algebraically: some sorts of "nice" symmetry. Linear is a very nice kind of symmetry, and even then you can't always solve a linear recurrence relation. Linear with constant coefficients has extremely nice symmetry that let you solve it explicitly. Because of that, you can generally take a method from ODE to solve a recurrence relation.