0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – heropup Dec 1 '14 at 17:51
0
$\begingroup$

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

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

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$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ That s quite obvious i just wonder if there is solution with generating functions $\endgroup$ – Seymur Mammadli Dec 1 '14 at 17:22
0
$\begingroup$

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!)

| cite | improve this answer | |
$\endgroup$

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.