6
$\begingroup$

Let $a,b,c$ be non-zero constants. How can we find an explicit formula for a sequence obeying a recurrence relation of the following type? $$ x_n = a x_{n-1} + b (n-1) x_{n-2} +c , \text{ for } n \geq 2$$ The initial conditions $x_0$ and $x_1$ are given, and can be assumed to be non-zero.

$\endgroup$
  • 1
    $\begingroup$ A good first approach for many such problems is to try ansätze similar to what would solve a corresponding differential equation. $y' = (ax+b)y$ has a solution of the form $y = c_1^{(x^2)}c_2^x \equiv e^{(c_1x^2+c_2x)}$. Adding the constant $+c$ gives a complicated diffeq with erfc in there. Since it's a second-order recurrence it's probably also good to try a sum of two such terms. $\endgroup$ – Alex Meiburg Jul 28 '17 at 7:43
  • 1
    $\begingroup$ I found that oeis.org/A000932 and oeis.org/A059480 have the explicit solutions (for initial conditions $(0,1)$ and $(1,0)$ which is sufficient to construct any) for $a=b=1$ in terms of Hypergeometric functions. The fact that the characteristic polynomial there "isn't anything in particular" leads to me to believe that it could be generalized to arbitrary $a$ and $b$. $\endgroup$ – Alex Meiburg Jul 28 '17 at 17:58
7
$\begingroup$

An approach providing formulas, although not always very explicit ones, starts by converting the whole sequence $(x_n)$ into a generating function. The first idea that comes to mind to apply this technique might be to consider the simple generating function $$\sum_{n=0}^\infty x_nt^n$$ but, due to the $(n-1)x_{n-2}$ term in the recursion, one can predict that $x_n$ grows roughly as a factorial hence the radius of convergence of this series is $0$.


The second idea that comes to mind might be to consider the exponential generating function $$X(t)=\sum_{n=0}^\infty x_n\frac{t^n}{n!}$$ Then the recursion yields $$X(t)=x_0+x_1t+\sum_{n=0}^\infty(a x_{n+1} + b (n+1) x_n +c)\frac{t^{n+2}}{(n+2)!}$$ that is, $$X(t)=x_0+x_1t+ a(X_1(t)-x_0t)+bX_2(t)+c\sum_{n=2}^\infty\frac{t^n}{n!}$$ with $$X_1(t)=\sum_{n=0}^\infty x_n\frac{t^{n+1}}{(n+1)!}\qquad X_2(t)=\sum_{n=0}^\infty x_n(n+1)\frac{t^{n+2}}{(n+2)!}$$ One sees that $$ \sum_{n=2}^\infty\frac{t^n}{n!}=e^t-1-t$$ and that $$ X_2(t)=\sum_{n=0}^\infty x_n(n+2-1)\frac{t^{n+2}}{(n+2)!}=tX_1(t)-Y(t)$$ with

$$Y(t)=\sum_{n=0}^\infty x_n\frac{t^{n+2}}{(n+2)!} $$

These definitions readily imply that $$Y'(t)=X_1(t)\qquad X'_1(t)=X(t)$$ hence all these steps indicate that one should have considered from the start the exponential generating function $Y(t)$ rather than $X(t)$ since, translating everything in terms of $Y$, one gets

$$Y''(t)-(a+bt)Y'(t)+bY(t)=Z(t)$$ with $$Z(t)=x_0+x_1t-ax_0t+c(e^t-1-t)$$


The rest is standard. In the general case, the solutions of the homogenous equation $$U''(t)-(a+bt)U'(t)+bU(t)=0$$ span a two dimensional vector space. Pick a basis $\{U(t),V(t)\}$ of this vector space, then every solution $Y(t)$ of the complete differential equation is $$Y(t)=A(t)U(t)+B(t)V(t)$$ where $(A(t),B(t))$ solves the system $$A'(t)U(t)+B'(t)V(t)=0\qquad A'(t)U'(t)+B'(t)V'(t)=Z(t)$$ Thus, $$A'(t)=V(t)Z(t)W(t)\qquad B'(t)=-U(t)Z(t)W(t)$$ where $$W(t)=\frac1{U'(t)V(t)-V'(t)U(t)}$$ which yields $$Y(t)=U(t)\left(A_0+\int_0^tV(s)Z(s)W(s)ds\right)-V(t)\left(B_0+\int_0^tU(s)Z(s)W(s)ds\right)$$ where the constants $(A_0,B_0)$ are determined by the initial conditions $Y(0)=Y'(0)=0$, which read $$U(0)A_0-V(0)B_0=0=U'(0)A_0-V'(0)B_0$$ hence, since $(U,V)$ is linearly independent, $A_0=B_0=0$, and, finally,

$$Y(t)=\int_0^t(U(t)V(s)-V(t)U(s))W(s)\,Z(s)\,ds$$

From there, depending on the exact form of the function $U$, $V$ and $W$, one can more or less easily deduce $Y(t)$, hence finally, every $x_n$ in terms of $(x_0,x_1)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.