Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|cite|improve this question
You can't use inhomogeneous initial condition for homogeneous problem. – Kaster Nov 28 '13 at 17:34
Can you expand on that? – tychicus Nov 28 '13 at 17:47
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. – Kaster Nov 28 '13 at 18:31
If it doesn't work out, try a larger degree polynomial. – vonbrand Aug 21 at 0:18

2 Answers 2

up vote 0 down vote accepted

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}.$

share|cite|improve this answer
Thank you for the help. – tychicus Dec 5 '13 at 16:35
You are welcome – 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)$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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