%This commad provides the text in the first column of the recurences
%
%This command has one parameter:
%       1) The width of the text
\newcommand\TTwoRecurOne[1]{%
   \parbox[t]{#1}{%
      \TTwoRecurenceFontSize
      %This command add a small line between 2 paragraphs to
      %better separate different elements.
      \def\Filet{\par\centerline{\rule{5em}{.5pt}}\par}
      \deflength{\parskip}{\TTwoRecurParSkip}
      %We accept a unbalanced last column
      %\defcounter{unbalance}{2}
      %Width of the vertical rule to separate columns.
      \deflength{\columnseprule}{.4pt}
      \DisplaySpace{\TTwoDisplaySpace}{\TTwoDisplayShortSpace}
 

      \begin{multicols}{3}
      \TTwoTitle{Master method:}
      \AdjustSpace{-.75ex plus .25 ex minus .5ex}
      \begin{DisplayFormulae}{1}{0pt}{2ex plus 1ex minus 1ex}{\SmallChar}{\StyleWithoutNumber}
         \Fm{T(n) = aT(n/b) + f(n)}
         \Fm{\MathRemark[\relax]{a\geq 1, b > 1}}
      \end{DisplayFormulae}

      \Filet

      \begin{DisplayFormulae}{1}{0pt}{2ex plus 1ex minus 1ex}{\SmallChar}{\StyleWithoutNumber}
      \unskip If \Fm[true]{\exists\,  \epsilon > 0} such that \Fm[true]{f(n) = O(n^{\log_b a - \epsilon})} 
      then: \Fm[true]{T(n) = \Theta(n^{\log_b a})}
      \end{DisplayFormulae}

      \Filet
      \begin{DisplayFormulae}{1}{0pt}{2ex plus 1ex minus 1ex}{\SmallChar}{\StyleWithoutNumber}
          \unskip If \Fm[true]{f(n) = \Theta(n^{\log_b a})} then
         \Fm[true]{T(n) = \Theta(n^{\log_b a} \log_2 n)}
      \end{DisplayFormulae}

      \Filet

      \begin{DisplayFormulae}{1}{0pt}{2ex plus 1ex minus 1ex}{\SmallChar}{\StyleWithoutNumber}
         \unskip  If \Fm[true]{\exists\, \epsilon > 0} such that 
         \Fm[true]{f(n) = \Omega(n^{\log_b a + \epsilon})},
         and \Fm[true]{\exists\, c < 1} such that \Fm[true]{a f(n/b) \leq cf(n)} for large $n$,
         then:
          \Fm[true]{T(n) = \Theta(f(n))}
      \end{DisplayFormulae}

      \TTwoTitle{Substitution \textup{(}example\textup{)}:}
      \begin{DisplayFormulae}{1}{0pt}{2ex plus 1ex minus 1ex}{\SmallChar}{\StyleWithoutNumber}
      \unskip  Consider the following recurrence:\\
          \Fm[true]{T_{i+1} = 2^{2^i} \cdot T_i^2\MathRemark{T_1 = 2}}.
      Note that $T_i$ is always a power of two.
     \end{DisplayFormulae}

      \begin{DisplayFormulae}{1}{0pt}{2ex plus 1ex minus 1ex}{\SmallChar}{\StyleWithoutNumber}
          \unskip  Let \Fm[true]{t_i = \log_2 T_i}.
          Then we have:
          \Fm[true]{t_{i+1} = 2^i + 2 t_i\MathRemark{t_1 = 1}}
      \end{DisplayFormulae}

      \begin{DisplayFormulae}{1}{0pt}{2ex plus 1ex minus 1ex}{\SmallChar}{\StyleWithoutNumber}
         \unskip  Let \Fm[true]{u_i = t_i/2^i}.
         Dividing both sides of the previous equation by \Fm[true]{2^{i+1}} we get: 
         \Fm[true]{\frac{t_{i+1}}{2^{i+1}} = \frac{2^i}{2^{i+1}} + \frac{t_i}{2^i}}
      \end{DisplayFormulae}

      \begin{DisplayFormulae}{1}{0pt}{2ex plus 1ex minus 1ex}{\SmallChar}{\StyleWithoutNumber}
         \unskip   Substituting we find:\\%[-1ex plus .5ex minus .5ex]
          \Fm[true]{u_{i+1} = 2^{-1} + u_i\MathRemark{u_1 = 2^{-1}}},
         which is simply \Fm[true]{u_i = i/2}.

      So we find that \Fm[true]{T_i} has the closed form \Fm[true]{T_i = 2^{i2^{i-1}}}.
      \end{DisplayFormulae}

      \TTwoTitle{Summing factors \textup{(}example\textup{)}:} 
      \begin{DisplayFormulae}{1}{0pt}{2ex plus 1ex minus 1ex}{\BigChar}{\StyleWithoutNumber}
         \unskip  Consider the following recurrence:\\
          \Fm[true]{T(n) = 3T(n/2) + n\MathRemark{T(1) = 1}}
      \end{DisplayFormulae}

      \begin{DisplayFormulae}{1}{0pt}{2ex plus 1ex minus 1ex}{\BigChar}{\StyleWithoutNumber}
         \unskip  Rewrite so that all terms involving $T$ are on the
         left side:\\
          \Fm[true]{T(n) - 3T(n/2) = n}

      Now expand the recurrence,
      and choose a factor which makes the left side ``telescope''.
      \end{DisplayFormulae}

      \begin{DisplayFormulae}{1}{0pt}{2ex plus 1ex minus 1ex}{\BigChar}{\StyleWithoutNumber}
          \Fm{\left(T(n) - 3T(n/2) = n\right)} 
          \def\FormulaRecur{\left(T(n/2) - 3T(n/4) = n/2\right)}
          \Fm{\FormulaRecur}
          %To get the size of the preceding formula
          \WriteFormula{0pt}{\TmpLengthA}{\FormulaRecur}{false}
          \Fm{\makebox[\TmpLengthA][c]{$\vdots$}}
          \Fm{3^{\log_2 n - 1}\left(T(2) - 3T(1) = 2\right)} 
      \end{DisplayFormulae}

      \begin{DisplayFormulae}{1}{0pt}{2ex plus 1ex minus 1ex}{\SmallChar}{\StyleWithoutNumber}
         \unskip  Let \Fm[true]{m = \log_2 n}.
         Summing the left side we get:
         \def\FirstPart{T(n) - 3^mT(1)}
         \FmPartA{\FirstPart= T(n) - 3^m}
         \FmPartB{\FirstPart}{= T(n) - n^k}\\ 
         \MathRemark[\relax]{\text{where } k = \log_2 3 \approx 1\SepDecimal 58496}.
      \end{DisplayFormulae}

      Summing the right side we get:\\
            \begin{DisplayFormulae}{1}{0pt}{2ex plus 1ex minus 1ex}{\BigChar}{\StyleWithoutNumber}
                \Fm{\sum_{i=0}^{m-1} \frac{n}{2^i} 3^i = n \sum_{i=0}^{m-1} \left(\frac{3}{2} \right)^i}
            \end{DisplayFormulae}

      \begin{DisplayFormulae}{1}{0pt}{2ex plus 1ex minus 1ex}{\BigChar}{\StyleWithoutNumber}
      \unskip  Let \Fm[true]{c = \frac{3}{2}}.
      Then we have:
            \def\FirstPart{n \sum_{i=0}^{m-1} c^i}
            \FmPartA{\FirstPart = n \left( \frac{c^m-1}{c-1} \right)}
            \FmPartB{\FirstPart}{= 2 n \left( c^{\log_2 n } - 1 \right)}
            \FmPartB{\FirstPart}{= 2 n \left( c^{(k-1) \log_c n } - 1 \right)}
            \FmPartB{\FirstPart}{= 2 n^k  - 2n} 
      and so \Fm[true]{T(n) = 3 n^k - 2n}.
      \end{DisplayFormulae}

      Full history recurrences can often be changed to limited history ones.

      \TTwoTitle{Example:}
      \AdjustSpace{-1.5ex plus .5ex minus .5ex}
      \begin{DisplayFormulae}{1}{0pt}{2ex plus 1ex minus 1ex}{\BigChar}{\StyleWithoutNumber}
         \unskip  Consider:
         \Fm{T_i = 1 + \sum^{i-1}_{j=0} T_j\MathRemark{T_0 = 1}}\\
         Note that:
         \Fm{T_{i+1} = 1 + \sum^i_{j=0} T_j}\\
         By subtracting we find:
            \def\FirstPart{T_{i+1} - T_i}
            \FmPartA{\FirstPart = 1 + \sum^i_{j=0} T_j - 1 - \sum^{i-1}_{j=0} T_j}
            \FmPartB{\FirstPart}{= T_i}\\ 
        And so \Fm[true]{T_{i+1} = 2T_i = 2^{i+1}}.
      \end{DisplayFormulae}

      \TTwoTitle{Generating functions:}
      \begin{enumerate}[noitemsep,nolistsep]
         \item Multiply both sides of the equation by $x^i$. 
         \item Sum both sides over all $i$ for which the equation is valid. 
         \item Choose a generating function $G(x)$.
               Usually $G(x) = \sum_{i=0}^\infty x^i g_i$.
         \item Rewrite the equation in terms of the generating function $G(x)$. 
         \item Solve for $G(x)$. 
         \item The coefficient of $x^i$ in $G(x)$ is $g_i$.
      \end{enumerate}

      \TTwoTitle{Example:}
      \begin{DisplayFormulae}{1}{0pt}{2ex plus 1ex minus 1ex}{\BigChar}{\StyleWithoutNumber}
         \unskip  
         Let the equation: \\
         \Fm{g_{i+1} = 2 g_i + 1\MathRemark{g_0 = 0}}.\\[.6ex plus .2ex minus .1ex]
         Multiply and sum:
         \Fm{\sum_{i\geq 0} g_{i+1} x^i = \sum_{i\geq 0} 2 g_i x^i + \sum_{i\geq 0} x^i}
         We choose: \Fm[true]{G(x) = \sum_{i\geq 0} x^i g_i}.\\
         Rewrite in terms of \Fm[true]{G(x)}:
         \Fm{\frac{G(x)-g_0}{x} = 2 G(x) + \sum_{i\geq 0} x^i}\\
         Simplify:
         \Fm{\frac{G(x)}{x} = 2 G(x) + \frac{1}{1-x}}\\
         Solve for \Fm[true]{G(x)}:
         \Fm{G(x) =  \frac{x}{(1-x)(1-2x)}}.\\
         Expand this using partial fractions:
               \def\FirstPart{G(x)}
               \FmPartA{\FirstPart = x \left(\frac{2}{1-2x} - \frac{1}{1-x}\right)}
               \FmPartB{\FirstPart}{= x \left(2 \sum_{i\geq 0} 2^i x^i - \sum_{i\geq 0} x^i\right)}
               \FmPartB{\FirstPart}{= \sum_{i\geq 0} (2^{i+1} - 1) x^{i+1}}\\
         So \Fm[true]{g_i = 2^i - 1}.
      \end{DisplayFormulae}
      \end{multicols}
   }%
}