# Find sequence function and general rule

the function $$a_{n+2}=3a_{n+1}-2a_n+2$$ is given, and $$a_0=a_1=1, (a_n)_{n\ge0}$$ multiplying everything by $$/\sum_{n=0}^\infty x^{n+2}$$ also adding $$\sum_{n=0}^\infty (a_{n+2}x^{n+2}+a_1x+a_0)-a_1x-a_0=\sum_{n=0}^\infty (3a_{n+1}x^{n+2}+a_0)-a_0-\sum_{n=0}^\infty 2a_nx^{n+2}+\sum_{n=0}^\infty 2x^{n+2}$$ we get $$R(X)-2x-1=3x(R(X)-1)-2x^2R(X)+\frac{2x^2}{1-x}$$ $$R(X)(1-3x+2x^2)+x-1=\frac{2x^2}{1-x}$$ $$R(X)(1-3x+2x^2)=\frac{3x^2-2x+1}{1-x}$$ $$R(X)=\frac{3x^2-2x+1}{(1-x)^2(1-2x)}=\frac{A}{(1-x)^2}+\frac{B}{1-2x}$$ so $$3x^2-2x+1=A(1-2x)+B(1-x)^2$$ $$3x^2-2x+1=x^2(B)+x(-2A-2B)+A+B$$ B=3
-2A-2B=-2
A+B=1$$\quad\Longrightarrow\quad A=-2, B=3$$ $$R(X)=\frac{-2}{(1-x)^2}+\frac{3}{1-2x}=-2\sum_{n=0}^\infty nx^{n-1}+3\sum_{n=0}^\infty (2x)^2=$$ how to proceed?

• When doing partial fraction expansion you have to take in account multiple roots in $(1-2x)^2$ – Trismegistos Apr 14 '14 at 9:13
• correction: (1-x)^2 – user2974951 Apr 14 '14 at 9:18
• Anyway $(1 - x)^2$ has also multiple roots and you have to take them into account. – Trismegistos Apr 14 '14 at 10:18

\begin{align} R(x) &= \dfrac{1-3\, x+4\, x^2}{1-4\, x+5\, x^2-2\, x^3}\\ &= \dfrac{2}{1-2 \, x} + \dfrac{1}{1-x} - \dfrac{2}{{\left(1-x\right)}^{2}}\\ &= \sum_{n\ge 0} \left(2^{n+1}-2\, n-1\right)\, x^n \end{align}
It is better to work generating functions by multiplying by $z^n$ and sum over $n \ge 0$, which here gives: $$\frac{A(z) - a_0 - a_1 z}{z^2} = 3 \frac{A(z) - a_0}{z} - 2 A(z) + 2 \frac{1}{1 - z}$$ This results in: $$A(z) = \frac{1 - 3 z + 4 z^2}{1 - 4 z + 5 z^2 - 2 z^3} = \frac{2}{1 - 2 z} + \frac{1}{1 - z} - \frac{2}{(1 - z)^2}$$ Read off the coefficients: $$a_n = 2 \cdot 2^n + 1 - 2 \binom{-2}{n} = 2^{n + 1} - 2 n - 1$$
$a_{n+2}=3a_{n+1}-2a_n+2$, $a_0=a_1=1$
Doing it the more pedestrian way, you would first find the basis solutions of the homogeneous equation that are geometric progressions, $a_n=q^n$. This is the case if $$q^2=3q-2\iff 0=(q-1)(q-2),$$ so that the general homogeneous solution is $$a_n=C+D\,2^n$$ Since the inhomogeneity is also a constant, the ansatz of similar type is $a_n=A\,n$, resulting in the equation $$A(n+2)=3A(n+1)-2An+2\iff -A=2\iff A=-2$$ so that the general solution of the inhomogeneous recursion has the form $$a_n=-2n+C+D\,2^n$$ Checking the initial conditions gives $$1=C+D=-2+C+2D\iff 0=-2+D\land C=-D+1\iff D=2\land C=-1$$ so finally $$a_n=-(2n+1)+2^{n+1}.$$