# Recurrence relation using generating function

I tried to solve recurrence relation using generating functions

\begin{align} T_k &= 3 T_{k-1}-3T_{k-2}+T_{k-3} \\ T_0 &= 1 : T_1 = 3 : T_2 = 6 \end{align}

My approach was to equal \begin{align} T_0=x^k \end{align} but I cant get the right answer. I am quite new in Discrete Mathematics. Any kind of help or suggestion will highly appreciated

• I had posted an answer to your question but because someone else posted the exact same question within about a half hour of your posting, I strongly suspect that this is a homework exercise or an exam question. – heropup Dec 1 '14 at 17:51

Put $\displaystyle f(x)=\sum_{k\geq 0} a_k x^k$. We have for $k\geq 0$:

$$a_{k+3}=3a_{k+2}-3a_{k+1}+a_k$$ We mutiply by $x^{k+3}$, and we sum for $k\geq 0$: $$\sum_{k\geq 0}a_{k+3}x^{k+3}=3x\sum_{k\geq 0}a_{k+2}x^{k+2}-3x^2\sum_{k\geq 0}a_{k+1}x^{k+1}+x^3\sum_{k\geq 0}a_kx^k$$ We have $\displaystyle \sum_{k\geq 0}a_{k+3}x^{k+3}=f(x)-a_0-a_1x-a_2x^2$, $\displaystyle \sum_{k\geq 0}a_{k+2}x^{k+2}=f(x)-a_0-a_1x$, etc. I leave to you the computations, wich gives $f(x)$, and a last hint: Use the development in series of $(1+x)^{\alpha}$ to find $a_k$.

• Apparently, someone tried to deface this post. $($I make no comments as to intention; perhaps it was just a bad edit$)$. – Lucian Dec 1 '14 at 18:56

I'm not familiar with the generating function approach, but you can use an eigenvalue approach to solve this:

$T_{k} = 3T_{k-1} - 3T_{k-2} + T_{k-3}$ gives us the characteristic polynomial:

$$\lambda^{3} - 3\lambda^{2} + 3 \lambda - 1 = 0$$

We get eigenvalues $\lambda = 1$ with multiplicity $3$. And so this gives us a general form solution:

$$T_{n} = A + Bn + Cn^{2}$$

Now use your initial conditions to solve for $A, B, C$:

$T(0) = 1 = A$
$T(1) = 3 = A + Bn + Cn^{2} = 1 + B + C$
$T(2) = 6 = A + 2B + 4C = 1 + 2B + 4C$

• That s quite obvious i just wonder if there is solution with generating functions – Seymur Mammadli Dec 1 '14 at 17:22

A nice question with a surprise at the end.

The standard ordinary generating function approach leads to; $$GF=\frac{1}{1-3x+3x^2-x^3}$$ The 1, 3, 3, 1 denominator sparks thoughts of Pascal's Triangle; $$GF=\frac{1}{(1-x)^3}$$ And this is the well known generator of the triangular numbers; $$GF=\frac{1}{(1-x)^3}=1+3x+6x^2+10x^3+15x^4+\dots$$ To verify the answer check that the original recurrence relation also generates the triangular numbers.

(It does!)