Solve recurring sequence using a generating function

Question

I have the sequence $a_n=3a_{n-1}-3a_{n-2}+a_{n-3}$, $\forall\ n \ge 3$, with $a_0=2$, $a_1=2$, $a_2=4$ being the known terms, and I want to find a non-recursive equation for $a_n$ using a generating function.

What I have done:

$$ \begin{align} A(x) & = \sum_{n\ge0}{a_nx^n} = a_0+a_1x+a_2x^2+\sum_{n\ge 3}\left({3a_{n-1}-3a_{n-2}+a_{n-3}}\right)x^n\\ & = 2+2x+4x^2+3x\sum_{n\ge 3}{a_{n-1}x^{n-1}} -3x^2\sum_{n\ge 3}{a_{n-2}x^{n-2}} +x^3\sum_{n\ge 3}{a_{n-3}x^{n-3}}\\ & = 2+2x+4x^2+3xA(x)-3x^2A(x)+x^3A(x)\\ & = \frac{2+2x+4x^2}{1-3x+3x^2-x^3}\\ & = \frac{4x^2+2x+2}{(1-x)^3} \end{align} $$

As shown above, I have reached a solution for $A(x)$, but I'm not sure how to use it to find a solution for $a_n$. Any tips pointing me in the right direction would be greatly appreciated.

Answer 1

Your calculation is correct up to $$ \begin{align} A(x) & = \sum_{n\ge0}{a_nx^n} = a_0+a_1x+a_2x^2+\sum_{n\ge 3}\left({3a_{n-1}-3a_{n-2}+a_{n-3}}\right)x^n\\ & = 2+2x+4x^2+3x\sum_{n\ge 3}{a_{n-1}x^{n-1}} -3x^2\sum_{n\ge 3}{a_{n-2}x^{n-2}} +x^3\sum_{n\ge 3}{a_{n-3}x^{n-3}} \end{align} $$

But then $$ \begin{align} \sum_{n\ge 3}{a_{n-1}x^{n-1}} &= \sum_{n\ge 2}{a_{n}x^{n}} = A(x) - 2 - 2x \\ \sum_{n\ge 3}{a_{n-2}x^{n-2}} &= \sum_{n\ge 1}{a_{n}x^{n}} = A(x) - 2 \end{align} $$ so that $$ A(x) = 2+2x+4x^2 + 3x(A(a) - 2-2x) -3x^2(A(x) - 2) + x^3A(x) $$ which gives $$ A(x) = \frac{2-4x + 4x^2}{(1-x)^3} \, . $$

Differentiating the geometric series $\frac{1}{1-x} = \sum_{n=0}^\infty x^n$ twice gives $$ \frac{2}{(1-x)^3} = \sum_{n=2}^\infty n(n-1) x^{n-2} = \sum_{n=0}^\infty (n+1)(n+2)x^n \, , $$ therefore $$ \begin{align} A(x) &= (1-2x + 2 x^2) \sum_{n=0}^\infty (n+1)(n+2)x^n \\ &= \sum_{n=0}^\infty (n+1)(n+2)x^n - 2\sum_{n=0}^\infty (n+1)(n+2)x^{n+1} +2\sum_{n=0}^\infty (n+1)(n+2)x^{n+2} \\ &= \sum_{n=0}^\infty (n+1)(n+2)x^n - 2\sum_{n=1}^\infty n(n+1)x^n +2\sum_{n=2}^\infty (n-1)nx^n \\ &= \sum_{n=0}^\infty (n+1)(n+2)x^n - 2\sum_{n=0}^\infty n(n+1)x^n +2\sum_{n=0}^\infty (n-1)nx^n \\ &= \sum_{n=0}^\infty \bigl( (n+1)(n+2) - 2n(n+1) +2(n-1)n\bigr) x^n \\ &= \sum_{n=0}^\infty (n^2 -n+2) x^n \end{align} $$ and $a_n = n^2-n+2$.

Answer 2

Using Martin's hint, recall that $$ \frac{d^2}{dx^2} \left( \frac{1}{1-x} \right ) = \frac{2}{(1-x)^3}. $$

