Second-order recurrence relation over another variable

recurrence-relations

Given the recurrence relation

$$ \pi_0 = 0$$
$$ \pi_1 = 1$$
$$ \pi_{i+1} = \frac
{
(2i + 1) m \pi_i –
(i + 1) \pi_{i – 1}
}
{i}
$$

I tried to work through a simplistic tutorial and all I was able to find out is that $ \pi_i $ is a non-trivial polynomial in $m$ of order $i$.

Reading Wikipedia, I doubt that this equation is considered to have constant coefficients, so its solution would fall under Solving general homogeneous linear recurrence relations and I don't understand the methods described there. So how would I go about finding $\pi_i$ ?

Best Answer

First of all, to make it more clear it is linear and homogeneous, rearrange a bit: $$ \pi_{i+1} = \frac {(2i + 1) m} i \pi_i - \frac {i + 1} i \pi_{i - 1} $$

Since the coefficients, $\frac {(2i + 1) m} i$ and $-\frac {i + 1} i$, are not constant in $i$, and since $\pi_{i+1}$ depends on $\pi_{i}$ and $\pi_{i-1}$, you were right in your classification of the problem. This problem class doesn't really have a general method of solution, though, which is all that section of Wikipedia you mentioned was trying to say. It was just saying that some recurrence relations in this class are so common that their solutions are special functions. The examples they gave, though, were much simpler compared to yours, so I doubt there exists a solution to this in terms of a well-known special function.

The coefficients do approach constant values, though, as $i$ approaches infinity, so if you want asymptotic behaviour, you could figure that out pretty easily.

If I had to find $\pi_i$ exactly in terms of an unknown $m$, I would do it numerically, representing $\pi_i$ with a polynomial in $m$, i.e. a variable-length vector, so that $1 + 4m$ would be represented with [1, 4].

import numpy as np

pi = []
pi.append(np.array([0]))
pi.append(np.array([1]))

for i in range(1, 30):
    pi.append(
        np.insert((2*i + 1)/i*pi[i], 0, 0) -
        np.append((i + 1)/i*pi[i - 1], 0)
    )
Related Question