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

4 Answers

0 like 0 dislike
0 like 0 dislike
> 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.
0 like 0 dislike
0 like 0 dislike
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.
by
0 like 0 dislike
0 like 0 dislike
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.
0 like 0 dislike
0 like 0 dislike
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.

Related questions

0 like 0 dislike
0 like 0 dislike
3 answers
SalvadorHeresi asked Jun 21
Is there any reason to believe that big unsolved conjectures are either provable / disprovable in ZFC?
SalvadorHeresi asked Jun 21
0 like 0 dislike
0 like 0 dislike
11 answers
phillyvictor asked Jun 21
Can any number theorists explain the patterns going on in this factorization? (Sorta relevant to cyclotomic polynomials.)
phillyvictor asked Jun 21
0 like 0 dislike
0 like 0 dislike
10 answers
0 like 0 dislike
0 like 0 dislike
2 answers
Booksmart asked Jun 21
Any good or equal alternatives to Microsoft Mathematics?
Booksmart asked Jun 21
0 like 0 dislike
0 like 0 dislike
10 answers
JanosHermanEU asked Jun 21
Would it be possible to model any possible curve to a mathematical model given data points only?
JanosHermanEU asked Jun 21

24.8k questions

103k answers

0 comments

33.7k users

OhhAskMe is a math solving hub where high school and university students ask and answer loads of math questions, discuss the latest in math, and share their knowledge. It’s 100% free!