How do I find a closed form for this recurrence? $$a_0=0$$
$$a_n=a_{n-1} + 2n^2-n$$
What I have so far, but I don't think it's right:
$$x^n = x^{n-1} + 2x^2-x^{n-1}=2x+x^{n-2}-1$$
$$0=-x^{n-1}+x^{n-2}+2x-1$$
 A: hint: $a_n = (a_n-a_{n-1}) + (a_{n-1}-a_{n-2}) + \cdots + (a_1-a_0) + a_0 = \displaystyle \sum_{k=1}^n (2k^2-k)$. Can you find this sum?
A: In this answer, it is shown that
$$
\sum_{j=k}^n\binom{j}{k}=\binom{n+1}{k+1}\tag{1}
$$
Since $a_n-a_{n-1}=2n^2-n$, we have the telescoping series
$$
\begin{align}
a_n
&=a_0+\sum_{k=1}^n\left(a_k-a_{k-1}\right)\tag{2}\\
&=a_0+\sum_{k=1}^n\left(2k^2-k\right)\tag{3}\\
&=\sum_{k=1}^n\left[4\binom{k}{2}+\binom{k}{1}\right]\tag{4}\\[2pt]
&=4\binom{n+1}{3}+\binom{n+1}{2}\tag{5}\\[5pt]
&=\frac{(4n-1)(n+1)n}6\tag{6}
\end{align}
$$
Explanation:
$(2)$: Telescoping Series
$(3)$: apply the recurrence
$(4)$: write the summand using binomial coefficients
$(5)$: apply $(1)$
$(6)$: expand and factor
A: The homogenous part of the relation would be from $a_n=a_{n-1}$ with characteristic polynomial $(x-1)=0$, implying that the homogeneous solution would be of the form $\alpha\cdot 1^n$.
The non-homogenous part is a second degree polynomial (which is a special case of something of the form $1^n$).  Ordinarily we would want to use an arbitrary second degree polynomial $\beta_2 n^2+\beta_1 n + \beta_0$ for the particular solution, however since the general solution is of the form $1^n$ and the particular solution is technically also of the form $\beta_2 n^21^n+\beta_1 n 1^n + \beta_0 1^n$, we must multiply by an additional $n$ to make this linearly independent from the other solution.
The solution will then be of the form:
$$a_n=\alpha \cdot 1^n + \beta_2 n^3 1^n + \beta_1 n^2 1^n + \beta_0 n 1^n = \alpha + \beta_0 n + \beta_1 n^2+\beta_2 n^3$$
I will leave solving for the coefficients of $\alpha, \beta_0, \beta_1, \beta_2$ to you to do, but this can be done using the recurrence relation and the initial conditions.
