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

Question

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

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.

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

Answer 2

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

Answer 3

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$