Solving recurrence relation? Consider the recurrence relation $a_1=8,a_n=6n^2+2n+a_{n−1}$. Let  $a_{99}=K\times10^4$ .The value of $K$ is______ .

My attempt :
$a_n=6n^2+2n+a_{n−1}$
$=6n^2+2n+6(n−1)^2+2(n−1)+a_{n−2}$
$=6n^2+2n+6(n−1)^2+2(n−1)+6(n−2)^2+2(n−2)+......+a_1$
$=6n^2+2n+6(n−1)^2+2(n−1)+6(n−2)^2+2(n−2)+......+6.1^2+2.1$
$=6(n^2+(n−1)^2+...+2^2+1^2)+2(n+(n−1)+...+2+1)$
$=6×n(n+1)(2n+1)/6+2×n(n+1)/2$
$=n(n+1)(2n+1+1)$
$=2n^3+2n^2+2n^2+2n$
$=2n(n^2+n+n+1)$
$=2n(n^2+2n+1)$
$a_n=2n(n+1)^2$
for $n=99, a_{99}=2×99×(99+1)^2=198×10^4$

I'm looking for short trick or alternative way, can you explain please?
 A: Let $b_{n}=\frac{a_{n}}{2}$. 
Then $b_{n}=3n^2+n+b_{n-1}$. 
For any $n$th degree polynomial $Q(x)$, one can find a $n+1$th degree polynomial $P(x)$ such that $P(x)-P(x-1)=Q(x)$. 
Then, use this to note that $b_{n}-n(n+1)^2=b_{n-1}-(n-1)n^2$, since $n(n+1)^2-(n-1)n^2=3n^2+n$. 
Thus $b_{n}-n(n+1)^2$ is a constant. But since $b_{1}=0$, then this implies that $a_{n}=2n(n+1)^2$. 
Thus $a_{99}=198 \times 10^4$. 
A: The idea is to find a closed form solution. We start with
$$
a_1 = 8 \\
6n^2+2n = a_n -a_{n−1}
$$
which is an inhomogenous linear recurrence relation and look for the previous
sequence elements:
$$
6(n-1)^2 + 2(n-1) = 6n^2 -12 n + 6 + 2n - 2 = 6 n^2 - 10n + 4 
= a_{n-1} - a_{n-2}
$$
Substraction gives
$$
12n - 4 = a_n - 2 a_{n-1} + a_{n-2}
$$
where the inhomogenous polynomial has been reduced by one degree and the order has increased from $1$ to $2$. Repeating the procedure leads to
$$
12(n-1) - 4 = 12 n - 16 = a_{n-1} - 2 a_{n-2} + a_{n-3} \Rightarrow \\ 
12 = a_n - 3 a_{n-1} + 3 a_{n-2} - a_{n-3} \Rightarrow \\
12 = a_{n-1} - 3 a_{n-2} + 3 a_{n-3} - a_{n-4} \Rightarrow \\
a_n = 4 a_{n-1} - 6 a_{n-2} + 4 a_{n-3} - a_{n-4}
$$
which now is a homogenous recurrence relation of order $4$.
The characteristic polynomial is
$$
p(t) = t^4 - 4 t^3 + 6 t^2 - 4 t + 1 = (t-1)^4
$$
so the solution is
$$
a_n = k_1 1^n + k_2 n 1^n + k_3 n^2 1^n + k_4 n^3 1^n = k_1 + k_2 n + k_3 n^2 + k_4 n^3 
$$
The $k_i$ follow from the $a_i$ values:
\begin{align}
a_1 &= 8 \\
a_2 &= 6 \cdot 2^2 + 2 \cdot 2 + 8 = 36 \\
a_3 &= 6 \cdot 3^2 + 2 \cdot 3 + 36 = 96 \\
a_4 &= 6 \cdot 4^2 + 2 \cdot 4 + 96 = 200
\end{align}
We get a linear system
$$
\begin{pmatrix}
1 & 1 & 1 & 1 \\
1 & 2 & 4 & 8 \\
1 & 3 & 9 & 27 \\
1 & 4 & 16 & 64
\end{pmatrix}
\begin{pmatrix}
k_1 \\
k_2 \\
k_3 \\
k_4
\end{pmatrix}
=
\begin{pmatrix}
8 \\
36 \\
96 \\
200
\end{pmatrix}
$$
with the solution
$$
k =
\begin{pmatrix}
0 \\
2 \\
4 \\
2
\end{pmatrix}
$$
so we have
$$
a_n = 2 n + 4 n^2 + 2 n^3 = 2n (1 + 2n + n^2) = 2 n (n + 1)^2
$$
Then
$$
a_{99} = 2 \cdot 99 \cdot 100^2 = 198 \cdot 10^4
$$
and $K = 198$.
A: As $a_n-a_{n-1}$ is a quadratic polynomial, $a_n$ must be a cubic polynomial. By integration, close to $\dfrac63n^3=2n^3$.
Then the factor $10^4$ is very likely to be $(99+1)^2$, and we can gamble on the expression $2n(n+1)^2$. It works for $n=1$ ($a_1=8$) and $n=2$ ($a_2=36$). This is convincing enough.
$$2n=198.$$

By better knowledge of Faulhaber's formula, (the first coefficient is always $\dfrac1d$, the second coefficient is always $\dfrac12$), we can predict that the cubic term is exactly $\dfrac63n^3=2n^3$ and the quadratic term is exactly $\dfrac62n^2+n^2=4n^2$. This fits with $2n(n+1)^2$.
A: $$a_n-a_{n-1}=6n^2+2n$$
Now sum both sides from $n=2$ to $x$. You end up with a telescoping sum on the left hand side which will drastically make things easier and help you find the closed form, assuming you know some summation formulas.
$$\sum_{n=2}^x (a_n-a_{n-1})= \sum_{n=2}^x (6n^2+2n)$$
$$a_x-a_1=\sum_{n=2}^x (6n^2+2n)$$
$$a_x=a_1+\sum_{n=2}^x (6n^2+2n)$$
$$a_x=a_1-8+\sum_{n=1}^x (6n^2+2n)$$
$$a_x=\sum_{n=1}^x (6n^2+2n)$$
Therefore $a_{99}$ would be:
$$a_{99}=\sum_{n=1}^{99} (6n^2+2n)$$
Where now you can apply summation formulas.