From a table (erm, Wikipedia), we see that the generating function for the sequence $a_n = \binom{n+2}{2}$ is the function $g(x) = \frac{1}{(1-x)^3}$. Doing some rearrangements we see that the intended solution is just $\frac{1}{4}\binom{n+2}{2}.$

Answer 3

$A(x)=2+2x+4x^2+3x\sum_{n\geq3}a_{n-1}x^{n-1}-3x^2\sum_{n\geq3}a_{n-2}x^{n-2}+x^3\sum_{n\geq3}a_{n-3}x^{n-3}$

$\Rightarrow A(x)=2-4x+4x^2+3x\sum_{n\geq1}a_{n-1}x^{n-1}-3x^2\sum_{n\geq2}a_{n-2}x^{n-2}+x^3A(x)$

$\Rightarrow A(x)=2-4x+4x^2+3xA(x)-3x^2A(x)+x^3A(x)$

$\Rightarrow (-x^3+3x^2-3x+1)A(x)=2-4x+4x^2$

$\Rightarrow A(x)=\frac{2-4x+4x^2}{-x^3+3x^2-3x+1}=\frac{2(2x^2-2x+1)}{(1-x)^3}=\frac{4}{1-x}-\frac{4}{(1-x)^2}+\frac{2}{(1-x)^3}$

I will use $\sum_{n\geq 0}x^n=\frac{1}{1-x}$

claim: $\frac{1}{(1-x)^k}=\sum_{n\geq 0}\binom{n+k-1}{n}x^n$

So, $\frac{1}{(1-x)^k}=(\sum_{n\geq 0}x^n)^k=\sum_{n\geq0}x^n(\sum_{{i_1}+{i_2}+...+{i_k}=n}1)=\sum_{n\geq0}x^n\binom{n+k-1}{n}$

So, now you need to find $a_n$ which is the coefficient of $x^n$ in the generating function

For your problem, it is $4\cdot\binom{n+1-1}{n}-4\cdot\binom{n+2-1}{n}+2\cdot\binom{n+3-1}{n}=4-4(n+1)+\frac{2(n+1)(n+2)}{2}=n^2+3n+2-4n\\=n^2-n+2$

Answer 4

$a_n=3a_{n-1}-3a_{n-2}+a_{n-3}$, $\forall\ n \ge 3$, with $a_0=2$, $a_1=2$, $a_2=4$ being the known

There is a theorem that said the following: Let $q$ be a non zero number then $a_n = q^n$ is a solution of the linear homogeneous recurrence relation $a_n -c_1 a_{n-1} - a_2 a_{n-2} -\cdots - a_k a_{n-k} = 0$ with constant coefficients iff $q$ is a root of the polynomial equation $x^n - c_1 x^{n-1} - \cdots a_k = 0$ From "Introductory Combinatorics, 5th edition by Richard Brualdi". It is similar to differential equations you will find the roots if a root $r$ has a multiplicity say $k$ then the general solution $a_n = c_1 r^n + c_2 n r^n + c_3 n^2 r^n + \cdots + c_k n^k r^n $ Check the link "Roots of the characteristic polynomial"

https://en.wikipedia.org/wiki/Recurrence_relation

You can try this let

$a_n = p^n$ then

$$p^n -3p^{n-1} +3p^{n-2}-p^{n-3}=0$$ Factor $p^{n-3}$ $$p^{n-3} ( p^3 - 2p^2 + 2p - 1) = 0$$ $$p^3 -3p^2 +3p-1=0$$ Factor $$(p-1)(p^2-2p+1)=(p-1)(p-1)^2 =0$$ $(p-1)^3=0$ hence the solution is $1$ with multiplicity $3$ so $a_n = c_1 1^n +c_2 1^n n + c_3 1^n n^2$ But we know that $1^n =1 $ then using the given initials to find the constants $a_0 = c_1 = 2 $ etc.. $$a_n = 2 - n + n^2$$ checking $a_3=8, a_4=14$