# How to Solve Advanced Recurrence Relations

For some research I’m doing, I had to solve recurrences of the form: $$a(n)=n \cdot a(n-1)-(n-3) \cdot a(n-2)$$.

WolframAlpha gave the solution:

$$a(n) = 4c_2 \Gamma (n-1) ( \Gamma (n-1) F(1,n-2;n,n;1) -(c_1-4c_2(e-3))(n-2) )$$ Where F is the regularized generalized hypergeometric function.

I was taught a little bit about creating closed forms from recurrence relations, but have no clue to derive something such as this. It looks really similar to examples where you use exponential generating functions, but I can’t see exactly how it would work in this case. So my question is, how would a human get this solution, and where could I go to learn this and similar advanced techniques.

• At least this is a linear recurrence, even though the coefficients depend on $n$. I believe the theory here is well developed – Yuriy S Jul 4 '19 at 17:32
• Yes I figured as much. However, I have been unable to find the techniques at this level, which I’d like to know both so that I don’t have to rely on wolfram alpha, and so that I may possibly make deeper generalizations about my problem, concerning different recurrence relations. – Zachary Hunter Jul 4 '19 at 17:39
• I agree, but don't know any sources. Only dealt with such recurrences on a case to case basis. Here's a similar example math.stackexchange.com/q/2994975/269624. I only proved it, wouldn't know how to find the solution – Yuriy S Jul 4 '19 at 17:45

Here are two references which might be useful when learning recurrence relations.

Hint: Sometimes we are lucky and can find a solution also by elementary means. Assuming initial values $$a_0, a_1$$ are given, we derive from \begin{align*} a_n=na_{n-1}-(n-3)a_{n-2}\qquad n\geq 2 \end{align*} successively \begin{align*} \color{blue}{1}a_2&=2a_1+a_0\\ a_3&=\color{blue}{3}a_2\\ a_4&=4a_3-a_2=\color{blue}{11}a_2\\ a_5&=5a_4-2a_3=\color{blue}{49}a_2\\ a_6&=6a_5-3a_4=\color{blue}{261}a_2\\ &\cdots\\ \end{align*}

Looking for the values $$1,3,11,49,261$$ in OEIS we find the sequence A001339 with representation \begin{align*} a_{n+2}=\sum_{k=0}^n\binom{n}{k}(k+1)!\qquad\qquad n\geq 0 \end{align*}

• Again, the power of OEIS prevails :) – Yuriy S Jul 6 '19 at 20:53
• yes, thank you. I actually had just come up with this repertoire concept myself, and it has proven extremely useful. now with the additional techniques, things have become very manageable indeed. – Zachary Hunter Jul 6 '19 at 21:04
• @ZacharyHunter: You're welcome. Good to see the answer is useful. :-) – Markus Scheuer Jul 6 '19 at 21:05

Hint.

Considering $$S(x) = \sum_k a_k x^k$$ we have

$$S(x) -x\frac{d}{dx}\left(x S(x)\right)+x^4\frac{d}{dx}\left(\frac{S(x)}{x}\right) = 0$$

and solving for $$S(x)$$ we obtain

$$S(x) = C_0 (1-x)e^{-\frac 1x}$$

• I didn't consider a first order ODE, how did you figure out the exact form? What would be the method for a general recurrence such as: $a_{n+2}=(p n+q) a_{n+1}+(r n+s) a_n$ – Yuriy S Jul 5 '19 at 13:38
• this looks very promising and simple, thank you! – Zachary Hunter Jul 5 '19 at 13:58

Some general results that might be interesting.

As the OP said, generating functions do seem like a good method for this kind of recurrences.

Let's consider a more general homogeneous second order linear recurrence with coefficients linear in $$n$$:

$$\left(A_2 n+B_2 \right) a_{n+2}+\left(A_1 n+B_1 \right) a_{n+1}+\left(A_0 n+B_0 \right) a_n =0$$

Now let's introduce some function defined by its Frobenius series:

$$f(x)=\sum_{n=0}^\infty b_n x^{n+s}$$

Which (we claim) obeys a second order ODE in the form:

$$(\alpha_2 x^2+\beta_2 x+\gamma_2) f''(x)+(\beta_1 x+\gamma_1) f'(x)+\gamma_0 f(x)=0$$

We have:

$$f'(x)=\sum_{n=-1}^\infty (n+1+s) b_{n+1} x^{n+s}$$

