# Solving a nonhomogeneous recurrence relation?

I was asked to find a first order linear recurrence relation for

$$a_n=3n^2-2n+1$$

Here is what I did \begin{align}\label{1} a_{n-1} &= 3(n-1)^2-2(n-1)+1\\ &=3(n^2-2n+1)-2n+2+1\\ &=\underbrace{3n^2-2n+1}_{a_n}-6n+5\\ &=a_n-6n+5 \end{align} Thus, \begin{align} a_n-a_{n-1}=6n-5\tag{1}\label{2} \end{align} with $$a_0=1$$ is a first order recurrence relation for the given sequence.

But I was unable to retrieve the given sequence from this recurrence relation. Clearly, the recurrence is nonhomogeneous. So, its solution is of the form $$a_n=a_n^h+a_n^p$$ Now, $$a_n^h=c, \mbox{any constant}$$ Since $$f(n)=-6n+5$$o to find a particular solution for the non-homogeneous part, we set $$a_n^p=A_1n+A_0$$, where $$A_1,A_0$$ are constant. Substituting this into (\ref{2}) yield \begin{align*} A_1n+A_0-[A_1(n-1)+A_0]&=6n-5\\ A_1 &= 6n-5 \end{align*} I have tried this again and again but I couldn't tell what is happening? What is wrong with me?

Edited: Let me put it in this way, solve
\begin{align} a_n-a_{n-1}=6n-5,\ a_0=1. \end{align}

• Try $$a_n^p=A_1n^2+A_0n.$$
– bof
Nov 22 '18 at 13:07
• @bof, Why? $f(n)=6n-5$, a polynomial of degree one, shouldn't our particular solution take the same form? Nov 22 '18 at 13:15
• In your $a_n^p=A_1n+A_0$ the $A_0$ term is useless, because $a_n=A_0$ is a solution of the homogeneous recurrence $a_n-a_{n-1}=0$.
– bof
Nov 22 '18 at 21:56
• It's basically the same reason why, in solving the nonhomogeneous DIFFERENTIAL equation $y'-y=(6x+1)e^x$, you would look for a particular solution of the form $y_p=(Ax^2+Bx)e^x$ instead of $y_p=(Ax+B)e^x$.
– bof
Nov 23 '18 at 4:18
• Actually, you could turn your recurrence into a differential equation by considering the exponential generating function $$y(x)=\sum_{n=0}^\infty\frac{a_n}{n!}x^n.$$
– bof
Nov 23 '18 at 4:20

$$\implies$$

$$a_n-a_{n-1}=6n-5\iff6n=?$$ $$a_{n+1}-a_n=6(n+1)-5\iff6n=?$$

Compare the two values of $$6n?$$

• @marya, $$3\{n^2-(n-1)^2\}-2\{n-(n-1)\}=3(2n-1)-2=6n-5$$ is correct Nov 22 '18 at 12:49

Note that if $$a_n = p(n)$$, a polynomial of degree $$m$$, then the $$m + 1$$-th difference of $$a_n$$, satisfies $$\Delta^{m + 1} a_n = 0$$.

In this case we have:

$$\begin{equation*} a_{n + 3} - 3 a_{n + 2} + 3 a_{n + 1} - a_n = 0 \end{equation*}$$

Get initial values from the polynomial.