# Solve recurring sequence using a generating function

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.

• Think about the geometric series and its derivatives ... Nov 6 '18 at 19:23
• Note that you have an error right at the beginning, it should be $F(x) = a_0 + a_1 x + x_2 x^2 + \ldots$. Nov 6 '18 at 19:38
• Thanks for the correction @MartinR, I've fixed it. Regarding your tip above, I'm not certain I understand what you imply. Nov 6 '18 at 23:33
• You have it wrong, $\frac{4x^2+2x+2}{(1-x)^3}=2+8x+22x^2+44x^3+74x^4+112x^5+ \dots$. For example $3x\sum_{n\ge 3}{a_{n-1}x^{n-1}}$ is not equal to $3xA(x)$, instead it is $3x\sum_{n\ge 2}{a_{n}x^{n}}$, now the sum is almost $A(x)$ but not quite...
– Sil
Nov 7 '18 at 8:40

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

• Hey Martin, thanks for the answer and the effort. While it mostly makes sense to me, there has to be a mistake somewhere, because the explicit formula you found doesn't yield the same results as the recursive one. For $a_3$, the recursive formula yields $a_3=3a_2-3a_1+a_0=12-6+2=8$, while yours yields $a_3=n^2-2n+2=9-6+2=5$. Nov 7 '18 at 8:05
• @AngelPolitis: Sorry, that was a typo in the last line. $(n+1)(n+2) - 2n(n+1) +2(n-1)n$ expands to $n^2-n+2$. Nov 7 '18 at 8:10
• Thanks, Martin, it seems fine now. One last thing I can't get my head around is how you went from $(n+1)(n+2)\bigl(x^n - 2x^{n+1} +2x^{n+2} \bigr)$ to $\bigl( (n+1)(n+2) - 2n(n+1) +2(n-1)n\bigr) x^n$. Nov 7 '18 at 9:56
• @AngelPolitis: That's quite similar to what you did with $A(x)$. Write as three sums, then shift the indices so that $x^{n+1}$ and $x^{n+2}$ become $x^n$ again. Nov 7 '18 at 10:03
• I have tried that, but I always get some $x$ values, when I write it as three sums. Then, when I try to find a way to change them, I end up reverting it to the first equation and on goes the cycle... Nov 7 '18 at 10:22

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

• There was a mistake in the generating function I have corrected it. Now $a_3=8$ in the new generating function as you can check Nov 7 '18 at 6:44

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

• You're right! I made this change. Nov 7 '18 at 1:16
• I've flagged the comment as no longer needed, but looking at it more closely now... is the $\frac{1}{4}\binom{n+2}{2}$ claimed to be the final solution? Because already $n=0$ gives $\frac{1}{4}$, clearly not correct...
– Sil
Nov 7 '18 at 8:57

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

• While it's true that the formula $a_n=2−n+n^2$ apparently yields the correct results, how you ended up with that formula isn't clear to me. The part where you say "hence the solution is $a_n = c_1 1^n +c_2 n + c_3 n^2$" is also not clear. With some more elaboration on how you get from one step to another, this answer can be a good alternate solution, even though it fails to use generating functions as requested. Nov 7 '18 at 3:49
• @AngelPolitis Edited my post Nov 8 '18 at 2:49