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

-
Isn't the issue here that you have bidirectional recursion so you have to know the value of both $P_0$ and $P_L$? –  Verbeia Jan 12 '12 at 1:42
@Verbeia: Or just any two $P_i$s... –  Simon Jan 12 '12 at 1:49
@Simon - yes, and I meant $S$ not $L$ anyway. Not sure where I got $L$ from. :-/ –  Verbeia Jan 12 '12 at 1:52
I just updated the question. Thanks for your time. –  sosruko Jan 12 '12 at 2:48
Ok, so there isn't any dependence on $P_{i+1}$ after all. Have a look at the RSolve function. –  Verbeia Jan 12 '12 at 10:30

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\ .$$

Substituting $x=1$ gives oeis.org/A000681 –  Andrew Jan 12 '12 at 16:03