Recurrence relation $a_n = 4a_{n-1} - 3a_{n-2} + 2^n + n + 3$ with $a_{0} = 1$ and $a_{1} = 4$

This is a nonhomogeneous recurrence relation, so there is a homogeneous and a particular solution.

Homogenous:

$$a_n - 4a_{n-1} + 3a_{n-2} = 0$$

$$r^2 - 4r + 3 = 0$$

$$(r - 3)(r - 1)$$

$$a_n^h = \alpha(3^n) + \beta(1^n)$$

This is where my solution stops because I don't know how to solve the particular solution since it would be $$a_n - 4a_{n-1} + 3a_{n-2} = 2^n + n + 3$$ and I'm not sure what form it should be. Would it be $$A_0(r^n) + A_1(n) + A_2$$ where $$A_n$$ is a constant or not?

I've tried solving it with that form and it ended like this:

$$A_0(2^n) + A_1(n) + A_2 - 4(A_0(2^{n-1}) + A_1(n-1) + A_2) + 3(A_0(2^{n-2}) + A_1(n-2) + A_2) = 2^n + n + 3$$

After simplifying and dividing $$2^{n-2}$$:

$$A_0(2^n) - 4A_0(2^{n-1}) + 3A_0(2^{n-2}) - 4 = n + 3 + 2A_1(n) + 2A_2 - 2A_1$$

And that's where I stop since I don't know what to do next.

• Use a_{n-1} to get $a_{n-1}$ Oct 20 '20 at 15:24
• @jjagmath can you explain further? Oct 20 '20 at 15:27
• @Clover, I edited as jjagmath suggested. Please check I didn't change anything by mistake. Oct 20 '20 at 15:29
• Please, you can read the MSE-${\tt MathJax}$ Tutorial. Thanks. Oct 20 '20 at 15:30
• @cosmo5 you accidentally removed the initial values but I added it back again Oct 20 '20 at 15:36

There is no point in including a constant term in the particular solution because constants are part of the solution of the homogeneous equation. Try $$A_0 2^n + A_1 n^2+ A_2 n$$.

This way you will conclude that the general solution is given by $$a_n = \alpha 3^n + \beta - 2^{n+2} -\frac 14 n^2 -\frac 52 n.$$

Now you just need to compute $$\alpha, \beta$$ so that the initial conditions are satisfied.

• Should the characteristic root then be $r^2 - 4r + 3 = 3$? And why $A_{1}n^2 + A_{2}n$ instead of $A_{1}n + A_{2}$ for the particular solution? Oct 20 '20 at 15:46
• @Clover The characteristic polynomial is always relative to the homogeneous equation. The inicial choice for the particular solution would indeed be $A_0 2^n + A_1 n + A_0$ but, as you have seen, when you plug it into the equation you get an impossible system for computing the constants. When this happens, a common fix is to multiply by $n$. Oct 20 '20 at 16:29

So we have $$a_{\,n} - 4a_{\,n - 1} + 3a_{\,n - 2} = 2^{\,n} + n + 3 = q(n)$$ and the solutions to the homogeneous equations are $$3^{\,n} ,\;1$$

The homogeneous equation has constant coefficients and $$q(n) = 2^{\,n} + \left( {n + 3} \right)$$ is the sum of two terms of the form $$c^{\,n} \cdot {\rm polynomial}(n)$$

Then the theory says that in this case we can look for particular solutions of the form $$2^{\,n} \left( {An + B} \right),\quad C\left( {n + 3} \right)^{\,2} + D\left( {n + 3} \right) + E$$ (method of Undetermined Coefficients).

Since the constant term $$E$$ is already a homogeneous solution we can omit it and with simple passages we get $$A = 0,\;B = - 4,\;C = - 1/4,\;D = - 1$$

So the solution is $$a_{\,n} = \alpha \,3^{\,n} + \beta - 4 \cdot 2^{\,n} - {{\left( {n + 3} \right)^{\,2} } \over 4} - \left( {n + 3} \right)$$

Here's an alternative 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 &= \sum_{n\ge 2}\left(4a_{n-1} - 3a_{n-2} + 2^n + n + 3\right)z^n \\ &= 4z \sum_{n\ge 2} a_{n-1} z^{n-1} - 3z^2 \sum_{n\ge 2} a_{n-2} z^{n-2} + \sum_{n\ge 2} (2z)^n + z \sum_{n\ge 2} n z^{n-1} + 3\sum_{n\ge 2}z^n \\ &= 4z (A(z)-a_0)- 3z^2 A(z) + \frac{(2z)^2}{1-2z} + z\left(\frac{1}{(1-z)^2}-1\right) + \frac{3z^2}{1-z}, \end{align} so \begin{align} A(z) &= \frac{a_0 + a_1 z -4 a_0 z + \frac{4z^2}{1-2z} + \frac{z}{(1-z)^2}-z + \frac{3z^2}{1-z}}{1-4z+3z^2}\\ &= \frac{1 - z + \frac{4z^2}{1-2z} + \frac{z}{(1-z)^2} + \frac{3z^2}{1-z}}{1-4z+3z^2}\\ &= \frac{1 - 4 z + 14 z^2 - 24 z^3 + 12 z^4}{(1 - 2 z) (1 - 3 z)(1 - z)^3 } \\ &= -\frac{4}{1-2 z} + \frac{39/8}{1-3 z} + \frac{19/8}{1-z} - \frac{7/4}{(1-z)^2} - \frac{1/2}{(1-z)^3} \\ &= \sum_{n\ge 0}\left(-4\cdot 2^n + \frac{39}{8}\cdot3^n + \frac{19}{8} - \frac{7}{4}\binom{n+1}{1} - \frac{1}{2}\binom{n+2}{2}\right)z^n, \end{align} which immediately implies that \begin{align} a_n &= -4\cdot 2^n + \frac{39}{8}\cdot3^n + \frac{19}{8} - \frac{7}{4}\binom{n+1}{1} - \frac{1}{2}\binom{n+2}{2} \\ &= \frac{- 2^{n + 5} + 13\cdot 3^{n + 1} -2 n^2 - 20 n + 1}{8}. \end{align}