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?
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?
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.
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?