How can a recursive formula be turned into an explicit formula?
There is a entire field dedicated to this problem: it goes by the name “generating functions”. Depending on your particular formula, this method will be easier or harder to apply. For example, if you have a linear, constant coefficients formula, then your problem is always solvable and will lead to a rational (quotient of two polynomials) generating function, that can then be inverted to give a closed formula. In this respect, this method is formally similar to Laplace or Fourier Transform methods (or, more closely, the z-transform, if you ever heard of it; if you don’t, that’s not essential). On the other hand, if your recurrence is not of the above type, then the application will be harder: you’ll have to use more complicated generating functions (for a large number of full nonlinear problems there are no known solutions). I’ll leave you with a few references: the Wiki is not very good, but may give a few pointers; the relevant sections of the OCW’s MIT course is a very good and conc
