Find all solutions of the recurrence relation $a_n = 5a_{n-1} - 6a_{n-2} + 2^n + 3n$

Question

Question: Find all solutions of the recurrence relation $a_n = 5a_{n-1} - 6a_{n-2} + 2^n + 3n$ (Hint: Look for a particular solution of the form $qn2^n + p_1n + p_2$, where $q, p_1, p_2$ are constants).

Attempt:
The Hint indicates that the solution is of the form $qn2^n + p_1n + p_2$, thus

$$a_n = qn2^n + p_1n + p_2\\\iff a_n = qn2^n + p_1n + p_2= 5(qn2^{n-1} + p_1(n-1) + p_2) - 6(qn2^{n-2} + p_1(n-2) + p_2) + 2^n + 3n$$

I just need if this is a right approach, since I've already wasted hours solving this and I keep getting minute calculation error since my paper is not big enough (I write big apparently). I know for sure that $p_1 = \dfrac{3}{2}$. If my approach above is correct, I'll let this question rest.

Edit:
I think the hint is given due to the fact that $2^n + 3n$ looks nothing like linear homogenous recurrence nor does it even look like a "typical" linear nonhomogenous recurrence relation, since $2^n + 3n$. You might want to comment about that, but I think this book will cover this in future chapters.

Answer 1

Rewrite the LHS as $$ q(n-1)2^n+q2^n+p_1n+p_2$$ and the RHS as $$ q(n-1)2^n+(\frac{3q}{2}+1)2^n+(3-p_1)n+(7p_1-p_2) $$ Then compare the coefficients of $2^n$, $n$ and the constant term to get $$ q=\frac{3q}{2}+1,p_1=3-p_1,p_2=7p_1-p_2 $$ from which you can have $$ q=-2,p_1=\frac{3}{2},p_2=\frac{21}{4}. $$

Answer 2

We can also solve the recurrence using generating functions. We first convert the given recurrence:

$$ a_n = 5a_{n - 1} - 6a_{n - 2} + 2^n + 3n $$

into a power series by adding up all the elements of the recurrence:

$$ \sum_{n = 2}^{\infty} a_n x^n = \sum_{n = 1}^{\infty} 5a_n x^{n + 1} - \sum_{n = 0}^{\infty} 6 a_n x^{n + 2} + \sum_{n = 2}^{\infty} 2^n x^n + \sum_{n = 2}^{\infty} 3nx^n$$

Letting $F(x) = \sum_{n = 0}^{\infty} a_n x^n$ we can rewrite above:

$$ F(x) - a_0 - a_1 x = 5x(F(x) - a_0) - 6x^2F(x) + \sum_{2}^{\infty} 2^n x^n + \sum_{n = 2}^{\infty} 3nx^n $$

The choice of $x$ is arbitrary so we may choose an $x$ such that $\sum_{n = 2}^{\infty} 2^n x^n$ converges, getting:

$$ F(x) - a_0 - a_1 x = 5x(F(x) - a_0) - 6x^2F(x) + \frac{1}{1 - 2x} - 1 - 2x + \sum_{n = 2}^{\infty} 3nx^n $$

and for the last term we reason similarly:

$$ \sum_{n = 2}^{\infty} 3nx^n = \frac{3x}{(1 - x)^2} - 3x = \frac{3x^2(2 - x)}{(1 - x)^2} $$

And so:

$$ F(x) - a_0 - a_1 x = 5x(F(x) - a_0) - 6x^2F(x) + \frac{1}{1 - 2x} - 1 - 2x + \frac{3x^2(2 - x)}{(1 - x)^2} $$

Rearranging for $F(x)$ we get:

$$ (1 - 2x)(1 - 3x) F(x) = a_0 - 1 + (a_1 - 5a_0 - 2)x + \frac{3x^2(2 - x)}{(1 - x)^2} + \frac{1}{1 - 2x}$$

$$ (1 - 2x)(1 - 3x) F(x) = a + bx + \frac{3x^2(2 - x)}{(1 - x)^2} + \frac{1}{1 - 2x}$$

with $a = a_0 - 1$ and $b = a_1 - 5a_0 - 2$. Which means:

$$ F(x) = \frac{a + bx}{(1 - 2x)(1 - 3x)} + \frac{3x^2(2 - x)}{(1 - x)^2(1 - 2x)(1 - 3x)} + \frac{1}{(1 - 2x)^2(1 - 3x)} $$

Applying partial fraction decomposition to the middle term of above we get:

$$ \frac{3x^2(2 - x)}{(1 - x)^2(1 - 2x)(1 - 3x)} = \frac{15}{4} \frac{1}{1 - x} + \frac{3}{2} \frac{1}{(1 - x)^2} - 9\frac{1}{1 - 2x} + \frac{15}{4} \frac{1}{1 - 3x} $$

and to the first term, getting:

$$ \frac{a + bx}{(1 - 2x)(1 - 3x)} = \frac{-2a - b}{1 - 2x} + \frac{3a + b}{1 - 3x} $$

and similarly for the last term:

$$ \frac{1}{(1 - 2x)^2(1 - 3x)} = \frac{-6}{1 - 2x} - \frac{2}{(1 - 2x)^2} + \frac{9}{1 - 3x}$$

And so we have:

$$ F(x) = \frac{-2a - b}{1 - 2x} + \frac{3a + b}{1 - 3x} + \frac{15}{4} \frac{1}{1 - x} + \frac{3}{2} \frac{1}{(1 - x)^2} - 15 \frac{1}{1 - 2x} + \frac{51}{4} \frac{1}{1 - 3x} - \frac{2}{(1 - 2x)^2} $$

Converting above back to power series gives us the solution to the recurrence relation. We work out an example. For simplicity we let $a,b = 1$, which means $a_0 = 2$ and $a_1 = 13$. This gives us:

$$ F(x) = \frac{15}{4} \frac{1}{1 - x} + \frac{3}{2} \frac{1}{(1 - x)^2} - 18 \frac{1}{1 - 2x} + \frac{67}{4} \frac{1}{1 - 3x} - 2 \frac{1}{(1 - 2x)^2} $$

Now we construct the power series from above:

$$ F(x) = \sum_{n = 0}^{\infty} a_nx^n = \sum_{n = 0}^{\infty} \frac{15}{4} x^n + \sum_{n = 0}^{\infty} \frac{3}{2} (n + 1) x^n - \sum_{n = 0}^{\infty} 18 \cdot 2^n x^n + \sum_{n = 0}^{\infty} \frac{67}{4} 3^n x^n - \sum_{n = 0}^{\infty} 2^{n + 1}(n + 1)x^n $$

Which means:

$$ a_n = \frac{15}{4} + \frac{3}{2} (n + 1) - 18 \cdot 2^n + \frac{67}{4} 3^n - 2^{n + 1}(n + 1) $$

Which is equivalent to:

$$ a_n = \frac{1}{4} \left( 21 - 2n(2^{n + 2} - 3) + 67 \cdot 3^n - 5 \cdot 2^{n + 4} \right) $$

Which is the form given in Wolfram.

Note:

Solving the general form for $F(x)$ we get:

$$ a_n = (3a_0 - a_1 - 11)2^n + (-2a_0 + a_1 + \frac{31}{4})3^n + \frac{15}{4} + \frac{3}{2} (n + 1) - 2^{n + 1} (n + 1) $$