# Solve the recurrence $a_n - 3a_{n-1} + 2a_{n-2} = 6 \cdot 2^n$

Consider the recurrence

$$a_n - 3a_{n-1} + 2a_{n-2} = 6 \cdot 2^n.$$

I tried to solve this as follows. First, I found the homogeneous solution: $$a_n^{(h)} = r^2 - 3r + 2r \\ (r-2)(r-1) = 0 \\ r = 2,1 \\ a_n^{(h)} = A \cdot 2^n + B$$

While trying to solve for the particular solution (adding $$n$$ for linear independence), I get an answer which is a false statement: $$a_n^{(p)} = Cn2^n \\ Cn2^n - 3[C(n-1)2^{n-1}] + 2[C(n-2)2^{n-2}] = 6\cdot 2^n \\ 4Cn - 3[2Cn-2] + 2[Cn-2] = 6 \cdot 2^2 \\ 4Cn - 6Cn + 6 + 2Cn - 4 = 24 \\ 0Cn+2 = 24 \\ 0Cn = 22$$

I’m not sure where the issue lies. Am I performing the problem incorrectly, or does the problem have an issue?

• What you have proved is that $Cn2^n$ isn't a solution of your equation. – Yuval Filmus May 3 '19 at 6:55
• Our reference question may be helpful. – Raphael May 3 '19 at 7:02

Your calculation is an example of proof by contradiction. You assumed that $$a_n = Cn2^n$$, and reached a contradiction $$0 = 22$$. You can conclude that $$a_n \neq Cn2^n$$.
Your calculation shows that the general solution to your equation is $$a_n = A + 2^n B + n2^n C.$$ For some reason you forgot about the first two terms.
Let $$P(x) = \sum_{n=0}^\infty a_n x^n$$. Setting $$a_{-1} = a_{-2} = 0$$, we have $$(2x^2-3x+1) P(x) = \sum_{n=0}^\infty x^n (2a_{n-2} - 3 a_{n-1} + a_n) = \\ a_0 + (a_1 - 3a_0) x + \sum_{n=2}^\infty x^n (6 \cdot 2^n) = \\ a_0 + (a_1 - 3a_0) x + 24x^2 \sum_{m=0}^\infty (2x)^m = \\ a_0 + (a_1 - 3a_0) x + \frac{24x^2}{1-2x}.$$ Since $$2x^2-3x+1 = (2x-1)(x-1)$$, it follows that $$P(x) = \frac{(1-2x)(a_0 + (a_1 - 3a_0) x) + 24x^2}{(1-2x)^2(1-x)} = \frac{a_0 + (a_1 - 5a_0)x + (24-2a_1+6a_0)x^2}{(1-2x)^2(1-x)}.$$ Routine calculation shows that $$\frac{1}{(1-2x)^2(1-x)} = \sum_{n=0}^\infty (1+2^{n+1}n)x^n,$$ and so for $$n \geq 2$$ we get the formula $$a_n = a_0 (1 + 2^{n+1}n) + (a_1 - 5a_0) (1 + 2^n(n-1)) + (24 - 2a_1 + 6a_0) (1 + 2^{n-1}(n-2)).$$ Opening this up, we get the solution $$a_n = 24 - a_1 + 2a_0 - (24 - a_1 + a_0) \cdot 2^n + 12 \cdot n2^n.$$