How to solve this using generating functions?

Question

I have an equation:

$t_n =2t_{n-1}+t_{n-2}; t_0=0, t_1=1$

So, I rewrote this using generating functions as:

$\sum_{n=0}^{\infty} t_nz^n = 2\sum_{n=0}^{\infty} t_{n-1}z^n+\sum_{n=0}^{\infty} t_{n-2}z^n$

$g(z)=2zg(z)+z^2g(z)$

$g(z)={1\over{1-2z-z^2}}$

I don't know how to proceed after this? Can you help me please? Thanks.

Answer 1

The formula $t_n = 2t_{n - 1} + t_{n - 2}$ only makes sense if $n \ge 2$. So you should do the computation as

$$ G(z) = \sum_{n \ge 0} t_nz^n = t_0 + t_1z + \sum_{n \ge 2} t_nz^n = z + \sum_{n \ge 2}\left(2t_{n - 1} + t_{n - 2}\right)z^n$$

from which one finds

$$ G(z) = z + 2z(G(z) - t_0) + z^2G(z) = \frac{z}{1 - 2z - z^2}.$$

To compute this, one needs to factor the denominator:

$$ G(z) = \frac{z}{(1 - (1 - \sqrt 2)z)(1 - (1 + \sqrt 2)z)}.$$

This gives you

$$G(z) = \frac{A}{1 - (1 - \sqrt 2)z} + \frac{B}{1 - (1 + \sqrt 2)z} = \sum_{n \ge 0} \left( A(1 - \sqrt 2)^n + B(1 + \sqrt 2)^n \right)z^n $$

for some values of $A, B$ that you need to determine from the sequence.

---

By the way, in order to factorize a polynomial

$$ 1 + a_1z + a_2z^2 + \dots + a_nz^n $$

as

$$ (1 - r_1z)(1 - r_2z)\cdots(1-r_nz)$$

what you do is you solve

$$ a_n + a_{n - 1}z + \cdots + a_1z^{n - 1} + z^n = 0 $$

to get $r_1, \dots, r_n$. That is $r_1, \dots, r_n$ are the roots with the coefficients reversed.

Answer 2

The correct and most effective approach (re. to "Concrete Mathematics") starts from writing the recurrence in such a way that it incorporates the initial conditions and is valid for all the values of the index $n$.
Since the $t_n$ are assumed to be null for $n < 0$, we shall rewrite your recurrence as: $$ t_{\,n} = 2\,t_{\,n - 1} + t_{\,n - 2} + \left[ {1 = n} \right]\quad \left| {\;\forall n} \right. $$ where we make profitable use of the Iverson bracket $$ \left[ P \right] = \left\{ {\begin{array}{*{20}c} 1 & {P = TRUE} \\ 0 & {P = FALSE} \\ \end{array} } \right. $$

Now we multiply by $z^n$ and sum $$ \eqalign{ & g(z) = \sum\limits_{0\, \le \,n} {t_{\,n} \,z^{\,n} } = 2\,\sum\limits_{0\, \le \,n} {t_{\,n - 1} \,z^{\,n} } + \sum\limits_{0\, \le \,n} {t_{\,n - 2} \,z^{\,n} } + \sum\limits_{0\, \le \,n} {\left[ {1 = n} \right]\,z^{\,n} } = \cr & = 2\,z\,g(z) + z^2 g(z) + z \cr} $$ so $$ g(z) = {z \over {1 - 2z - z^2 }} $$

To this expression we can apply partial fraction decomposition to obtain $$ \eqalign{ & g(z) = {z \over {1 - 2z - z^2 }} = - {z \over {\left( {z - \left( { - 1 - \sqrt 2 } \right)} \right)\left( {z - \left( { - 1 + \sqrt 2 } \right)} \right)}} = \cr & = - {z \over {\left( {z - a} \right)\left( {z - b} \right)}} = - {1 \over {a - b}}\left( {{a \over {\left( {z - a} \right)}} - {b \over {\left( {z - b} \right)}}} \right) = \cr & = {1 \over {a - b}}\left( {{1 \over {\left( {1 - z/a} \right)}} - {1 \over {\left( {1 - z/b} \right)}}} \right) = \cr & = {1 \over {a - b}}\sum\limits_{0\, \le \,n} {\left( {{1 \over {a^{\,n} }} - {1 \over {b^{\,n} }}} \right)\,z^{\,n} } \cr} $$

Therefore we get for $t_n$ $$ \eqalign{ & t_{\,n} = {1 \over {a - b}}\left( {{1 \over {a^{\,n} }} - {1 \over {b^{\,n} }}} \right) = {1 \over {2\sqrt 2 }}\left( {{1 \over {\left( {\sqrt 2 - 1} \right)^{\,n} }} - {1 \over {\left( { - 1 - \sqrt 2 } \right)^{\,n} }}} \right) = \cr & = {1 \over {2\sqrt 2 }}\left( {{1 \over {\left( {\sqrt 2 - 1} \right)^{\,n} }} - {{\left( { - 1} \right)^{\,n} } \over {\left( {\sqrt 2 + 1} \right)^{\,n} }}} \right) = \cr & = {{\left( {\sqrt 2 + 1} \right)^{\,n} - \left( { - 1} \right)^{\,n} \left( {\sqrt 2 - 1} \right)^{\,n} } \over {2\sqrt 2 }} = \cr & = {1 \over {2\sqrt 2 }}\sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( {\left( \matrix{ n \cr k \cr} \right)\,\sqrt 2 ^{\,k} - \left( { - 1} \right)^{\,n} \left( \matrix{ n \cr k \cr} \right)\,\sqrt 2 ^{\,k} \left( { - 1} \right)^{\,n - k} } \right)} = \cr & = {1 \over {2\sqrt 2 }}\sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( {\left( \matrix{ n \cr k \cr} \right)\, - \left( { - 1} \right)^{\,k} \left( \matrix{ n \cr k \cr} \right)\,} \right)\sqrt 2 ^{\,k} } = \cr & = \sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,n} \right)} {\left( \matrix{ n \cr 2j + 1 \cr} \right)2^{\,j} } \cr} $$ whose first values are: $$ t = \left\{ {0,1,2,5,12,29,70,169, \cdots } \right\} $$