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

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?

• $a_n$ is a C-finite sequence as it satisfies an inhomogenous recurrence equation. There is a whole lot of theory on this. You don't need that much of it however, to answer your question. First, from a recurrence you can find a nice closed form in terms of exponential polynomials (and vice versa). Hence you can find a recurrence for the inhomogeneous part of the recurrence ($16+24n^2+36 \cdot 3^n$). Then from the recurrence of the inhomogeneous part and the homogeneous recurrence you can get a recurrence for the $a_n$. – blablablup Oct 23 at 12:13
• Again from here you can use the characteristic polynomial of the recurrence to get a closed form in terms of exponential polynomials which will will give you your answer (you might have to compute some initial values to get the coefficients of the closed form). This was of course only a quick sketch and you might want to read a bit more on C-finite sequences to follow all the steps. – blablablup Oct 23 at 12:15
• @blablablup what is C-finite sequence and what is an ingomogenous recurrence equation? Could you please send a link from where I could learn this theory? – user814992 Oct 23 at 12:16
• en.wikipedia.org/wiki/Constant-recursive_sequence and link.springer.com/chapter/10.1007/978-3-7091-0445-3_4 cover a lot of things in a hopefully quite understandable way – blablablup Oct 23 at 12:19
• Your calculation for $a_3$ should use $n=0$ everywhere, but you used $n=3$ in the last two terms. – RobPratt Oct 23 at 22:26

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}

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

• Yes but how can I thinkg of it on my own without the use of a program? – user814992 Oct 23 at 12:06
• @Michael Maybe there's some trick with telescopic sums e.g. setting $b_n$ to be some linear combination of several $a_i$ and then getting good telescopic sum for $b_n$, finding an easy solution for $b_n$ and then finding $a_n$. I am not sure. – peter.petrov Oct 23 at 12:08
• E.g. here is general theory about homogenous recurrence: math.berkeley.edu/~arash/55/8_2.pdf I am sure there's some theoretical apparatus for your case too (otherwise how does WA solve it?!). But I am not aware of that theory. – peter.petrov Oct 23 at 12:10
• @peter.petrov If you apply a difference operator that nullifies the rhs, you obtain a higher order homogeneous equation. The appropriate guess for particular solution is the part of this higher order equation that is not a solution to the original homogeneous equation. – PierreCarre Oct 23 at 12:16