Form a general formula to find the $n$th term of a recursive function given by $A_n = 3A_{n−1} + 2n$

Question

Here is the recursive formula: $A_n = 3A_{n−1} + 2n$. Given that when $A_0 = 1$, how can I generate a general formula to get $n$th term? Instead of working out term one by one until I get to the $n$th term.

Answer 1

Suppose, more generally, $a_n = ua_{n-1}+vc_n $.

We can get rid of the $u$ by dividing by $u^n$.

The recurrence becomes $\dfrac{a_n}{u^n} = \dfrac{a_{n-1}}{u^{n-1}}+\dfrac{vc_n}{u^n} $. If we let $b_n = \dfrac{a_n}{u^n}$, this is $b_n =b_{n-1}+\dfrac{vc_n}{u^n} $ or $b_n-b_{n-1} =\dfrac{vc_n}{u^n} $.

Summing from $1$ to $m$, this becomes $\sum_{n=1}^m(b_n-b_{n-1}) =\sum_{n=1}^m\dfrac{vc_n}{u^n} $ or $b_m =b_0+v\sum_{n=1}^m\dfrac{c_n}{u^n} $.

Putting in the definition of $b_m$, $\dfrac{a_m}{u^m} =a_0+v\sum_{n=1}^m\dfrac{c_n}{u^n} $ or $a_m =a_0u^m+vu^m\sum_{n=1}^m\dfrac{c_n}{u^n} $.

In your case, with $3 = 2, v=2$ and $c_n=n$, this becomes $a_m =a_03^m+2\cdot 3^m\sum_{n=1}^m\dfrac{n}{3^n} $.

Hint for that last sum: look at $\sum_{n=1}^m nx^n $. The cases $x=1$ and $x \ne 1$ need to be handled separately.