# Closed form of an inhomogeneous non-constant recurrence relation

I try to find a closed form for the $f_k$’s (at least for $f_1$) satisfying the following recurrence relation for any fixed $n>0$:

$f_0 = 0$, $f_n = 0$, and $f_k = \frac{n}{2k}(f_{k-1} + f_{k+1} + 2)$ for $k=1\ldots n-1$.

Since this is equivalent to $f_{k+1} = \frac{2k}{n} f_k – f_{k-1} – 2$, it appears to be a 2nd order linear inhomogeneous recurrence relation with a non-constant coefficient. Do you have an idea how to solve this?

#### Solutions Collecting From Web of "Closed form of an inhomogeneous non-constant recurrence relation"

This is not going to be a solution to the whole problem but as we will see a substantial step in the right direction. Consider a simpler recurrence relation first:

f_{k+1} = \frac{2 k}{n} f_k – f_{k-1}

for $k \in {\mathbb Z}$. Multiplying both sides by $x^k$ and summing from $k=-\infty,\cdots,\infty$ we get:
\begin{eqnarray}
\frac{F(x)}{x} &=& \frac{2}{n} x \frac{d F(x)}{d x} – x F(x)\\
\Rightarrow&&\\
\frac{ d F(x)}{d x} – \frac{n}{2} \left(\frac{1+x^2}{x^2}\right) F(x) &=& 0
\end{eqnarray}
This is a homogenous first order ODE whose generic solution reads:

F(x) = C \cdot e^{\frac{n}{2} \cdot (x – \frac{1}{x})} = \sum\limits_{k=-\infty}^\infty x^k \cdot C \cdot J_k(n)

In this case we have found a particular solution to the recurrence relations in question. Now, if we delve in properties of Bessel functions we will find out that the generic solution actually reads:

f_k = C_1 \cdot J_k(n) + C_2 \cdot Y_k(n)

where $Y_k(n)$ is the Neumann function. Now we are already very close to solving the original problem. The general solution to the original recurrence is a sum of the general solution to our recurrence and a special solution to the original recurrence. We can find the later using the Green’s function method for example. We will finish this later.

Now we are going to answer the question above using back-iteration . Again, we are only solving the simpler problem, i.e. :

y_{k+1} = f_k \cdot y_k +g_k \cdot y_{k-1}

subject to $y_1 = {\bf y}_1$ and $y_0=0$. Here of course $f_k = 2k/n$ and $g_k = -1$. In this case, as shown in Closed form solutions to a recursion relation, the solution reads:

y_{k+1} = {\bf y_1} \cdot \left( \prod\limits_{j=1}^k f_j\right) \cdot \sum\limits_{p=1}^{\lfloor \frac{k}{2} \rfloor} \sum\limits_{\begin{array}{rrr} 1 \le & i_p & \le k-2 p+1 \\ 2+i_p \le & i_{p-1} & \le k-2 p+3 \\ 2+i_{p-1} \le & i_{p-2} & \le k-2 p+5\\
\vdots & \vdots & \vdots \\ 2+i_3 \le & i_2 & \le k-3 \\ 2+ i_2 \le & i_1 & \le k-1\end{array}} \prod\limits_{q=1}^p \left(\frac{g_{i_q+1}}{f_{i_q+1} f_{i_q}}\right)

The multiple sum on the right hand side will rarely produce neat closed form expressions. However in this particular case it does . This is because after taking subsequent sums, firstly over $i_1$ then over $i_2$ and so on and so forth, and by absorbing the respective terms in the product to the result of the summation we end up with expressions that are similar to those we started with in the first place, i.e. before taking the sum. Indeed it is easy to check, using Mathematica for example, that the result reads:
\begin{eqnarray}
y_{k+1} &=& {\bf y_1} \cdot
k! (\frac {2} {n})^k
\sum\limits_ {p = 0}^{\lfloor \frac {k} {2} \rfloor}
(-\frac {n^2} {4})^p\frac {(k – p) _ {(p)}} {p! \cdot p! \cdot k_ {(p)}}\\
y_{k+1}&=& {\bf y_1} \cdot(\frac {2} {n})^k \sum\limits_ {p = 0}^{\lfloor \frac {k} {2} \rfloor}
\binom{k-p}{p} \cdot \frac{(k-p)!}{p!} \cdot (-\frac {n^2} {4})^p
\end{eqnarray}
By comparing the result above with my previous answer to this problem we get a nice identity for the Bessel functions:

y_{k+1} = {\bf y_1} \frac{J_0(n) Y_{k+1}(n)-Y_0(n) J_{k+1}(n)}{J_0(n) Y_1(n)-J_1(n) Y_0(n)}\cdot