Solving recurrence relation?

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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