1

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}

marya
  • 745
  • 1
    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? – marya Nov 22 '18 at 13:15
  • 1
    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 04: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 04:20

2 Answers2

1

$\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?$

lab bhattacharjee
  • 274,582
0

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.

vonbrand
  • 27,812