# Solve recursion relation

Let $E$ be a real number. Consider the following recurrence relation: $$a_{n+2} (n+3)(n+2) + a_{n+1} + E a_n = 0$$ subject to $a_0 = 1$ and $a_1 = -1/2$. By using the method of generating functions I have shown -- and checked numerically-- that the solution to that relation reads: $$a_n = \frac{(2 \sqrt{-E})^n}{(-\frac{1}{(2 \sqrt{-E})})!}\sum\limits_{n_1=0}^n \frac{ 1}{n_1! (n-n_1)!} \frac{(-\frac{1}{(2 \sqrt{-E})}+n-n_1)!}{(1+n-n_1)!} (\frac{-1}{2})^{n_1}$$

Now the question is can I solve the recurrence relation in some other way rather than resorting to the method of generating functions? Another question would be what happens if the term $a_{n+1}$ is replaced by say $a_{n-m+1}$ where $m$ is some positive integer.

I will sketch one approach to tackle solve recursion relations of this kind. The solution may not be complete but at least it will be visible why certain recursions adopt closed form solutions and others don't. Our recursion can be written as: $$a_{n+2} = f(n) a_{n+1} + g(n) a_n$$ where $$\left(f(n),g(n)\right) = \left(-\frac{1}{(n+2)(n+3)}, -\frac{E}{(n+2)(n+3)}\right) \tag{I}$$ Let us now iterate our relation back in time. In the first $i_1$ steps we are choosing the first term on the right hand side. Then in the $(i_1+1)$st step we are choosing the second term. After that in the $i_2-i_1$ consecutive steps we again choose the first term and after that in the $i_2+2$th step we choose the second term. We repeat the whole procedure $p$ times. After all this we again choose the first term $n-i_p- 2 p +1$ times. Having done all this we went down in time $[i_1 + (i_2-i_1)+ \cdots + (i_p-i_{p-1}) + (n-i_p-2 p+1)]\cdot 1 + p \cdot 2= n+1$ steps. Therefore the time argument of the last $a$ on the rhs is $n+2-(n+1) = 1$. We have: $$a_{n+2} = \left(\prod\limits_{q=0}^{p-1} \left( \prod\limits_{\xi=n-i_{q+1}-2 q+1}^{n-i_q-2 q} f(\xi)\right) \cdot g(n - i_{q+1} - 2 q )\right) \cdot \left(\prod\limits_{\xi=0}^{n-i_p- 2 p} f(\xi) \right) \cdot a_1 \tag{II}$$ where the rhs is summed ofver all possible sequences $0 \le i_1 \le i_2 \le \cdots \le i_p \le n - 2 p$.
Alternatively we could also have terms where the product on the right hand side ends up with a $g$ and not an $f$ as above. This happens when $n-2 p = i_{p+1}$ and $0 \le i_1 \le i_2 \le \cdots \le i_p \le n - 2 p - 1$. Then we have:
$$a_{n+2} = \left(\prod\limits_{q=0}^{p} \left( \prod\limits_{\xi=n-i_{q+1}-2 q+1}^{n-i_q-2 q} f(\xi)\right) \cdot g(n - i_{q+1} - 2 q )\right) \cdot a_0 \tag{III}$$ Now , using (I) the we see that the products on the rhs in (II) and (III) are very similar to $1/((n+2)!)^2$ except that certain pairs of consecutive integers are missing in the denominator. In fact we are having: $$a_{n+2} = \sum\limits_{\xi=0}^1 \sum\limits_{p=0}^{\lfloor (n-\xi)/2 \rfloor} \frac{(-1)^{n-2p+1} (-E)^p}{(n+3) \cdot (\prod\limits_{j=3}^{n+2} j)^2 \cdot 2} \cdot \left(\sum\limits_{0 \le i_1 \le \cdots \le i_p \le n- 2 p - \xi} \cdot \prod\limits_{q=0}^{p-1} \left(n - i_{q+1} - 2 q +2\right)_{(2)} \right)\cdot a_{1-\xi}$$ Note that $a_{n+2}$ is a polynomial of order $\lfloor n/2 \rfloor$ in $-E$ with coefficients that in principle can be expressed as a function of $n$ in a closed form. Numerical calculations of the recurrence relation confirm my findings.