Math Uber-Tier

[Anonymous No.4382049]

Hey, /sci/, was hoping you could help me with this one problem I'm stuck on.

I have an idea on how to solve it, but I need to ask you:

Is it always possible to change a recursive sequence into a non-recursive one? If not, why and if so, do you know any theorems that could help with this? Thanks.

[Anonymous No.4382065]

For example, every sequence defined by a linear recurrence with constant coefficients has a closed-form solution.

http://en.wikipedia.org/wiki/Recurrence_relation

http://en.wikipedia.org/wiki/Closed-form_solution

[Anonymous No.4382079]

>>4382065

What about sequences defined by a non-linear recurrence?

[Anonymous No.4382108]

>>4382079
they usually can't be solved
sadface.jpg

[Anonymous No.4382125]

>>4382108
Uh, yes they can.

[Anonymous No.4383578]

>>4382125

Care to enlighten us?

[sage No.4383588]

>>4382049
Please define 'change'.

[Anonymous No.4383596]

>>4383588

Given a non-linear recursive sequence, how do you find its closed-form solution, assuming one exists?

[Anonymous No.4384024]

>>4383596
Solve for the polynomial of one degree higher than highest-ordered term of the recursion.

If f(n+1) = f(n) + n, the highest order is 1, so the closed form is of order 2

If f(n+1) = f(n) + n^2, the highest order is 2, so the closed form is of order 3.

Etc...

[Anonymous No.4384031]

So uhh, how bout prime number finding?
Or does "find the first n prime numbers and then find the next one" count as a non-recursive function?

[Anonymous No.4384044]

>>4384031
nevermind, I guess finding the nth prime number isn't really a truly recursive process anyway. Factorial though maybe?