Solve the following recurrence relations

Question

Solve the following recurrence relations:

$\qquad$a) $a_n = a_{n-1} + 3(n-1), a_0 = 1$

$\qquad$b) $a_n = a_{n-1} + 3n^2, a_0 = 10$

I know that $a_n = a_{n-1} + f(n)$ = $a_0 + \sum_{i=0}^n f(i)$. So how do I evaluate the sum of the additional terms involving the function of $n$?

Answer 1

$\sum\limits_{i=1}^{n}3(i-1)=\sum\limits_{i=0}^{n-1}3i=3\sum\limits_{i=0}^{n-1}i=3\frac{n(n-1)}{2}$

$\sum\limits_{i=1}^n3i^2=3\sum\limits_{i=1}^{n}i^2=3\frac{n(2n+1)(n+1)}{6}$

Answer 2

Note that $(n+1)^k-n^k$ is a polynomial in $n$ of degree $k-1$, i.e., one degree less. This suggests that $a_n$ might be a quadratic in $n$ for a) and a cubic for b). Make the ansatz $a_n= A+Bn+Cb^2$ (or $a_n=A+Bn+Cn^2+Dn^3$) and see if you can make $a_n-a_{n-1}=3(n-1)$ or $=3n^2$.

Answer 3

make for b) the ansatz $$a_n=An^3+Bn^2+Cn+D$$ with real numbers $$A,B,C,D$$