2

Is there any general method to solve for $r(n)$ with the recurrence relation $$\frac1{r(n)}=P(n)+r(n-1)$$ where $P(n)$ is a polynomial of $n$?

My current direction is to convert the problem into a differential equation problem, however traditional methods fail, e.g. ‘reverse engineering’ of solving Airy’s differential equation by recurrence relation.

If such general method does not exist, solutions for $r(n)$ when $P(n)=n, n^2,2n+1...$(simple polynomials) are also welcomed.

Any suggestions?

Thanks in advance.

Szeto
  • 11,159

1 Answers1

1

(Too long for a comment.) The terms in $\,n\,$ can be eliminated using finite differences, which in the end gives a non-linear recursion of order $\,1+\deg P\,$ with constant coefficients. However, I am not aware of ways to solve such recurrences in the general case.

For example, even in the simple linear case $\,P(n)=an+b\,$:

$$ \begin{cases} \begin{align} an+b &= \frac{1}{r_n}-r_{n-1} \\ a(n-1)+b &= \frac{1}{r_{n-1}}-r_{n-2} \end{align} \end{cases} $$

Eliminating $\,n\,$ between the two gives the (not obviously tractable) second-order recurrence:

$$ a = \frac{1}{r_n}-r_{n-1}-\left(\frac{1}{r_{n-1}}-r_{n-2}\right) \\ \iff\quad r_n = \frac{1}{a +r_{n-1}+\cfrac{1}{r_{n-1}}-r_{n-2}} = \frac{r_{n-1}}{r_{n-1}^2+ a r_{n-1}- r_{n-1}r_{n-2}+1} $$

dxiv
  • 76,497