Solve the recurrence relation $a_n=3a_{n-1}+n^2-3$, with $a_0=1$.

Question

My solutions: the homogeneous portion is $a_n=c3^n$, and the inhomogeneous portion is $a^*_n=-1/2n^2-3/4n+9/8$.

This results in a final recurrence relation of $$a_n=-\frac{1}{8}3^n-\frac{1}{2}n^2-\frac{3}{4}n+\frac{9}{8}.$$

I am just wondering if someone could check my work to make sure I have the procedure correct.

You can check it yourself, can't you? Does $3a_n + (n+1)^2-3 = a_{n+1}$? — Thomas Andrews, Nov 23 '14 at 21:25
If you don't feel like doing the (relatively simple) algebra as per Thomas's comment, you can also check the first few cases. The recurrence relation given initially yields the sequence $1,1,4,18,\ldots$. Does this match your final result? — Semiclassical, Nov 23 '14 at 22:08

score 2 · Answer 1 · answered Nov 23 '14 at 21:59

Well you've made a mistake,I'm not sure where is your mistake anyway here's is a different solution $$a_n=3a_{n-1}+n^2-3\\a_{n-1}=3a_{n-2}+n^2-2n-2\\a_n-a_{n-1}=3a_{n-1}+n^2-3-3a_{n-2}-n^2+2n+2\\a_n=4a_{n-1}-3a_{n-2}+2n-1\\a_{n-1}=4a_{n-2}-3a_{n-3}+2n-3\\a_n-a_{n-1}=4a_{n-1}-3a_{n-2}+2n-1-4a_{n-2}+3a_{n-3}-2n+3\\a_n=5a_{n-1}-7a_{n-2}+3a_{n-3}+2\\a_n=5a_{n-1}-7a_{n-2}+3a_{n-3}+2\\a_{n-1}=5a_{n-2}-7a_{n-3}+3a_{n-4}+2\\a_n-a_{n-1}=5a_{n-1}-7a_{n-2}+3a_{n-3}+2-5a_{n-2}+7a_{n-3}-3a_{n-4}-2\\a_n=6a_{n-1}-12a_{n-2}+10a_{n-3}-3a_{n-4}\\t^4-6t+12t-10t+3=0\\t_{1,2,3}=1\\t_4=3\\a_n=C_1+nC_2+n^2C_3+C_43^n\\1=C_1+C_4\\a_1=1,a_2=4,a_3=18\\a_1=C_1+C_2+C_3+3C_4\\a_2=C_1+2C_2+4C_3+9C_4\\a_3=C_1+3C_2+9C_3+27C_4\\C_1=0,C_2=-\frac{3}{2},C_3=-\frac{1}{2},C_4=1\\a_n=-\frac{3}{2}n-\frac{1}{2}n^2+3^n$$

Frank Vel · Answer 2 · 2014-11-23T22:25:09.867

Given the homogenous solution: $a_n^{(h)} = c_03^n$ and the particular solution: $a_n^{(p)} = c_1n^2+c_2n+c_3$, and we have: $a_n = a_n^{(h)}+a_n^{(p)}$. First we find the coefficients to the particular solution: $$ \begin{align} &a_n^{(p)} \:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:- 3a_{n-1}^{(p)} &&= n^2+0n-3\\ \iff &c_1n^2+c_2n+c_3 -3\left(c_1(n-1)^2+c_2(n-1)+c_3\right) &&= n^2+0n-3\\ \iff &c_1n^2+c_2n+c_3 -3(c_1n^2-2c_1n+c_1+c_2n-c_2+c_3) &&= n^2+0n-3\\ \iff &\color{red}{c_1}n^2\color{green}{+c_2}n\color{blue}{+c_3}\color{red}{-3c_1}n^2\color{green}{+6c_1}n\color{blue}{-3c_1}\color{green}{-3c_2}n\color{blue}{+3c_2}\color{blue}{-3c_3} &&= n^2+0n-3\\ \iff &\color{red}{(-2c_1)}n^2+\color{green}{(6c_1-2c_2)}n+\color{blue}{(3c_1-3c_2+4c_3)} &&= \color{red}{1}n^2\color{green}{+0}n\color{blue}{-3}\\ \end{align} $$

This gives three equations: $$ \begin{matrix} \color{red}{-2c_1}&&&= \color{red}{1}\\ \color{green}{6c_1}&\color{green}{-2c_2}&&= \color{green}{0}\\ \color{blue}{3c_1}&\color{blue}{-3c_2}&\color{blue}{+4c_3}&= \color{blue}{3} \end{matrix} $$

Solving this system yields: $$ \begin{matrix} c_1&&&=-\frac{1}{2}\\ &c_2&&= -\frac{3}{2}\\ &&c_3&= 0 \end{matrix} $$

So we have $a_n^{(p)} = - \frac{1}{2}n^2-\frac{3}{2}n+0$

This means a solution is given by $a_n = c_03^n - \frac{1}{2}n^2-\frac{3}{2}n$, and given the initial condition $a_0 = 1$, we can solve this for $c_0$:

