# The particular solution of the recurrence relation

I cannot find out why the particular solution of $a_n=2a_{n-1} +3n$ is $a_{n}=-3n-6$

here is the how I solve the relation

$a_n-2a_{n-1}=3n$ as $\beta (n)= 3n$

using direct guessing

$a_n=B_1 n+ B_2$

$B_1 n+ B_2 - 2 (B_1 n+ B_2) = 3n$

So $B_1 = -3$, $B_2 = 0$

the particular solution is $a_n = -3 n$

and the homo. solution is $a_n = A_1 (-2)^n$

Why it is wrong??

-
In the first line of your attempted solution, the $a_{n-1}$ has morphed into $a_n$. That's guaranteed to get you in trouble. –  Gerry Myerson Dec 19 '12 at 5:21
O that is a Typo, changed. –  Samuel Dec 19 '12 at 5:25
You still have the same problem three lines later: it should be $$B_1n+B_2-2\big(B_1(n-1)+B_2\big)=3n\;.$$ –  Brian M. Scott Dec 19 '12 at 5:25
Yes, you fixed it in the line I pointed to, but you're still using the incorrect version in the calculations that follow. –  Gerry Myerson Dec 19 '12 at 5:26
Thank Brain and Gerry. I know where have gone wrong. –  Samuel Dec 19 '12 at 5:32

Let $A_n=\sum_{0\le r\le m}B_rn^r$

The coefficient of $x^m$ in $A_n-2A_{n-1}$ is $B_m-2B_m=-B_m$

Comparing the coefficients of the highest power $(=1)$ of $n,$

we derive $-B_m=0$ for $m>1$ and $-B_m=3$ if $m=1$

So, $A_n$ reduces to $-3n+B_0$

Consequently, $A_n-2A_{n-1}= -3n+B_0-2\{-3(n-1)+B_0\}=-3n-(B_0+6)$

Comparing the constants, $B_0+6=0\implies B_0=-6$

Alternatively,

$A_n-2A_{n-1}=\sum_{0\le r\le m}B_rn^r-2\sum_{0\le r\le m}B_r(n-1)^r$

$=n^m(B_m-2B_m)+n^{m-1}\{B_{m-1}-2(B_{m-1}+\binom m1 B_m(-1))\}+\cdots$

$=-n^mB_m+n^{m-1}(-B_{m-1}+2mB_m)+\cdots$

Like 1st method, $B_1=-3$ and $B_m=0$ for $m>1$

Putting $m=1,$ and comparing the coefficients of $m-1=0$-th power of $n,$ we get $B_0=2B_1=-6$

-
Since the homogeneous problem has no polynomial solution, the particular solution must be linear, not quadratic. Trying a quadratic is a waste of time. –  Gerry Myerson Dec 20 '12 at 4:13
@GerryMyerson, I've edited the answer. Could you please elaborate "no polynomial solution". Btw, had the coefficients of of $A_n,A_{n-1}$ been same, $A_n$ could be quadratic. –  lab bhattacharjee Dec 20 '12 at 15:22
The homogeneous problem is $a_n=2a_{n-1}$; the general solution thereof is $a_n=C2^n$, which is not a polynomial. Going to the original equation, $a_n-2a_{n-1}=3n$, the right side is linear, and since no linear function can be a solution to the homogeneous equation, there is a linear particular solution. So we can simply write $a_n=B_1n+B_2$, as Samuel did, and then work out the values of $B_1$ and $B_2$. –  Gerry Myerson Dec 20 '12 at 17:22

using direct guessing

$a_n=B_1 n+ B_2$

$B_1 n+ B_2 - 2 (B_1 (n-1)+ B_2) = 3n$

then

$B_1 - 2B_1 = 3$

$2 B_1 - B_2 =0$

The solution will be

$B_1 = -3, B_2=-6$

-

Use generating functions. Define $A(z) = \sum_{n \ge 0} a_n z^n$, write the recurrence without subtractions in indices: $$a_{n + 1} = 2 a_n + 3 n + 3$$ Multiply by $z^n$, sum over $n \ge 0$ and recognize the resulting sums, particularly: \begin{align} \sum_{n \ge 0} z^n &= \frac{1}{1 - z} \\ \sum_{n \ge 0} n z^n &= z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 - z} \\ &= \frac{z}{(1 - z)^2} \end{align} to get: $$\frac{A(z) - a_0}{z} = 2 A(z) + \frac{3}{(1 - z)^2} + \frac{3}{1 - z}$$ As partial fractions this gives: $$A(z) = \frac{a_0 + 6}{1 - 2 z} - \frac{3}{1 - z} - \frac{3}{(1 - z)^2}$$ Using the generalized binomial theorem, in particular: $$\binom{-m}{n} = \binom{m + n - 1}{m - 1} (-1)^n$$ you read off the coefficients: \begin{align} a_n &= (a_0 + 6) 2^n - 3 - 3 \binom{n + 2 - 1}{2 - 1} \\ &= (a_0 + 6) 2^n - 3 - 3 (n + 1) \\ &= (a_0 + 6) 2^n - 3 n - 6 \end{align}

-