1
$\begingroup$

I'm trying to solve the recurrence $a_n=3a_{n-1}-2a_{n-2}+3$ for $a_0=a_1=1$. First I solved for the homogeneous equation $a_n=3a_{n-1}-2a_{n-2}$ and got $\alpha 1^n+\beta 2^n=a_n^h$. Solving this gives $a_n^h =1$. The particular solution, as I understand, will be $a_n^*=B$ since $f(n)=3\times 1^n$. But then I get $B=a^*=3a^*_{n-1}-2a^*_{n-2}+3=B+3$. This has to be a mistake, but I don't see what I did wrong.

$\endgroup$
2
$\begingroup$

$$a_n - a_{n-1}+3=2(a_{n-1}-a_{n-2}+3)$$ $$a_n - a_{n-1}+3=2^{n-1}(a_1-a_0+3)=3\cdot 2^{n-1}$$ $$\\$$ $$a_n = a_{n-1} + 3\cdot (2^{n-1}-1)$$ $$a_{n-1} = a_{n-2} + 3\cdot (2^{n-2}-1)$$ $$...$$ $$a_1 = a_0 + 3\cdot (2^0-1)$$ Adding side by side, $$a_n=a_0+3\cdot (2^0+2^1+...+2^{n-1}-n)$$ $$=1+3\cdot (2^n-1-n)=3\cdot2^n-3n-2$$

$\endgroup$
2
$\begingroup$

Let $f(x) = \sum_{n=0}^\infty a_nx^n$. Multiplying the recurrence by $x^n$ and summing over $n\geqslant 2$ we find that the LHS is $$\sum_{n=2}^\infty a_nx^n = f(x)-1-x $$ and the RHS is $$3\sum_{n=2}^\infty a_{n-1}x^n - 2\sum_{n=2}^\infty a_{n-2}x^n + 3\sum_{n=2}^\infty x^n = 3x(f(x)-1) - 2x^2f(x)+\frac{3x^2}{1-x}. $$ Equating the above and $f(x)$ we find that $$f(x) = \frac{1-2x}{1-3x+2x^2} + \frac{3x^2}{(1-x)(1-3x+2x^2)}. $$ Partial fraction decomposition yields $$f(x) = \frac1{1-x} + \frac3{1-2x} - \frac3{(1-x)^2}, $$ which has series representation $$f(x) = \sum_{n=0}^\infty(1+3\cdot(2^n) - 3(n+1))x^n. $$ It follows that $$a_n = 1+3\cdot(2^n) - 3(n+1),\ n\geqslant0. $$

$\endgroup$
1
$\begingroup$

Hint: Look for a particular solution of the shape $a_n^\ast=Bn$. You should get $B=-3$.

$\endgroup$
5
  • 1
    $\begingroup$ So here's what I did. I used your $a_n^*=Bn$ and got that $B=-3$ and so $a_n^*=-3n$. So then the solution to the inhomogenous equation is $a_n=\alpha +\beta 2^n-3n$. Solving with the initial conditions gives $a_n=3\cdot 2^n-3n-2$. This is the correct solution. So thanks. How did you know to use that particular solution? $\endgroup$
    – pretzelman
    Nov 24 '15 at 3:08
  • $\begingroup$ It is a standard "trick" both for differential equations and linear recurrences with constant coefficients. If $1$ were a double root of the characteristic polynomial, we would have to go up to a quadratic in $n$. $\endgroup$ Nov 24 '15 at 3:17
  • $\begingroup$ so basically, if the 'usual' particular solutions fails, then we can just tack on an $n$ and then try again? $\endgroup$
    – pretzelman
    Nov 24 '15 at 3:19
  • $\begingroup$ Exactly. Constant must fail because $a-3a+2a=0$. $\endgroup$ Nov 24 '15 at 3:21
  • $\begingroup$ Okay! Thanks, André! $\endgroup$
    – pretzelman
    Nov 24 '15 at 3:21
1
$\begingroup$

Because of the constant term, define $$b_n=a_n+c n +d$$ Replacing in $$a_n=3a_{n-1}-2a_{n-2}+3$$ leads to $$b_n=3 b_{n-1}-2 b_{n-2}+c+3$$ So, choose $c=-3$ and the recurrence becomes $$b_n=3 b_{n-1}-2 b_{n-2}$$ Then, as usual, the characteristic equation $r^2-3r+2=0$ which has roots $r_1=1$, $r_2=2$. So $$b_n=C_1 \,1^n+C_2 \,2^n=C_1+C_2 \,2^n$$ $$a_n=C_1+C_2 \,2^n-3n$$ Apply the initial conditions $$a_0=C_1+C_2=1\quad \quad \quad a_1=C_1+2C_2-3=1$$ which give $C_1=-2$ and $C_2=3$ which finally give $$a_n=-2+3 \times 2^n-3n$$

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