# Generic step by step aproach to convert any recursive formula to explicit.

• February 22nd 2010, 11:02 AM
Soubhik
Generic step by step aproach to convert any recursive formula to explicit.
Hello everyone,
I am very new to the forum.
Here is my question.

Can a generic step by step approach be created to
convert any recursive formula to explicit formula?
• February 22nd 2010, 11:16 AM
MoeBlee
What is the context of the question? In what context do you mean 'formula'? Formulas of certain kinds of languages or formulas in the broad sense of a finite string of members of an alpahabet? What do you mean by 'recursive formula' and 'explicit formula'? Does this have to do with recursive operations on formulas (such as variable substitution) or something else?
• February 22nd 2010, 11:20 AM
Soubhik
By formula I mean for example Fibonacci reccursive formula has an explicit representation too...like that. Did I make it clear?
• February 22nd 2010, 11:43 AM
MoeBlee
So, as I take it, you mean as to number theoretic functions, and you're asking whether there is an algorithm to transform the conjunction of the equations in the recursive "definition" of a number theoretic function into actual ("non-circular") definitional form.

Hmm, good question. It seems to me (this should be double-checked) that the ordinary proofs of the "definition by recursion" theorems are constructive in the sense that they prove not only existence but also display an "explicit" ("non-circular") definition (for example, the union of a set of approximating functions). So, I would guess that one could show an algorithm that utilizes the proof to display an explicit definition. But I'd like to hear from someone who can be more definite on the question.
• February 22nd 2010, 11:51 AM
icemanfan
The formula for the summation $\sum_{n=1}^{\infty} n^pr^{n-1}$, which is defined for all positive integers p and real numbers r such that -1 < r < 1, can be determined by a recursion of p, but there is no explicit formula in terms of p for all p.
• February 22nd 2010, 01:41 PM
Soubhik
OK, I understand that all recursive formula do not have an explicit expression, but then for those which should have a valid explicit formula, is there any generic methodical approach to get to that.
I know generating functions is one method, but there must be other methods too. Some must be easier in other methods to derive.
How to choose the correct method. Can there be a thumb rule?