2
$\begingroup$

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?

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

The generating function I'm getting is:

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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