Finding General Expression from recursion I am trying to find a general expression from a recursion.
Here it goes:
$(x+i)P_i = (i+1)P_{i+1} + \frac{x}{2} P_{i-1}$
$i$ goes from $0$ to $S$.
How can I calculate a generic $P_i$ in terms of $P_0$? So, if $P_i = C \times P_0$, what is $P_0$?
Is it possible to solve this in Mathematica? What is the function I'm looking for?
You can assume $P_0 = 1$.
Thanks.
[UPDATE]
I am  not quite sure if this would help. I started from $P_0$ and have the following equations:
$P_{1}=P_{0}x$ 
$P_{2}=P_{0}(\frac{1}{2!})(x^2+\frac{x}{2})$
$P_{3}=P_{0}(\frac{1}{3!})(x^3+\frac{3x^2}{2}+x)$
$P_{4}=P_{0}(\frac{1}{4!})(x^4+3x^3+\frac{19x^2}{4}+3x)$
$P_{5}=P_{0}(\frac{1}{5!})(x^5+5x^4+\frac{55x^3}{4}+20x^2+12x)$
I tried to find polynomials that will represent above, but I could not find one.
These are basically balance equations for a two dimensional markov chain. I solved it numerically, but I want to have a analytical solution as well.
 A: I think the answer is no, it's not possible to solve in Mathematica and probably no closed form (in terms of standard functions) exists.
Using the initial condition $P_{-1}=0$ so that $P_1 = x P_0$ as in your edit, we can try to solve the recurrence relation using Mathematica
soln = RSolve[P[i] == ((-1 + i + x) P[-1 + i])/i - (x P[-2 + i])/(2 i) 
           && P[-1] == 0 && P[0] == P0, P, i][[1]]

{P -> DifferenceRoot[Function[{y, n}, 
  {x y[n] - 2 (1 + n + x) y[1 + n] + (4 + 2 n) y[2 + n] == 0, 
   y[-1] == 0, y[0] == P0}]]}

It returns an DifferenceRoot object, which is just the original relation wrapped up in something that knows how to do various calculations.
For example, as you noted in your edit, the result takes the form
$$ \begin{align}
P_i = \frac{x}{i!}P_0 R_i(x)\,, \quad 
R_i(x) = \sum_{j=0}^{i-1} a_{i,j} x^j\,,\\
\text{ where }
a_{i,i-1}=1 \text{ and } a_{i,j}=0 \text{ for } i\geq j
\end{align}$$
We can produce the $R_i(x)$, up to some factors of 2, with Mathematica
Table[(i! 2^Floor[i/2])/(P0 x) P[i], {i, 1, 5}] /. soln // Expand

{1, 1 + 2 x, 2 + 3 x + 2 x^2, 12 + 19 x + 12 x^2 + 4 x^3, 
 48 + 80 x + 55 x^2 + 20 x^3 + 4 x^4}

If we extract the coefficients of the polynomials $R_i(x)$ using
Reverse[CoefficientList[#, x]] & /@ %

then we can feed them for various $i$ into 
The On-Line Encyclopedia of Integer Sequences
to see if they match any known pattern.
Unfortunately, they don't. So the chances are, there are no simple variation of a common polynomial sequence that reproduce the $R_i(x)$.
Note that the higher order polynomial have more complicated coefficients.
Which you can look at by running
Map[Times @@ (Superscript @@@ FactorInteger[#]) &, %, {2}]
on the previous output. Some large primes arrive pretty quickly.
Interestingly though, up to the factors of 2, the sequence $R_i(1)$ corresponds to A005650 and $R_i(2)$ matches A000522. However, $R_i(3)$ and higher do not seem to match anything in OEIS. That said, maybe these clues could be of some help in finding a closed form.
Finally, we can find a recurrence relation for the $a_{i,j}$ by plugging the general form of the solution into the original relation. It yields
$$ a_{i+1,j} = i a_{i,j} + a_{i,j-1} - \frac{i}{2}a_{i-1,j-1}\,,
\text{ where } a_{i,j}=0 \text{ for } j<0 \text{ or } j\geq i\ .
$$
See also: https://mathoverflow.net/questions/32937/how-to-find-guess-a-polynomial-sequence
Which reminds me, maybe a generating function approach would get somewhere.
Have you read generatingfunctionology and A=B?