$$x f'(x)=\sum_{n=0}^\infty (n+s) b_n x^{n+s}$$

$$f''(x)=\sum_{n=-2}^\infty (n+1+s)(n+2+s) b_{n+2} x^{n+s}$$

$$x f''(x)=\sum_{n=-1}^\infty (n+s)(n+1+s) b_{n+1} x^{n+s}$$

$$x^2 f''(x)=\sum_{n=0}^\infty (n-1+s)(n+s) b_n x^{n+s}$$

Substituting the series, we obtain the following recurrence relation:

$$\alpha_2 (n-1+s)(n+s) b_n+\beta_2 (n+s)(n+1+s) b_{n+1} +$$ $$+ \gamma_2 (n+1+s)(n+2+s) b_{n+2} +\beta_1 (n+s) b_n+\gamma_1 (n+1+s) b_{n+1}+$$ $$+\gamma_0 b_n=0$$

Or:

$$\gamma_2 (n+s+1)(n+s+2) b_{n+2}+$$ $$+\left( \beta_2 n^2+(\beta_2 (2s+1)+\gamma_1)n+(\beta_2 s+\gamma_1) (s+1) \right) b_{n+1}+$$ $$+\left( \alpha_2 n^2+(\beta_1+(2s-1) \alpha_2)n+\alpha_2 s (s-1)+\beta_1 s+\gamma_0 \right) b_n=0$$

To get rid of quadratic terms, we need to be able to factor out one of the brackets before the first term, let's pick $$(n+s+1)$$. Which means that the other two coefficients should have the form:

$$q(n+s+1)(n+p)=q(n^2+(p+s+1) n+p(s+1))$$

For the second term we have:

$$q=\beta_2 \\ p=s+\frac{\gamma_1}{\beta_2}$$

For the third term:

$$q=\alpha_2 \\ p=s+\frac{\beta_1}{\alpha_2}-2=\frac{\alpha_2 s (s-1)+\beta_1 s+\gamma_0}{\alpha_2 (s+1)}$$

We have obtained an equation which allows us to get rid of one parameter, for example, $$\gamma_0$$.

Now our recurrence relation is reduced to:

$$\gamma_2 (n+s+2) b_{n+2}+ \left(\beta_2n+\beta_2s+\gamma_1 \right) b_{n+1} +\left(\alpha_2 n+\alpha_2(s-2)+\beta_1 \right) b_n=0$$

We now have a linear second order recurrence with six parameters left, which (at least in principle) can be related to the original parameters $$A_2,B_2,A_1,\dots$$, and we can even set $$a_n=b_n$$.

In the example from Integral representation for the solution of a difference equation we have:

$$\gamma_2=1 \\ s=0 \\ \beta_2=\gamma_1=-2 \\ \alpha_2=1 \\ \beta_1=3 \\ \gamma_0=1$$

Which makes the generating function obey the following ODE:

$$(x-1)^2 f''(x)+(3 x-2) f'(x)+f(x)=0 \\ f(0)=1, \qquad f'(0)=0$$

Wolfram Alpha gives the exact solution:

$$f(x)=\frac{1}{1-x} \exp \left(- \frac{x}{1-x} \right)$$

From the explicit recurrence form given in the linked question, we also have:

$$f(x)= e \int_0^\infty e^{-(1-x) t} J_0 (2 \sqrt{t} ) dt$$

But this is correct and confirmed numerically.

So, the method allows us to obtain an ODE for a certain class of second order linear recurrence relations with variable coefficients linear in $$n$$.

Note: for the case in the OP the method doesn't seem to work as stated, some modifications need to be made.

Update: Another example.

Using hypergeometric equation, we can derive the following result. The sequence with explicit form:

$$a_n = \frac{(\alpha)_n}{(\beta)_n} {_2 F_1} (n+1, n+\alpha; n+\beta; p )$$

obeys the recurrence relation:

$$p(p-1) (n+2) a_{n+2}+ [(2p-1) n +(\alpha+2) p -\beta] a_{n+1} + (n+ \alpha) a_n=0$$ $$a_0 = {_2 F_1} (1, \alpha; \beta; p )$$ $$a_1 = \frac{\alpha}{ \beta} {_2 F_1} (2, 1+\alpha; 1+\beta; p )$$

$$p \neq 0, p \neq 1, \qquad \beta \notin \mathbb{Z}$$.

For general initial conditions the solution also exists, but will be more complicated.