In a certain series, the $n$th term, $T_n=4T_{n-1} + n – 1$. If $T_1$ = 4, then find the value of $T_{200}$.
I tried the following:
$T_n-T_{n-1}=3T_{n-1} + n – 1$
$T_{n-1}-T_{n-2}=3T_{n-2} + n – 2$
$T_{n-2}-T_{n-3}=3T_{n-3} + n – 3$
Then I proceeded to calculate the difference of the first $2$ and the last $2$ to get:
$$T_n-3T_{n-1}+3T_{n-2}-T_{n-3}=3(T_{n-1} -T_{n-3})$$
Well $\dots$ basically I didn't reach anywhere (neither LHS nor RHS is in friendly form). Then I also tried taking $n^{th}$ order differences and then I got a GP at $3^{rd}$ order difference but still didn't know what to do from there (I'm only familiar with APs of $n^{th}$ order difference).
How to solve this problem? Please help.
Answer (and its format):
$$\frac {10(4^{200})-601}9$$
Edit:
Kindly suggest such that even if the question is tweaked a bit, I may be able to solve that too. For example:
$$T_n=3T_{n-1} + n – 1\text { and } T_1 = 3 \text { then } T_{100}=?$$
Best Answer
The idea is to transform the original sequence $\{T_n\}$ to a geometric sequence by absorbing the term $n - 1$ into the transformed sequence. To this end, we are trying to rewrite the original recurrence relation as \begin{equation*} T_n + an + b = 4(T_{n - 1} + a(n - 1) + b), \end{equation*} where $a$ and $b$ are to be determined by \begin{align*} \begin{cases} 4an - an = n \\[1em] 4b - 4a - b = -1 \end{cases}. \end{align*}
Therefore, $a = 1/3, b = (4a - 1)/3 = 1/9$. Hence \begin{align*} T_n + \frac{1}{3}n + \frac{1}{9} = \left(T_1 + \frac{1}{3} + \frac{1}{9}\right)4^{n - 1}. \end{align*}
$T_{200}$ then follows easily.