Second-Order, Linear Inhomogeneous Recurrence Relation With Constant Coefficients

Question

How does one solve the general recurrence relation $$s_n=\alpha s_{n-1}+\beta s_{n-2}+\zeta(n)?$$

Answer 1

Here is a foolproof approach. The difference equation is second order so we'll need two initial values, say $s_0,s_1$.

Let $S(x):=\sum_{n=0}^\infty s_nx^n$. Similarly, $Z(x):=\sum_{n=0}^\infty \zeta(n)$. Then

$$s_{n}x^n=\alpha s_{n-1}x^n+\beta s_{n-2}x^n+\zeta(n)x^n$$

summing this from $n=2$ to $\infty$ gives:

$$S(x)-s_1x+s_0=\alpha x(S(x)-s_0)+\beta x^2 S(x)+Z(x)-\zeta(1)x-\zeta(0).$$

Solving this for $S(x)$ gives:

$$S(x)=\frac{Z(x)-\zeta(1)x-\zeta(0)-(1+\alpha x)s_0+s_1x}{1-\alpha x-\beta x^2}$$

meaning that

$$s_n(x)=\left.\frac{d^n}{dx^n}S(x)\right|_{x=0},$$

or just reading off the $x^n$ coefficient. If $\zeta(n)=n$ or $n^2$, then $Z(x)=x/(1-x)^2$ or $Z(x)=-x(x-1)/(1-x)^3$. I'll leave the pleasure of figuring out the exact coefficients to you. You can save yourself some time by using partial fractions on the expression for $S(x)$ and then use the known nice generating functions like $1/(1-x)=1+x+x^2$, or Newton's formulas for $1/(1-x)^s$, etc.

Answer 2

The command of Maple rsolve({s(n) = alpha*s(n-1)+beta*s(n-2)+Zeta(n)}, s) produces a long answer which can be seen in the worksheet exported as a PDF file. For example, in the concrete case $$ rsolve({s(1) = 1, s(2) = 1, s(n) = s(n-1)+s(n-2)+Zeta(n)}, s)$$ the answer is $$ -1/5\,\sqrt {5} \left( -1/2\,\sqrt {5}+1/2 \right) ^{n}+1/5\,\sqrt {5} \left( 1/2\,\sqrt {5}+1/2 \right) ^{n}+ $$ $$\sum_{n0=3}^n 2/5\,\sqrt {5} \left( -2\, \left( \sqrt {5}+1 \right) ^{-1} \right) ^{ n-{\it n0}} \left( \sqrt {5}+1 \right) ^{-1}\zeta(n0)- $$ $$\sum_{n0=3}^n 2/5\,\sqrt {5} \left( -2\, \left( -\sqrt {5}+1 \right) ^{-1} \right) ^ {n-{\it n0}} \left( -\sqrt {5}+1 \right) ^{-1}\zeta(n0) $$

Answer 3

A particular solution of the difference equation $$s_n=\alpha s_{n-1}+\beta s_{n-2}+a+bn+cn^2\qquad(n\geq2)$$ can be found with the "Ansatz" $$s_n=A+Bn+Cn^2,\tag{1}$$ and solving for $A$, $B$, $C$ by comparing coefficients. If $\alpha+\beta\ne1$, i.e.,if the associated homogeneous problem $$s_n=\alpha s_{n-1}+\beta s_{n-2}\tag{2}$$ has no constant solutions, there will be exactly one admissible triple $(A,B,C)$.

Then solve the homogeneous problem $(2)$ in the usual way and add its general solution $n\mapsto C_1\lambda^n +C_2 \mu^n$ to the particular solution $(1)$ constructed before. Finally fix $C_1$ and $C_2$ using the initial conditions.

The cases $\alpha+\beta=1$ and $\lambda=\mu$ require special consideration, but lead to similar results.