Solving a nonhomogenous recurrence relation

Question

$$a_n=4a_{n-1}+(n\cdot 3^n+2)^2$$

What is the very first step that should be done?

Answer 1

In general for nonhomogenous recurrence relations, the solution involves two broad steps:

• Solve the homogenous relation first (sort of like how you might do with ODEs)
• Using the nonhomogenous term as a basis, make an educated guess as to what the solution might be: choose something that has basically the same form, but up to a scalar multiple. A rule of thumb for the occasions in which that guess doesn't work is just to multiply it by $n$ and try again.

From there, your solution should be the sum of these, and you use any initial conditions available to solve for the various unknown constants that will pop up.

---

Here, the homogenous relation is $a_n = 4a_{n-1}$. This is pretty easy to solve using the characteristic polynomial method.

As for the nonhomogenous relation, I would make the guess $a_n = B(n\cdot 3^n+2)^2$ where $B$ is some unknown constant. Then I would substitute that into the original recurrence relation, both for $a_n$ and $a_{n-1}$ (changing the $n$'s to $(n-1)$'s in the latter), and try to determine the constant $B$.

If that doesn't work, I would try that guess, but times $n$, $n^2$, and so on as necessary.

Based on the form of the nonhomogenous term, you might also consider an alternative approach: expanding the squared term to $3^{2n}n^2 + 4 n\cdot 3^n + 4$.

If you choose this method, you have multiple nonhomogenous terms. In such a case, you would consider each one-by-one. For example, you would make a guess for $a_n = 4a_{n-1} + 3^{2n}n^2$, one for $a_n = 4a_{n-1} + 4 n\cdot 3^n$, and so on, using a new guess for each. Once you have solutions you could then add them all up with the solution for the homogenous relation.

Answer 2

Consider taking small steps that make the problem easier, no matter how small.

So first I can get rid of the coeff $4$ by introducing $b_n=4^n a_n$. The original recurrence relation can be rewritten as $$b_n=b_{n-1}+(n\cdot 3^n+2)^2/4^n.$$

Now you can deduce that $b_n=b_1+\sum_{m=2}^n (m3^m+2)^2/4^m$. And the summation is (almost) a trivial matter.

EDIT: now you simply need the technique used in summing geometric progressions. Frst you expand the square and break the terms up. You will need to sun terms of the form $m^kq^m$, where $k=0,1,2$. Multiply the whole sum by $q$, shifting the series by one place, and subtract it from the original series, you will reduce it to a sum where $k$ is one less that the original one. Finally you can reduce all the sum to geometric progressions.

The sum is $\sum_{m=2}^n (m 3^m + 2)^2/4^m = \frac1{375 }4^{-n - 1}(100\times 3^{2 n + 3} n^2 - 80 \times3^{n + 2} (2 \times3^{n + 1} + 25) n + 59009\times 4^n - 8000\times 3^{n + 2}+ 208\times 3^{2 n + 3} - 2000).$ Yes, it's ugly. Since you didn't give $a_1$ you can't know $b_1$, so you can leave it as a parameter. Now substitute it back to $b_n=4^n a_n$ to get the answer to the original problem.