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.

  • $\begingroup$ Think about the geometric series and its derivatives ... $\endgroup$ – Martin R Nov 6 '18 at 19:23
  • $\begingroup$ 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$. $\endgroup$ – Martin R Nov 6 '18 at 19:38
  • $\begingroup$ Thanks for the correction @MartinR, I've fixed it. Regarding your tip above, I'm not certain I understand what you imply. $\endgroup$ – Angel Politis Nov 6 '18 at 23:33
  • $\begingroup$ 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... $\endgroup$ – 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$.

  • $\begingroup$ 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$. $\endgroup$ – Angel Politis Nov 7 '18 at 8:05
  • 1
    $\begingroup$ @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$. $\endgroup$ – Martin R Nov 7 '18 at 8:10
  • $\begingroup$ 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$. $\endgroup$ – Angel Politis Nov 7 '18 at 9:56
  • $\begingroup$ @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. $\endgroup$ – Martin R Nov 7 '18 at 10:03
  • $\begingroup$ 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... $\endgroup$ – Angel Politis Nov 7 '18 at 10:22


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

  • $\begingroup$ 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 $\endgroup$ – Mustang 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}.$

  • $\begingroup$ You're right! I made this change. $\endgroup$ – Sean Roberson Nov 7 '18 at 1:16
  • $\begingroup$ 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... $\endgroup$ – 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"


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$

  • $\begingroup$ 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. $\endgroup$ – Angel Politis Nov 7 '18 at 3:49
  • $\begingroup$ @AngelPolitis Edited my post $\endgroup$ – Ameryr Nov 8 '18 at 2:49

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.