I need some help with the following non-homogenous recurrence relation.

$$a_n-2a_{n-1}+a_{n-2}=n+1$$ $$a_0=0, a_1=1$$

When I solve the associated homogenous equation I use the auxiliary equation $x^2-2x+1=0$ and obtain the root $x=1$. Hence, I obtain the equation $a_n=(A+nB)1^n$. Using the initial conditions I get $a_n=n$.

When it comes to the particular solution I get stuck, however. I thought the solution should be on the form $cn+d$ due to $n+1$. The following calculations show how I then get stuck:

$$a_n-2a_{n-1}+a_{n-2}=n+1$$ $$cn+d-2(c(n-1)+d)+c(n-2)+d=n+1$$ $$cn+d-2(cn-c+d)+cn-2c+d=n+1$$ $$cn+d-2cn+2c-2d+cn-2c+d=n+1$$ $$0=n+1$$

So obviously I am wrong about the form of the particular solution.

  • $\begingroup$ You can't use inhomogeneous initial condition for homogeneous problem. $\endgroup$
    – Kaster
    Nov 28 '13 at 17:34
  • $\begingroup$ Can you expand on that? $\endgroup$
    – tychicus
    Nov 28 '13 at 17:47
  • $\begingroup$ You said that to find $a_n$ you use initial conditions, but you can't do that since initial conditions are from different inhomogeneous problem. $\endgroup$
    – Kaster
    Nov 28 '13 at 18:31
  • $\begingroup$ If it doesn't work out, try a larger degree polynomial. $\endgroup$
    – vonbrand
    Aug 21 '15 at 0:18

Use difference solution. Define $\Delta a_k=a_k-a_{k-1}$: $$ \Delta a_k- \Delta a_{k-1}=k+1\\ \Delta a_{k-1} - \Delta a_{k-2}=k\\ \ldots\\ \Delta a_2-\Delta a_1 = k-(k-3) $$ Now sum LSH and RHS. On LHS you'll get $\Delta a_k - \Delta a_1$, on RHS $k(k-1)+1 - S_{k-3}$, where $S_{k-3} = 1+2+\ldots +k-3$. Clearly $\Delta a_1=1$ so you get $$ \Delta a_{k}= 2 +k(k-1)-S_{k-3} $$ Now sum over $k$ over both sides. On LHS you'll get $a_n$ and on RHS some expression $O(n^3)$ after some algebra. Note $\frac{2k(k-1)}{2}-\frac{(k-3)(k-2)}{2}=\frac{k^2-3k-6}{2}.$

  • $\begingroup$ You are welcome $\endgroup$
    – Alex
    Dec 5 '13 at 16:40

The form of the equation allows us to solve it by using only first-order difference equations (see Remark 1). Arrange the equation as $$\begin{cases}[a_{n}-a_{n-1}]-[a_{n-1}-a_{n-2}]=n+1,{\quad}n=3,4,\cdots\\ a_{1}=1,\ a_{0}=0,\end{cases}$$ which is a first-order difference equation in $b_{n}:=[a_{n-1}-a_{n-2}]$ for $n=2,3,\cdots$. So, we have $$\begin{cases}b_{n+1}-b_{n}=n+1,{\quad}n=2,3,\cdots\\ b_{2}=1,\end{cases}$$ which implies $$\begin{aligned}b_{n}=&1\prod_{k=2}^{n-1}1+\sum_{k=2}^{n-1}(k+1)\prod_{\ell=k+1}^{n-1}1\\ =&1+\sum_{k=2}^{n-1}(k+1)\\ =&\sum_{{\color{blue}k=1}}^{n-1}k+(n-2)\\ =&\frac{1}{2}(n^{2}+n-4),\end{aligned}$$ where we have applied Remark 2(i). Next, we set $c_{n}:=a_{n-2}$ for $n=2,3,\cdots$, then $c_{n+1}-c_{n}=a_{n-1}-a_{n-2}=b_{n}$, i.e., $$\begin{cases}c_{n+1}-c_{n}=\frac{1}{2}(n^{2}+n-4),{\quad}n=2,3,\cdots\\ c_{2}=0\end{cases}$$ whose solution is $$\begin{aligned}c_{n}=&0\prod_{k=2}^{n-1}1+\frac{1}{2}\sum_{k=2}^{n-1}(k^{2}+k-4)\prod_{\ell=k+1}^{n-1}1\\ =&\frac{1}{2}\sum_{k=2}^{n-1}(k^{2}+k-4)\\ =&\frac{1}{2}\sum_{{\color{blue}k=1}}^{n-1}k^{2}+\frac{1}{2}\sum_{{\color{blue}k=1}}^{n-1}k-2(n-2)-{\color{blue}1}\\ =&\frac{1}{2}\frac{1}{6}(n-1)n(2n-1)+\frac{1}{2}\frac{1}{2}(n-1)n-2(n-2)-1\\ =&\frac{1}{6}(n^{3}-13n+18),\end{aligned}$$ where we have applied Remark 2(ii). As $a_{n}=c_{n+2}$, we get $$a_{n}=\frac{1}{6}(n^{3}+6n^{2}-n),{\quad}n=2,3,\cdots.\tag*{$\blacksquare$}$$

Remark 1. The first-order difference equation $x_{n+1}-p_{n}x_{n}=q_{n}$ has the solution $\displaystyle x_{n}=x_{m}\prod_{k=m}^{n-1}q_{k}+\sum_{k=m}^{n-1}q_{k}\prod_{\ell=k+1}^{n-1}p_{\ell}$ with the convention that the empty product is unity.

Remark 2. The following identities hold.

(i) $\displaystyle\sum_{k=1}^{m}k=\frac{1}{2}m(m+1)$.

(ii) $\displaystyle\sum_{k=1}^{m}k^{2}=\frac{1}{6}m(m+1)(2m+1)$.


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.