Find the general term for sequence ($a_n$) which equates to the recursive equation $a_{n+3}=5a_{n+2}-7a_{n+1}+3a_n+16+24n^2+36*3^n$

Question

Find the general term for sequence ($a_n$) which equates to the recursive equation $a_{n+3}=5a_{n+2}-7a_{n+1}+3a_n+16+24n^2+36*3^n$ with $a_0=3$, $a_1=5$ and $a_2=27$

I tried doing this question by working out how much $a_k$ is for some $a_k$.

$a_3=5*27-7*5+3*3+16+24*9+36*3^3=1383$

As soon as I saw this huge result, I realized that I was going down the wrong path. I then thought that maybe it is a function like $f(x)=Ax^2+Bx+C$ and I tried substituting some values (I know that this is not correct mathematical thought, but I was hoping for some inspiration on what to do, inspiration which unfortunately did not come). All of these routes I attempted did not work out for me. This is the first time I am seeing a question of this type, could you please explain to me how to solve it, how you intuitively thought of each step and also what general thought pattern I should follow in the future when confronted with a question like this?

Answer 1

Here's one approach. Let $A(z)=\sum_{n\ge 0} a_n z^n$ be the ordinary generating function for $a_n$. Then the recurrence relation implies that \begin{align} &A(z) - a_0 - a_1 z - a_2 z^2 \\ &= \sum_{n\ge 0}\left(5a_{n+2}-7a_{n+1}+3a_n+16+24n^2+36\cdot3^n\right)z^{n+3} \\ &= 5z\sum_{n\ge 0} a_{n+2} z^{n+2} - 7z^2 \sum_{n\ge 0} a_{n+1} z^{n+1} + 3z^3\sum_{n\ge 0} a_n z^n + 16\sum_{n\ge 0} z^{n+3} + 24\sum_{n\ge 0}n^2 z^{n+3} + 36z^3\sum_{n\ge 0}(3z)^n \\ &= 5z (A(z)-a_0-a_1 z)- 7z^2 \left(A(z)-a_0\right) + 3z^3A(z) + \frac{16z^3}{1-z} + \frac{24z^4(1+z)}{(1-z)^3} + \frac{36z^3}{1-3z}, \end{align} so \begin{align} A(z) &= \frac{a_0 + a_1 z + a_2 z^2 + 5z (-a_0-a_1 z)+ 7a_0z^2 + \frac{16z^3}{1-z} + \frac{24z^4(1+z)}{(1-z)^3} + \frac{36z^3}{1-3z}}{1-5z + 7z^2 - 3z^3}\\ &= \frac{3 + 5 z + 27 z^2 + 5z (-3-5 z)+ 21z^2 + \frac{16z^3}{1-z} + \frac{24z^4(1+z)}{(1-z)^3} + \frac{36z^3}{1-3z}}{1-5z + 7z^2 - 3z^3}\\ &= \frac{3 - 28 z + 119 z^2 - 236 z^3 + 221 z^4 - 88 z^5 - 87 z^6}{(1 - 3 z)^2(1 - z)^5}\\ &= -\frac{2}{1-3 z} + \frac{3}{(1-3 z)^2} - \frac{9}{1-z} + \frac{55}{(1-z)^2} - \frac{92}{(1-z)^3} + \frac{72}{(1-z)^4} - \frac{24}{(1-z)^5} \\ &= \sum_{n\ge 0}\left(-2\cdot 3^n + 3\binom{n+1}{1}3^n -9 + 55\binom{n+1}{1} - 92\binom{n+2}{2} + 72\binom{n+3}{3}-24\binom{n+4}{4}\right)z^n, \end{align} which immediately implies that \begin{align} a_n &= -2\cdot 3^n + 3\binom{n+1}{1}3^n -9 + 55\binom{n+1}{1} - 92\binom{n+2}{2} + 72\binom{n+3}{3}-24\binom{n+4}{4} \\ &= 2 - n - 9 n^2 + 2 n^3 - n^4 + 3^n + 3^{n + 1} n. \end{align}

Answer 2

You can put it in WA e.g.

the recurrence

See the Recurrence equation solution section there.
Then just use the values for $a_0, a_1, a_2$ to find the constants $c_i$.

Probably there's good amount of theory behind that and that's what WA implemented.

And here is the solution with the constants found.

complete solution

All in all, I don't think this is a problem well-suited for humans, it's hard to guess the solution or find any pattern by just observing. Maybe there's some trick (or theoretical apparatus) to simplify things and solve it in the general case... but unless you know it, you have no chance.

At the end of the day the formula is:

$a(n) = -n (n ((n - 2) n + 9) - 3^{n + 1} + 1) + 3^n + 2$