How to solve this using generating functions? 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.
 A: 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.
A: 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\}
$$
