1
$\begingroup$

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?

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.