Recurrence relation using generating function

Question

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

Answer 1

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

Answer 2

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$