$a_0 = 1 = c_03^0 - \frac{1}{2}0^2 - \frac{3}{2}0 \iff c_0 = 1$

This means $a_n = 3^n - \frac{1}{2}n^2-\frac{3}{2}n$

score 1 · Answer 3 · 2014-11-23T22:07:59.613

1

$$ a_n = 3a_{n-1} + n^2 - 3 = 3^ka_{n-k} + n^2 + 3(n - 1)^2 + \ldots + 3^{k - 1}(n - k + 1)^2 - (3 + \ldots + 3^k) $$

$$ a_n = 3^ka_{n - k} + \sum_{m=0}^{k-1}3^m(n - m)^2 - \sum_{m = 0}^{k-1}3^{m+1}$$

Setting $k = n$, we have $$a_n = 3^n + \sum_{m=0}^{n-1}3^m(n - m)^2 - \sum_{m = 0}^{n-1}3^{m+1} = \frac{1}{2}(-n^2 - 3n + 3^{n+1} - 3) - \frac{3}{2}(3^n - 1) + 3^n.$$ The last was calculated using numerical software. Simplifying we have, $$\frac{1}{2}(-n^2 - 3n + 3^{n+1} - 3) - \frac{3}{2}(3^n - 1) + 3^n = 3^n - \frac{1}{2}n^2 - \frac{3}{2}n.$$

edited Nov 23 '14 at 22:07

answered Nov 23 '14 at 21:33

1

@atl This took me many edits to get right. Sorry about that. It should be fine now. Your result is incorrect. Sub in $n = 1$, you should get $1$. – Nov 23 '14 at 22:11

score 0 · Answer 4 · answered Aug 06 '19 at 19:33

Use generating functions. Define $A(z) = \sum_{n \ge 0} a_n z^n$, multiply the shifted recurrence by $ẓ^n$ and sum over $n \ge 0$, recognize some sums:

$\begin{align*} \sum_{n \ge 0} a_{n + 1} z^n &= 3 \sum_{n \ge 0} a_n z^n + \sum_{n \ge 0} (n + 1)^2 - 3 \sum_{n \ge 0} z^n \\ \frac{A(z) -a_0}{z} &= 3 A(z) + \sum_{n \ge 0} n^2 z^n + 2 \sum_ {n \ge 0} n z^n - 2 \sum_{n \ge 0} z^n \end{align*}$

You know the geometric sum:

$\begin{align*} \sum_{n \ge 0} z^n &= \frac{1}{1 - z} \frac{d}{d z} \sum_{n \ge 0} z^n &= \sum_{n \ge 0} n z^{n - 1} \\ z \frac{d}{d z} \sum_{n \ge 0} z^n &= \sum_{n \ge 0} n z^n \\ &= \frac{z}{(1 - z)^2} \sum_{n \ge 0} n^2 z^n &= \frac{z + z^2}{(1 - z)^3} \end{align*}$

Plug this in above, solve for $A(z)$, and write as partial fractions:

$\begin{align*} A(z) &= \frac{1 - z - z^2 - z^3}{(1 - z) (1 + z) (1 - 3 z) (1 + z + z^2)} \\ &= \frac{7 + 2 z}{39 (1 + z + z^2)} + \frac{21}{52 (1 - 3 z)} + \frac{1}{4 (1 + z)} + \frac{1}{6 (1 - z)} \\ &= \frac{(7 + 2 z) (1 - z)}{39 (1 - z^3)} + \frac{21}{52 (1 - 3 z)} + \frac{1}{4 (1 + z)} + \frac{1}{6 (1 - z)} \\ &= \frac{7 - 5 z - 2 z^2}{39 (1 - z^3)} + \frac{21}{52 (1 - 3 z)} + \frac{1}{4 (1 + z)} + \frac{1}{6 (1 - z)} \end{align*}$

You want the coefficient of $z^n$ from this. Everything in sight is just a geometric series:

$\begin{align*} [z^n] \left( \frac{7 - 5 z - 2 z^2}{39 (1 - z^3)} + \frac{21}{52 (1 - 3 z)} + \frac{1}{4 (1 + z)} + \frac{1}{6 (1 - z)} \right) &= (7 [z^n] - 5 [z^{n - 1}] - 2 [z^{n - 2}]) \frac{1}{1 - z^3)} + \frac{21}{52} \cdot 3^n + \frac{1}{4} \cdot (-1)^n + \frac{1}{6} \\ &= [n = 0] \cdot 7 + \frac{21}{52} \cdot 3^n + \frac{1}{4} \cdot (-1)^n + \frac{1}{6} \end{align*}$

Here $[n = 0]$ uses Iverson's convention: $1$ if the condition is true, $0$ if false. If $n = 0$, the only relevant term is the first one, if $n > 0$ the other two terms cancel with it.

Solve the recurrence relation $a_n=3a_{n-1}+n^2-3$, with $a_0=1$.

4 Answers4