\documentclass[a4paper,12pt,brazil,landscape]{article}
\newcommand{\ultimamodificacao}{30 de outubro de 2007}
\usepackage[latin1]{inputenc}
\usepackage[brazil]{babel}
\usepackage{epsfig,graphicx,color,latexsym,alltt,calc,ifthen,slides,hyperref} 
 
\begin{document}


\setbackgroundcolor{white}
\settextcolor{blue}
\setslidetitlecolor{red}
\setbordercolor{darkblue}

\setedition{slides.sty}
\newincluder{fulledition}
\setincluder{fulledition}{true}

\sffamily 
\bfseries 
\mathversion{bold}
\Hugesize 
%\Hugefont

\hypertarget{inicio}{}
\title{Rela\c{c}\~oes de Recorr\^encia \\ Baseado em Townsend (1987), Cap. 4}
\author{Newton José Vieira}
\lhead{Matemática Discreta}
\rhead{Capítulo 4}
\lfoot{UFMG}
%\rfoot{rsb}
\organization{UFMG}
\cfoot{\hyperlink{inicio}{\threebigotimes}~~~\hyperlink{sumario}{\threebigoplus}}
\date{\ultimamodificacao}
\titlepage

\newslide{SUMÁRIO}
\hypertarget{sumario}{}
%\begin{twoblocks}
\begin{itemize}
\item \hyperlink{relacoes-recorrencia-1}{Relações de Recorrência}
\item \hyperlink{rr-definicoes-1}{RR's Lineares com Coeficientes Constantes: Definições}
\item \hyperlink{rr-solucao-1}{RR's Lineares com Coeficientes Constantes: Solução}
\item \hyperlink{outras-tecnicas-1}{Outras Técnicas para Resolução de RRs}
\item \hyperlink{div-e-conquista}{Relações Tipo Divisão e Conquista}
\end{itemize}
%\centralbar{13cm}
%\begin{itemize}
%\item \hyperlink{comandos}{Comandos Especiais}
%\end{itemize}
%\end{twoblocks}

\pagenumbering{arabic}

%--------------------------------------------------------------------------------------------

\section{RELAÇÕES DE RECORRÊNCIA}
\hypertarget{relacoes-recorrencia-1}{}
\setskiplink{capitulo4}

\newslide{\bf Rela\c{c}\~oes de Recorr\^encia}

\begin{itemize}
 \item \textcolor{black}{Defini\c{c}\~{a}o:}
       \begin{quote}
        Uma \textcolor{black}{rela\c{c}\~{a}o de recorr\^{e}ncia} (RR) \'{e} uma f\'{o}rmula
        que consta de duas partes:
        \begin{itemize}
         \item um conjunto de \textcolor{black}{condi\c{c}\~{o}es iniciais} (condi\c{c}\~{o}es de contorno); e
         \item uma \textcolor{black}{parte recorrente}.
        \end{itemize}
        (Uma RR \'{e} um esquema recursivo para computar uma sequ\^{e}ncia de n\'{u}meros.)
       \end{quote}

 \item Exemplo:
       \begin{quote}
        RR que define a sequ\^{e}ncia de Fibonacci:
        \begin{itemize}
         \item $a_1=1$, $a_2=1$;
         \item $a_n=a_{n-1}+a_{n-2}$ para $n\geq 3$.
        \end{itemize}
       \end{quote}
\end{itemize}
%--------------------------------------------------------------------------------------------

\newslide{\bf Rela\c{c}\~oes de Recorr\^encia}

\begin{itemize}
 \item \textcolor{black}{Solu\c{c}\~{a}o} de uma rela\c{c}\~{a}o de recorr\^{e}ncia:

       \begin{quote}
        Uma f\'{o}rmula fechada para a fun\c{c}\~{a}o definida pela RR.
       \end{quote}

 \item Exemplo:
       \begin{quote}
        Solu\c{c}\~{a}o para a RR que define a sequ\^{e}ncia de Fibonacci:
 
        \[a_n=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n-
           \frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n\mbox{.}\]
       \end{quote}
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{Tr\^es algoritmos para calcular $a_n$ (da sequ\^{e}ncia de Fibonacci)}

\begin{itemize}
 \item Baseado na RR, \textcolor{black}{iterativo} $\Longrightarrow$ linear.
 \item Baseado na RR, \textcolor{black}{recursivo} $\Longrightarrow$ exponencial.
 \item Baseado na \textcolor{black}{solu\c{c}\~{a}o da RR} $\Longrightarrow$\parbox[t]{15cm}{ constante \\
            (erro de arredondamento).}
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{Exemplo de RR}

\begin{itemize}
 \item Algoritmo de pesquisa bin\'{a}ria (por $x$) em lista ordenada:
 
       \begin{tabbing}
        {\bf se} x\={\bf se} x\= \kill
        {\bf se} a lista tem apenas 1 elemento {\bf ent\~{a}o} \\
                 \>compare $x$ com o elemento da lista; \\
                 \>retorne a resposta apropriada; \\
        {\bf sen\~{a}o} \\
                 \> seja $m$ o elemento do meio da lista; \\
                 \> {\bf se} $x < m$ {\bf ent\~{a}o} \\
                 \>          \>chame o algoritmo recursivamente na
                               $1^{\underline{a}}$ metade; \\
                 \> {\bf sen\~{a}o} \\
                 \>          \>chame o algoritmo recursivamente na
                               $2^{\underline{a}}$ metade; \\
                 \> {\bf fim} \\
        {\bf fim}
       \end{tabbing}
%--------------------------------------------------------------------------------------------

%\newslide{RELAÇÕES DE RECORRÊNCIA (6)}
%\hypertarget{relacoes-recorrencia-6}{}
       
%       $a_n$, o n\'{u}mero de compara\c{c}\~{o}es para lista de $n=2^k$ elementos:

N\'umero de compara\c{c}\~oes:  ???

\end{itemize}

%--------------------------------------------------------------------------------------------
\newslide{Exemplo de RR}

\begin{itemize}
 \item Algoritmo de pesquisa bin\'{a}ria (por $x$) em lista ordenada:
 
       \begin{tabbing}
        {\bf se} x\={\bf se} x\= \kill
        {\bf se} a lista tem apenas 1 elemento {\bf ent\~{a}o} \\
                 \>compare $x$ com o elemento da lista; \\
                 \>retorne a resposta apropriada; \\
        {\bf sen\~{a}o} \\
                 \> seja $m$ o elemento do meio da lista; \\
                 \> {\bf se} $x < m$ {\bf ent\~{a}o} \\
                 \>          \>chame o algoritmo recursivamente na
                               $1^{\underline{a}}$ metade; \\
                 \> {\bf sen\~{a}o} \\
                 \>          \>chame o algoritmo recursivamente na
                               $2^{\underline{a}}$ metade; \\
                 \> {\bf fim} \\
        {\bf fim}
       \end{tabbing}
%--------------------------------------------------------------------------------------------

%\newslide{RELAÇÕES DE RECORRÊNCIA (6)}
%\hypertarget{relacoes-recorrencia-6}{}
       
%       $a_n$, o n\'{u}mero de compara\c{c}\~{o}es para lista de $n=2^k$ elementos:

N\'umero de compara\c{c}\~oes:   $a_1=1; a_n=a_{n/2}+1 \mbox{ para } n\geq 2$.

\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{Exemplo de RR}

\begin{itemize}
\item RR para o n\'{u}mero de sequ\^{e}ncias bin\'{a}rias de $n$ d\'{\i}gitos sem 1's
      consecutivos:

      \begin{center}
      \begin{tabular}{cccccc}
      $n$:& 0 & 1 & 2 & 3 & 4 \\ \hline
          &   & 0 & 0\textcolor{black}{0} & 00\textcolor{black}{0} & 000\textcolor{black}{0} \\
          &   & 1 & 1\textcolor{black}{0} & 10\textcolor{black}{0} & 100\textcolor{black}{0} \\
          &   &   & \textcolor{black}{01} & 01\textcolor{black}{0} & 010\textcolor{black}{0} \\
          &   &   &          & 0\textcolor{black}{01} & 001\textcolor{black}{0} \\
          &   &   &          & 1\textcolor{black}{01} & 101\textcolor{black}{0} \\
          &   &   &          &           & 00\textcolor{black}{01} \\
          &   &   &          &           & 10\textcolor{black}{01} \\
          &   &   &          &           & 01\textcolor{black}{01} \\
    $a_n$:& 1 & 2 & 3        &  5        &  8
      \end{tabular}
      \end{center}

\textcolor{black}{RR:} ???
\end{itemize}
%--------------------------------------------------------------------------------------------

\newslide{Exemplo de RR}

\begin{itemize}
\item RR para o n\'{u}mero de sequ\^{e}ncias bin\'{a}rias de $n$ d\'{\i}gitos sem 1's
      consecutivos:

      \begin{center}
      \begin{tabular}{cccccc}
      $n$:& 0 & 1 & 2 & 3 & 4 \\ \hline
          &   & 0 & 0\textcolor{black}{0} & 00\textcolor{black}{0} & 000\textcolor{black}{0} \\
          &   & 1 & 1\textcolor{black}{0} & 10\textcolor{black}{0} & 100\textcolor{black}{0} \\
          &   &   & \textcolor{black}{01} & 01\textcolor{black}{0} & 010\textcolor{black}{0} \\
          &   &   &          & 0\textcolor{black}{01} & 001\textcolor{black}{0} \\
          &   &   &          & 1\textcolor{black}{01} & 101\textcolor{black}{0} \\
          &   &   &          &           & 00\textcolor{black}{01} \\
          &   &   &          &           & 10\textcolor{black}{01} \\
          &   &   &          &           & 01\textcolor{black}{01} \\
    $a_n$:& 1 & 2 & 3        &  5        &  8
      \end{tabular}
      \end{center}

\textcolor{black}{RR:} $a_0=1, a_1=2; a_n=a_{n-1}+a_{n-2} \mbox{ para } n\geq 2$.
\end{itemize}
%--------------------------------------------------------------------------------------------

\newslide{Exemplo de RR}

\begin{itemize}
\item RR para o n\'{u}mero de regi\~{o}es em que o plano \'{e} dividido por $n$ retas, se
      h\'{a} interse\c{c}\~{a}o entre cada par de retas, mas n\~{a}o h\'{a} interse\c{c}\~{a}o de mais de 2
      retas em um \'{u}nico ponto:
      
      \begin{picture}(400,160)
       \put(10,140){\makebox(0,0){$n$:}}
       \put(50,140){\makebox(0,0){0}}
       \put(130,140){\makebox(0,0){1}}
       \put(230,140){\makebox(0,0){2}}
       \put(370,140){\makebox(0,0){3}}
       
       \put(10,0){\makebox(0,0){$a_n$:}}
       \put(50,0){\makebox(0,0){1}}
       \put(130,0){\makebox(0,0){2}}
       \put(230,0){\makebox(0,0){4}}
       \put(370,0){\makebox(0,0){7}}
       
       \put(50,80){\circle{20}}
       \put(50,80){\makebox(0,0){1}}
       
       \put(130,40){\line(0,1){80}}
       \put(110,80){\circle{20}}
       \put(110,80){\makebox(0,0){1}}
       \put(150,80){\circle{20}}
       \put(150,80){\makebox(0,0){2}}
       
       \put(230,40){\line(0,1){80}}
       \put(210,100){\circle{20}}
       \put(210,100){\makebox(0,0){1}}
       \put(250,100){\circle{20}}
       \put(250,100){\makebox(0,0){2}}
       \put(190,80){\line(1,0){80}}
       \put(210,60){\circle{20}}
       \put(210,60){\makebox(0,0){4}}
       \put(250,60){\circle{20}}
       \put(250,60){\makebox(0,0){3}}
       
       \put(370,80){\circle{20}}
       \put(370,80){\makebox(0,0){7}}
       \put(300,110){\circle{20}}
       \put(300,110){\makebox(0,0){1}}
       \put(370,110){\circle{20}}
       \put(370,110){\makebox(0,0){2}}
       \put(440,110){\circle{20}}
       \put(440,110){\makebox(0,0){3}}
       \put(410,60){\circle{20}}
       \put(410,60){\makebox(0,0){4}}
       \put(370,30){\circle{20}}
       \put(370,30){\makebox(0,0){5}}
       \put(330,60){\circle{20}}
       \put(330,60){\makebox(0,0){6}}
       \put(300,95){\line(1,0){140}}
       \put(335,95){\makebox(0,0){$\bullet$}}
       \put(405,95){\makebox(0,0){$\bullet$}}
       \put(320,110){\line(1,-1){80}}
       \put(420,110){\line(-1,-1){80}}
      \end{picture}

\vspace*{5mm}
\textcolor{black}{RR:} ???

\end{itemize}
%--------------------------------------------------------------------------------------------

\newslide{Exemplo de RR}

\begin{itemize}
\item RR para o n\'{u}mero de regi\~{o}es em que o plano \'{e} dividido por $n$ retas, se
      h\'{a} interse\c{c}\~{a}o entre cada par de retas, mas n\~{a}o h\'{a} interse\c{c}\~{a}o de mais de 2
      retas em um \'{u}nico ponto:
      
      \begin{picture}(400,160)
       \put(10,140){\makebox(0,0){$n$:}}
       \put(50,140){\makebox(0,0){0}}
       \put(130,140){\makebox(0,0){1}}
       \put(230,140){\makebox(0,0){2}}
       \put(370,140){\makebox(0,0){3}}
       
       \put(10,0){\makebox(0,0){$a_n$:}}
       \put(50,0){\makebox(0,0){1}}
       \put(130,0){\makebox(0,0){2}}
       \put(230,0){\makebox(0,0){4}}
       \put(370,0){\makebox(0,0){7}}
       
       \put(50,80){\circle{20}}
       \put(50,80){\makebox(0,0){1}}
       
       \put(130,40){\line(0,1){80}}
       \put(110,80){\circle{20}}
       \put(110,80){\makebox(0,0){1}}
       \put(150,80){\circle{20}}
       \put(150,80){\makebox(0,0){2}}
       
       \put(230,40){\line(0,1){80}}
       \put(210,100){\circle{20}}
       \put(210,100){\makebox(0,0){1}}
       \put(250,100){\circle{20}}
       \put(250,100){\makebox(0,0){2}}
       \put(190,80){\line(1,0){80}}
       \put(210,60){\circle{20}}
       \put(210,60){\makebox(0,0){4}}
       \put(250,60){\circle{20}}
       \put(250,60){\makebox(0,0){3}}
       
       \put(370,80){\circle{20}}
       \put(370,80){\makebox(0,0){7}}
       \put(300,110){\circle{20}}
       \put(300,110){\makebox(0,0){1}}
       \put(370,110){\circle{20}}
       \put(370,110){\makebox(0,0){2}}
       \put(440,110){\circle{20}}
       \put(440,110){\makebox(0,0){3}}
       \put(410,60){\circle{20}}
       \put(410,60){\makebox(0,0){4}}
       \put(370,30){\circle{20}}
       \put(370,30){\makebox(0,0){5}}
       \put(330,60){\circle{20}}
       \put(330,60){\makebox(0,0){6}}
       \put(300,95){\line(1,0){140}}
       \put(335,95){\makebox(0,0){$\bullet$}}
       \put(405,95){\makebox(0,0){$\bullet$}}
       \put(320,110){\line(1,-1){80}}
       \put(420,110){\line(-1,-1){80}}
      \end{picture}

\vspace*{5mm}
\textcolor{black}{RR:} $a_0=1; a_n=a_{n-1}+n \mbox{ para } n\geq 1$.

\end{itemize}
%--------------------------------------------------------------------------------------------

\newslide{Exemplo de RR}

\begin{itemize}
\item Um experimento \'{e} executado lan\c{c}ando-se um dado at\'{e} que apare\c{c}am 2 n\'{u}meros
      pares. Determine uma RR para o n\'{u}mero de experimentos que terminam no
      $n$-\'{e}simo lan\c{c}amento, ou antes.

      \textcolor{black}{RR:} ???
\end{itemize}
%--------------------------------------------------------------------------------------------

\newslide{Exemplo de RR}

\begin{itemize}
\item Um experimento \'{e} executado lan\c{c}ando-se um dado at\'{e} que apare\c{c}am 2 n\'{u}meros
      pares. Determine uma RR para o n\'{u}mero de experimentos que terminam no
      $n$-\'{e}simo lan\c{c}amento, ou antes.
      
      \vspace*{5mm}
      \begin{description}
       \item[$a_{n-1}$:] n\'{u}mero de experimentos que terminam antes do
                $n$-\'{e}simo lan\c{c}amento;
       \item[$n-1$:] n\'{u}mero de escolhas para o lan\c{c}amento que deu n\'{u}mero par
                antes do $n$-\'{e}simo lan\c{c}amento;
       \item[$3$:] n\'{u}mero de escolhas para tal n\'{u}mero par;
       \item[$3^{n-2}$:] n\'{u}mero de escolhas para os n\'{u}meros \'{\i}mpares;
       \item[$3$:] n\'{u}mero de escolhas para o n\'{u}mero par do $n$-\'{e}simo
                lan\-\c{c}a\-men\-to.
      \end{description}
      
      \textcolor{black}{RR:} $a_0=0, a_1=0; a_n=a_{n-1}+(n-1)\times 3^n \mbox{ para } n\geq 2$.
\end{itemize}
%--------------------------------------------------------------------------------------------

\newslide{Exemplo de RR}

\begin{itemize}
\item RR para o n\'{u}mero de maneiras de ``completar com par\^{e}nteses''
      (em ingl\^{e}s, {\it fully parenthesize\/}) uma express\~{a}o
      
      \[w_1+w_2+\cdots+w_n\mbox{.}\]
      
      \vspace*{3mm}
      \begin{center}
      \begin{tabular}{cccccc}
       $n$:& 0 & 1 & 2 & 3 & 4 \\ \hline
           &   & $w_1$ & $(w_1+w_3)$ & $((w_1+w_2)+w_3)$ &
                                                      $(((w_1+w_2)+w_3)+w_4)$ \\
           &   &       &             & $(w_1+(w_2+w_3))$ &
                                                      $((w_1+(w_2+w_3))+w_4)$ \\
           &   &       &             &              & $((w_1+w_2)+(w_3+w_4))$ \\
           &   &       &             &              & $(w_1+(w_2+(w_3+w_4)))$ \\
           &   &       &             &              & $(w_1+((w_2+w_3)+w_4))$ \\
     $a_n$:& 0 & 1 & 1 &  2 & 5
      \end{tabular}
      \end{center}
      
%--------------------------------------------------------------------------------------------

\newslide{Exemplo (continua\c{c}\~ao)} 

      Para colocar par\^{e}ntesis em $w_1+w_2+\cdots+w_n$, para $n\geq 2$,
      fazer para $r$ de 1 a $n-1$:
      
      \begin{enumerate}
       \item[.] colocar par\^{e}ntesis em $w_1+\cdots+w_r$, obtendo $E_1$;
       \item[.] colocar par\^{e}ntesis em $w_{r+1}+\cdots+w_n$, obtendo $E_2$;
       \item[.] obter $(E_1+E_2)$.
      \end{enumerate}
      
      \vspace*{3mm}
      \textcolor{black}{RR:}
       $a_0=0, a_1=1; a_n=\sum_{k=1}^{n-1}a_ka_{n-k}\mbox{ para } n\geq 2$.         

%--------------------------------------------------------------------------------------------

\newslide{Exemplo de RR}

 \item O problema das permuta\c{c}\~{o}es ca\'{o}ticas.
 
       \begin{enumerate}
        \item[.] $D_0=1$, $D_1=0$.
        \item[.] Para $n\geq 2$, $x_n$ pode ficar nas posi\c{c}\~{o}es 1 a $n-1$.
        
              Suponha $x_n$ na posi\c{c}\~{a}o $i$:
              \begin{enumerate}
               \item[\ \ \ \ ] \underline{caso 1}: $x_i$ na posi\c{c}\~{a}o $n$:
                     $D_{n-2}$ permuta\c{c}\~{o}es para os elementos restantes.
               \item[\ \ \ \ ] \underline{caso 2}: $x_i$ fora da posi\c{c}\~{a}o $n$:
                     $D_{n-1}$ permuta\c{c}\~{o}es (\'{e} como se $x_n$ fosse retirado).
              \end{enumerate}
              
              Logo, $D_n=(n-1)(D_{n-1}+D_{n-2})$ para $n\geq 2$.
       \end{enumerate}
       
%--------------------------------------------------------------------------------------------

\newslide{Exemplo (continua\c{c}\~ao)}

       Simplificando:
       
       \begin{enumerate}
        \item[.] $D_n=(n-1)(D_{n-1}+D_{n-2})$ pode ser re-escrita assim:
              \[D_n-nD_{n-1}=-(D_{n-1}-(n-1)D_{n-2})\mbox{.}\]
        \item[.] Fazendo-se $a_n=D_n-nD_{n-1}$, tem-se:
              \[a_1=-1, a_n=-a_{n-1} \mbox{ para } n\geq 2\mbox{,}\]
              ou ainda,
              \[a_n=(-1)^n\mbox{.}\]
        \item[.] Logo,
        
              \[D_0=1, D_n=nD_{n-1}+(-1)^n \mbox{ para } n\geq 1\mbox{.}\]
       \end{enumerate}
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{Exemplos de RRs com mais de uma vari\'{a}vel}

\begin{itemize}
 \item RR para combina\c{c}\~{o}es:
       \[C(n,0)=C(n,n)=1, C(n,r)=C(n-1,r-1)+C(n-1,r)\mbox{.}\]
       
 \item RR para arranjos:
       \[P(n,0)=1, P(n,n)=n!, P(n,r)=rP(n-1,r-1)+P(n-1,r)\mbox{.}\]

%--------------------------------------------------------------------------------------------

\newslide{Exemplo de RRs simult\^aneas}

 \item RR's para o n\'{u}mero de sequ\^{e}ncias bin\'{a}rias de $n$ d\'{\i}gitos com:
       \begin{itemize}
        \item n\'{u}mero par de 0's e n\'{u}mero par de 1's ($a_n$);
        \item n\'{u}mero par de 0's e n\'{u}mero \'{\i}mpar de 1's ($b_n$);
        \item n\'{u}mero \'{\i}mpar de 0's e n\'{u}mero par de 1's ($c_n$); e
        \item n\'{u}mero \'{\i}mpar de 0's e n\'{u}mero \'{\i}mpar de 1's ($d_n$).
       \end{itemize}
       
       Sistema simult\^{a}neo de RR's:
       
       \begin{enumerate}
        \item[.] $a_0=1$, $b_0=c_0=d_0=0$;
        \item[.] $a_n=b_{n-1}+c_{n-1}$,
                  \newline
                 $b_n=a_{n-1}+d_{n-1}$,
                  \newline
                 $c_n=a_{n-1}+d_{n-1}$,
                  \newline
                 $d_n=b_{n-1}+c_{n-1}$, para $n\geq 1$.
       \end{enumerate}
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{RRs e somat\'orias}

\noindent RR's podem descrever somat\'{o}rias. Exemplos:
 
\begin{itemize}
 \item $1+2+\cdots+n$:
       \begin{quote}
        $a_1=1$; $a_n=a_{n-1}+n$ para $n\geq 2$.
       \end{quote}
 \item $2^0+2^1+2^2+\cdots+2^n$:
       \begin{quote}
        $a_0=1$; $a_n=a_{n-1}+2^n$ para $n\geq 1$.
       \end{quote}
\end{itemize}

%--------------------------------------------------------------------------------------------

\section{RR'S LINEARES COM COEFICIENTES CONSTANTES: DEFINIÇÕES}
\hypertarget{rr-definicoes-1}{}

\newslide{Defini\c{c}\~{o}es}

\vspace*{10mm}
\noindent Uma RR \textcolor{black}{linear de ordem} $r$ (de uma vari\'{a}vel) tem uma parte
recorrente da forma:

\[a_n+h_1(n)a_{n-1}+h_2(n)a_{n-2}+\cdots+h_r(n)a_{n-r}=f(n)\mbox{.}\]

%--------------------------------------------------------------------------------------------

\newslide{Defini\c{c}\~{o}es}

\noindent Observa\c{c}\~{o}es:

\vspace*{3mm}
\begin{itemize}
 \item se $f\equiv 0$ a RR \'{e} \textcolor{black}{homog\^{e}nea}.
 \item se $f\not\equiv 0$ a RR \'{e} \textcolor{black}{n\~{a}o-homog\^{e}nea}; neste caso:
 
       \begin{itemize}
        \item a \textcolor{black}{parte homog\^{e}nea} da RR \'{e}:
             \[a_n+h_1(n)a_{n-1}+h_2(n)a_{n-2}+\cdots+h_r(n)a_{n-r}=0\mbox{;}\]
        \item a \textcolor{black}{parte n\~{a}o-homog\^{e}nea} da RR \'{e} $f$.
       \end{itemize}
 \item se as fun\c{c}\~{o}es $h_i$ s\~{a}o constantes diz-se que a RR tem \textcolor{black}{coeficientes
       constantes}.
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{Exemplo}

\begin{itemize}
 \item $a_1=a_2=1$; $a_n=a_{n-1}+a_{n-2}$ para $n\geq 3$.

\vspace*{10mm} 
       RR linear homog\^{e}nea de ordem 2 com coeficientes constantes.

%--------------------------------------------------------------------------------------------

\newslide{Exemplo}

 \item $w_1=w_2=0$, $w_n=w_{n-1}+w_{n-2}+1$ para $n\geq 3$.
 
\vspace*{10mm} 
       RR linear n\~{a}o-homog\^{e}nea de ordem 2, com coeficientes constantes.
       \begin{itemize}
        \item parte homog\^{e}nea: $w_n=w_{n-1}+w_{n-2}$.
        \item parte n\~{a}o-homog\^{e}nea: $f(n)=1$.
       \end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{Exemplo}

 \item $a_1=0$, $a_n=a_{n/2}+1$ para $n=2^k$ ($k\geq 1$).
 
\vspace*{10mm} 
       RR n\~{a}o linear.

%--------------------------------------------------------------------------------------------

\newslide{Exemplo}

  \item $a_0=0, a_1=1$, $a_n=\sum_{k=1}^{n-1}a_ka_{n-k}$ para $n\geq 2$.
 
\vspace*{10mm} 
       RR n\~{a}o linear.

%--------------------------------------------------------------------------------------------

\newslide{Exemplo}

 \item $D_0=1$, $D_n=nD_{n-1}+(-1)^n$ para $n\geq 1$.
 
\vspace*{10mm} 
       RR linear n\~{a}o-homog\^{e}nea de ordem 1, com coeficientes n\~{a}o constantes.

%--------------------------------------------------------------------------------------------

\newslide{Exemplo}

 \item $C(n,0)=C(n,n)=1$, $C(n,r)=C(n-1,r-1)+C(n-1,r)$.
 
\vspace*{10mm} 
       N\~{a}o \'{e} RR de uma vari\'{a}vel.
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{RR bem definida}

\noindent Uma RR linear de ordem $r$ \textcolor{black}{bem definida} consiste de:

\begin{itemize}
 \item parte recorrente; e
 \item $r$ condi\c{c}\~{o}es iniciais, para $r$ valores consecutivos.
\end{itemize}

%--------------------------------------------------------------------------------------------

\section{RR'S LINEARES COM COEFICIENTES CONSTANTES: SOLUÇÃO}
\hypertarget{rr-solucao-1}{}

\vspace*{10mm}
\begin{itemize}
 \item T\'{e}cnicas similares \`{a}s de resolu\c{c}\~{a}o de equa\c{c}\~{o}es diferenciais ordin\'{a}rias.
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{Um exemplo}

\noindent Seja uma RR \textcolor{black}{linear de ordem $r$ com coeficientes constantes}.
\underline{Exemplo}: $a_0=2$, $a_1=5$, $a_n-5a_{n-1}+6a_{n-2}=0 \,\,\, (n\geq 2)$.

\vspace*{7mm} 
\noindent {\bf Estrat\'{e}gia:}

\begin{enumerate}
 \item Encontrar uma {\bf solu\c{c}\~{a}o geral para a parte recorrente}, com $r$
       constantes arbitr\'{a}rias $C_1$, $C_2$, \ldots, $C_r$.

       \vspace*{3mm}
       \underline{Exemplo}: $C_12^n+C_23^n$

\newslide{Continua\c{c}\~ao do exemplo}

 \item Resolver um sistema de $r$ equa\c{c}\~{o}es simult\^{a}neas --- uma equa\c{c}\~{a}o para cada
       condi\c{c}\~{a}o inicial --- com $r$ inc\'{o}gnitas --- os $C_i$'s.

       \vspace*{3mm}
       \underline{Exemplo}: $\begin{array}[t]{l}
                             C_12^0+C_23^0=a_0=2 \\
                             C_12^1+C_23^1=a_1=5 \\
                             \\
                             \mbox{Solu\c{c}\~{a}o do sistema: } C_1=1, C_2=1\mbox{.} \\
                             \\
                             \mbox{Solu\c{c}\~{a}o da RR: } 2^n+3^n\mbox{.}
                            \end{array} $
\end{enumerate}

%--------------------------------------------------------------------------------------------

\newslide{Princ\'{\i}pio da Superposi\c{c}\~{a}o}

      Se $g_1(n)$ \'{e} solu\c{c}\~{a}o de \[a_n+c_1a_{n-1}+\cdots+c_ra_{n-r}=f_1(n)\] e
         $g_2(n)$ \'{e} solu\c{c}\~{a}o de
         \[a_n+c_1a_{n-1}+\cdots+c_ra_{n-r}=f_2(n)\mbox{,}\]
      ent\~{a}o
      $C_1g_1(n)+C_2g_2(n)$ \'{e} solu\c{c}\~{a}o de \[a_n+c_1a_{n-1}+\cdots+c_ra_{n-r}=
      C_1f_1(n)+C_2f_2(n)\mbox{,}\] para quaisquer constantes $C_1$ e $C_2$.

%--------------------------------------------------------------------------------------------

\newslide{Corol\'ario do Princ\'{\i}pio da Superposi\c{c}\~{a}o}

      Se $g_1(n)$, $g_2(n)$, \ldots, $g_r(n)$ s\~{a}o solu\c{c}\~{o}es de
         \[a_n+c_1a_{n-1}+\cdots+c_ra_{n-r}=0\mbox{,}\] ent\~{a}o
      $C_1g_1(n)+C_2g_2(n)+\cdots+C_rg_r(n)$ tamb\'{e}m \'{e} \\
      para quaisquer constantes $C_1$, $C_2$, \ldots, $C_r$.

\vspace*{10mm}
$\Longrightarrow$ Como encontrar $r$ $g_i$'s?

\vspace*{5mm}
\begin{itemize}
 \item \textcolor{black}{Procurar solu\c{c}\~{o}es da forma $\alpha^n$, para algum n\'{u}mero
       $\alpha$}.
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{Dois exemplos}

\begin{itemize}
 \item $a_n=3a_{n-1}$ tem a solu\c{c}\~{a}o geral $C_13^n$.

 \item $a_0=2$, $a_1=5$, $a_n-5a_{n-1}+6a_{n-2}=0$ para $n\geq 2$.
 
       Seja a fun\c{c}\~{a}o geradora $g(x)=\sum_{n=0}^{\infty}a_nx^n$.
       \begin{itemize}
        \item Multiplicando ambos os lados da parte recorrente por $x^n$:
             \[a_nx^n-5a_{n-1}x^n+6a_{n-2}x^n=0 \,\,\,(n \geq 2)\mbox{.}\]
        \item Somando ambos os lados a partir de $n=2$:
              \[\sum_{n=2}^\infty a_nx^n-5\sum_{n=2}^\infty
                a_{n-1}x^n+6\sum_{n=2}^\infty a_{n-2}x^n=0\mbox{.}\]
                
%--------------------------------------------------------------------------------------------

\newslide{Continuação do exemplo}
                
        \item Mas,
              \begin{itemize}
               \item $\sum_{n=2}^\infty a_nx^n=g(x)-a_1x-a_0$,
               \item $\sum_{n=2}^\infty a_{n-1}x^n=x(g(x)-a_0)$, e
               \item $\sum_{n=2}^\infty a_{n-2}x^n=x^2g(x)$.
              \end{itemize}
        \item Assim, $g(x)-a_1x-a_0-5xg(x)+5a_0x+6x^2g(x)=0$
              ou seja,
              \[g(x)=\frac{a_0+a_1x-5a_0x}{6x^2-5x+1}=
                     \frac{2-5x}{(3x-1)(2x-1)}\]
              ou ainda,
              \[g(x)=\frac{1}{1-2x}+\frac{1}{(1-3x)}\mbox{.}\]
        \item Lembrando que $1/(1-z)=1+z+z^2+\cdots$, conclui-se que
              \[a_n=2^n+3^n\mbox{.}\]
       \end{itemize}
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{Conclusão do exemplo}

\noindent Em geral, solu\c{c}\~{o}es da forma $\alpha^n$ s\~{a}o produzidas porque a
decomposi\c{c}\~{a}o em fra\c{c}\~{o}es parciais cont\'{e}m termos da forma

\[\frac{C}{1-\alpha x}=C(1+\alpha x+\alpha^2x^2+\cdots)\mbox{.}\]

\noindent Se $\alpha^n$ \'{e} solu\c{c}\~{a}o para a parte recorrente, ent\~{a}o:

\[\alpha^n+c_1\alpha^{n-1}+\cdots+c_r\alpha^{n-r}=0\mbox{.}\]

\noindent Dividindo por $\alpha^{n-r}$, tem-se a {\bf equa\c{c}\~{a}o caracter\'{\i}stica} da
RR:
\[\alpha^r+c_1\alpha^{r-1}+\cdots+c_r=0\mbox{.}\]

\noindent Se a equa\c{c}\~{a}o caracter\'{\i}stica tem $r$ ra\'{\i}zes diferentes $\alpha_1$,
\ldots, $\alpha_r$, ent\~{a}o tem-se $r$ solu\c{c}\~{o}es $\alpha_1^n$, \ldots,
$\alpha_r^n$. Pelo princ\'{\i}pio da superposi\c{c}\~{a}o,

\[C_1\alpha_1^n+C_2\alpha_2^n+\cdots+C_r\alpha_r^n\]

\noindent \'{e} tamb\'{e}m uma solu\c{c}\~{a}o para a parte recorrente.

%--------------------------------------------------------------------------------------------

\newslide{Exemplo}

\begin{itemize}
 \item $a_0=3, a_1=-3$, $a_n+a_{n-1}-2a_{n-2}=0$ para $n\geq 2$.
 
       \begin{itemize}
        \item equa\c{c}\~{a}o caracter\'{\i}stica: $\alpha^2+\alpha-2=0$;
        \item ra\'{\i}zes: $\alpha_1=1$, $\alpha_2=-2$;
        \item solu\c{c}\~{a}o geral: $C_11^n+C_2(-2)^n$;
        \item para satisfazer as condi\c{c}\~{o}es iniciais, deve-se ter:
        
              $\begin{array}{ll}
                \ \ \ \ & C_11^0+C_2(-2)^0=a_0=3 \\
                \ \ \ \ & C_11^1+C_2(-2)^1=a_1=-3 \\
              \end{array}$
              
              o que d\'{a}: $C_1=1$ e $C_2=2$.
        \item solu\c{c}\~{a}o da RR: \framebox{$a_n=1+2(-2)^n$}
       \end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{Exemplo}

 \item $a_1=0, a_2=1$, $a_n+a_{n-2}=0$ para $n\geq 3$.
 
       \begin{itemize}
        \item equa\c{c}\~{a}o caracter\'{\i}stica: $\alpha^2+1=0$;
        \item ra\'{\i}zes: $\alpha_1=i$, $\alpha_2=-i$;
        \item solu\c{c}\~{a}o geral: $C_1i^n+C_2(-i)^n$;
        \item para satisfazer as condi\c{c}\~{o}es iniciais, deve-se ter:
        
              $\begin{array}{ll}
                \ \ \ \ & C_1i^1+C_2(-i)^1=a_1=0 \\
                \ \ \ \ & C_1i^2+C_2(-i)^2=a_2=1 \\
              \end{array}$
              
              o que d\'{a}: $C_1=-1/2$ e $C_2=-1/2$.
        \item solu\c{c}\~{a}o da RR: \framebox{$a_n=-[i^n/2+(-i)^n/2]$}
       \end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{Exemplo}

 \item $a_1=10, a_2=18, a_3=70$, $a_n-3a_{n-1}-4a_{n-2}+12a_{n-3}=0$ para
       $n\geq 4$.
 
       \begin{itemize}
        \item equa\c{c}\~{a}o caracter\'{\i}stica: $\alpha^3-3\alpha^2-4\alpha+12=0$;
        \item ra\'{\i}zes: $\alpha_1=2$, $\alpha_2=-2$, $\alpha_3=3$;
        \item solu\c{c}\~{a}o geral: $C_12^n+C_2(-2)^n+C_33^n$;
        \item para satisfazer as condi\c{c}\~{o}es iniciais, deve-se ter:
        
              \vspace*{3mm}
              $\begin{array}{ll}
                \ \ \ \ & C_12^1+C_2(-2)^1+C_33^1=a_1=10 \\
                \ \ \ \ & C_12^2+C_2(-2)^2+C_33^2=a_2=18 \\
                \ \ \ \ & C_12^3+C_2(-2)^3+C_33^3=a_3=70 \\
              \end{array}$
              
              \vspace*{3mm}
              ou seja: $C_1=1$, $C_2=-1$ e $C_3=2$.
        \item solu\c{c}\~{a}o da RR: \framebox{$a_n=2^n-(-2)^n+2(3^n)$}
       \end{itemize}

\end{itemize}

%--------------------------------------------------------------------------------------------

%\newslide{Equação característica com raízes idênticas}

%\begin{itemize}
%\item $a_0=1, a_1=6$, $a_n-6a_{n-1}+9a_{n-2}=0$ para $n\geq 2$.
% 
%       Seja a fun\c{c}\~{a}o geradora $g(x)=\sum_{n=0}^{\infty}a_nx^n$.
%       \begin{itemize}
%        \item Fazendo-se as manipula\c{c}\~{o}es usuais, tem-se:
%              \[g(x)=\frac{a_0+a_1x-6a_0x}{9x^2-6x+1}=
%                     \frac{1}{(3x-1)^2}\mbox{.}\]
%        \item \underline{Observa\c{c}\~{a}o}:
%              \begin{itemize}
%               \item equa\c{c}\~{a}o caracter\'{\i}stica: $\alpha^2-6\alpha+9=0$;
%               \item denominador da fun\c{c}\~{a}o geradora: $9x^2-6x+1$.
%              \end{itemize}

%--------------------------------------------------------------------------------------------

%\newslide{RR'S LINEARES COM COEFICIENTES CONSTANTES: SOLUÇÃO (18)}
%\hypertarget{rr-solucao-18}{}              
              
%        \item \underline{Pode-se provar que}:
%              \begin{itemize}
%               \item se a equa\c{c}\~{a}o caracter\'{\i}stica \'{e} $\alpha^2+c_1\alpha+c_2=0$, o
%                     denominador da fun\c{c}\~{a}o geradora \'{e} $c_2x^2+c_1x+1$.
%               \item se uma equa\c{c}\~{a}o tem raiz dupla, a outra tamb\'{e}m tem.
%              \end{itemize}
%        \item Decompondo a fun\c{c}\~{a}o geradora:
%              \[g(x)=\frac{1}{1-3x}+\frac{3x}{(1-3x)^2}\mbox{.}\]
        
%        \item Lembrando que \[\frac{1}{1-z}=1+z+z^2+\cdots,\]
%              chega-se a
%              \[g(x)=(1+0)+(3+1(3))x+(9+2(9))x^2+\cdots+(3^n+n3^n)x^n+
%              \cdots\mbox{.}\]
              
%--------------------------------------------------------------------------------------------

%\newslide{RR'S LINEARES COM COEFICIENTES CONSTANTES: SOLUÇÃO (19)}
%\hypertarget{rr-solucao-19}{}
              
%              Logo,
%              \[a_n=3^n+n3^n\mbox{.}\]
%       \end{itemize}
 
%\end{itemize}

%--------------------------------------------------------------------------------------------

%\newslide{RR'S LINEARES COM COEFICIENTES CONSTANTES: SOLUÇÃO (20)}
%\hypertarget{rr-solucao-20}{}

%\noindent \underline{Importante}:

%\vspace*{10mm}
%\begin{itemize}
% \item Se a fun\c{c}\~{a}o geradora tem um fator \[(x-\alpha_i)^m\]  no denominador,
%       a decomposi\c{c}\~{a}o em fra\c{c}\~{o}es parciais cont\'{e}m termos cujos denominadores
%       s\~{a}o: \[(x-\alpha_i), (x-\alpha_i)^2, \ldots, (x-\alpha_i)^m\mbox{.}\]
%       Tais termos contribuem, respectivamente, com solu\c{c}\~{o}es das formas
%       \[\alpha_i^n, n\alpha_i^n, n^2\alpha_i^n, \ldots,
%        n^{m-1}\alpha_i^n\mbox{.}\]
        
% \item Coerentemente, se a equa\c{c}\~{a}o caracter\'{\i}stica tem uma raiz $\alpha_i$ de
%       {\bf multiplicidade} $m$, ent\~{a}o ela contribue com $m$ solu\c{c}\~{o}es:
%       \[\alpha_i^n, n\alpha_i^n, n^2\alpha_i^n, \ldots,
%        n^{m-1}\alpha_i^n\mbox{.}\]
%\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{Equação característica com raízes idênticas}

\vspace*{10mm}
\noindent Se a equa\c{c}\~{a}o caracter\'{\i}stica tem uma raiz $\alpha_i$ de
       {\bf multiplicidade} $m$, ent\~{a}o ela contribue com $m$ solu\c{c}\~{o}es:
       \[\alpha_i^n, n\alpha_i^n, n^2\alpha_i^n, \ldots,
        n^{m-1}\alpha_i^n\mbox{.}\]

\newslide{Exemplo}

\begin{itemize}
 \item $a_1=3, a_2=11, a_3=29$, $a_n-7a_{n-1}+16a_{n-2}-12a_{n-3}=0$ para
       $n\geq 4$.
 
       \begin{itemize}
        \item equa\c{c}\~{a}o caracter\'{\i}stica: $\alpha^3-7\alpha^2+16\alpha-12=0$;
        \item ra\'{\i}zes: $\alpha_1=2$, de multiplicidade 2, e $\alpha_2=3$;
        \item solu\c{c}\~{a}o geral: $C_12^n+C_2n2^n+C_33^n$;
        \item para satisfazer as condi\c{c}\~{o}es iniciais, deve-se ter:
              $C_1=1$, $C_2=2$ e $C_3=-1$.
        \item solu\c{c}\~{a}o da RR: \framebox{$a_n=2^n+n2^{n+1}-3^n$}
       \end{itemize}
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{RRs lineares N\~{a}o-homog\^{e}neas com coeficientes constantes}

\noindent Pelo princ\'{\i}pio da superposi\c{c}\~{a}o, se $g(n)$ \'{e} a solu\c{c}\~{a}o geral para a
parte homog\^{e}nea

\[a_n+c_1a_{n-1}+\cdots+c_ra_{n-r}=0,\]

\noindent e se $p(n)$ \'{e} alguma solu\c{c}\~{a}o da parte recorrente

\[a_n+c_1a_{n-1}+\cdots+c_ra_{n-r}=f(n),\]

\noindent ent\~{a}o $g(n)+p(n)$ tamb\'{e}m \'{e} solu\c{c}\~{a}o da parte recorrente. Como
$g(n)+p(n)$ tem $r$ constantes, \'{e} a {\bf solu\c{c}\~{a}o geral da parte recorrente}.

\vspace*{10mm}
\noindent $\Longrightarrow$ N\~{a}o existe um m\'{e}todo geral para determinar $p(n)$.

%--------------------------------------------------------------------------------------------

\newslide{RRs lineares N\~{a}o-homog\^{e}neas com coeficientes constantes}

\begin{description}
 \item[\textcolor{black}{Caso 1:} $f(n)$ \'{e} polin\^{o}mio] \
 
      $p(n)$ \'{e} um polin\^{o}mio cuja ordem \'{e} a ordem de $f(n)$ somada com a
      multiplicidade de 1 na equa\c{c}\~{a}o carater\'{\i}stica.
\end{description}

%--------------------------------------------------------------------------------------------

\newslide{Exemplo}

\begin{itemize}
 \item $a_1=-4$, $a_n+3a_{n-1}=4n^2-2n$ para $n\geq 2$.
 
       \begin{itemize}
        \item solu\c{c}\~{a}o geral da parte homog\^{e}nea $a_n+3a_{n-1}=0$:
              \[g(n)=C_1(-3)^n\mbox{.}\]
        \item $p(n)$ \'{e} polin\^{o}mio de ordem 2, $An^2+Bn+C$:
        
              \begin{itemize}
               \item $[An^2+Bn+C]+3[A(n-1)^2+B(n-1)+C]=4n^2-2n$;
               \item desenvolvendo, tem-se:

                     \vspace*{2mm}               
                     $\begin{array}{lr}
                       \ \ \ \ & 4A=4 \\
                       \ \ \ \ & 4B-6A=-2 \\
                       \ \ \ \ & 3A-3B+4C=0 \\
                      \end{array}$
                      
                     \vspace*{2mm}
                     cuja solu\c{c}\~{a}o \'{e}: $A=1$, $B=1$, $C=0$;
                     
               \item portanto, tem-se: \[p(n)=n^2+n\mbox{.}\]
              \end{itemize}
                   
%--------------------------------------------------------------------------------------------

\newslide{Exemplo (continuação)}                    

        \item solu\c{c}\~{a}o geral da parte recorrente:
             \[g(n)+p(n)= C_1(-3)^n+n^2+n\mbox{.}\]          
        \item para satisfazer a condi\c{c}\~{a}o inicial, deve-se ter:
        
              $\begin{array}{ll}
                \ \ \ \ & C_1(-3)^1+1^2+1=a_1=-4 \\
              \end{array}$
              
              o que d\'{a}: $C_1=2$.
        \item solu\c{c}\~{a}o da RR: \framebox{$a_n=2(-3)^n+n^2+n$}
       \end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{Exemplo}

 \item $w_1=0, w_2=0$, $w_n=w_{n-1}+w_{n-2}+1$ para $n\geq 3$.
 
       \begin{itemize}
        \item solu\c{c}\~{a}o geral da parte homog\^{e}nea $w_n-w_{n-1}-w_{n-2}=0$:
              \[g(n)=C_1\left(\frac{1+\sqrt{5}}{2}\right)^n+
                     C_2\left(\frac{1-\sqrt{5}}{2}\right)^n\mbox{.}\]
        \item $p(n)$ \'{e} polin\^{o}mio de ordem 0, $A$:
        
              \begin{itemize}
               \item $A-A-A=1$; ou seja, $A=-1$;
               \item portanto, tem-se: \[p(n)=-1\mbox{.}\]
              \end{itemize}

        \item solu\c{c}\~{a}o geral da parte recorrente:
             \[g(n)+p(n)= C_1\left(\frac{1+\sqrt{5}}{2}\right)^n+
                     C_2\left(\frac{1-\sqrt{5}}{2}\right)^n-1\mbox{.}\]
                     
%--------------------------------------------------------------------------------------------

\newslide{Exemplo (continuação)}

        \item para satisfazer as condi\c{c}\~{o}es iniciais, deve-se ter:

              \vspace*{3mm}
              $\begin{array}{ll}
                \ \ \ \ & C_1\left(\frac{1+\sqrt{5}}{2}\right)^1+
                     C_2\left(\frac{1-\sqrt{5}}{2}\right)^1-1=a_1=0 \\
                \ \ \ \ & C_1\left(\frac{1+\sqrt{5}}{2}\right)^2+
                     C_2\left(\frac{1-\sqrt{5}}{2}\right)^2-1=a_2=0 \\
              \end{array}$
              
              \vspace*{3mm}
              o que d\'{a}: $C_1=1/\sqrt{5}, C_2=-1/\sqrt{5}$.
        \item solu\c{c}\~{a}o da RR: \framebox{$w_n=\frac{1}{\sqrt{5}}\left(
              \frac{1+\sqrt{5}}{2}\right)^n-\frac{1}{\sqrt{5}}\left(
              \frac{1-\sqrt{5}}{2}\right)^n-1$}
       \end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{Exemplo}

 \item $a_0=1$, $a_n=a_{n-1}+n$ para $n\geq 1$.
 
       \begin{itemize}
        \item solu\c{c}\~{a}o geral da parte homog\^{e}nea $a_n-a_{n-1}=0$:
              \[g(n)=C_1(1)^n=C_1\mbox{.}\]
        \item $p(n)$ \'{e} polin\^{o}mio de ordem 2, $An^2+Bn+C$:
        
              \begin{itemize}
               \item $[An^2+Bn+C]-[A(n-1)^2+B(n-1)+C]=n$;
               \item desenvolvendo, tem-se:
               
                     \vspace*{3mm}
                     $\begin{array}{lr}
                       \ \ \ \ & 2A=1 \\
                       \ \ \ \ & -A+B=0 \\
                      \end{array}$
                      
                     \vspace*{3mm}
                     cuja solu\c{c}\~{a}o \'{e}: $A=1/2$, $B=1/2$;
               \item portanto, tem-se: \[p(n)=n^2/2+n/2\mbox{.}\]
              \end{itemize}
              
%--------------------------------------------------------------------------------------------

\newslide{Exemplo (continuação)}

        \item solu\c{c}\~{a}o geral da parte recorrente:
             \[g(n)+p(n)= C_1+n^2/2+n/2\mbox{.}\]          
        \item para satisfazer a condi\c{c}\~{a}o inicial, deve-se ter:
        
              $\begin{array}{ll}
                \ \ \ \ & C_1+0^2/2+0/2=a_0=1 \\
              \end{array}$
              
              o que d\'{a}: $C_1=1$.
        \item solu\c{c}\~{a}o da RR: \framebox{$a_n=n^2/2+n/2+1$}
       \end{itemize}
       
\end{itemize}      

%--------------------------------------------------------------------------------------------

\newslide{RRs lineares N\~{a}o-homog\^{e}neas com coeficientes constantes}

\begin{description}
 \item[\textcolor{black}{Caso 2:} $f(n)$ \'{e} da forma $\alpha^n$] \
 
      $p(n)$ \'{e} $An^k\alpha^n$, para algum $A$, onde $k$ \'{e} a multiplicidade de
      $\alpha$ na equa\c{c}\~{a}o caracter\'{\i}stica.
\end{description}

%--------------------------------------------------------------------------------------------

\newslide{Exemplo}

\begin{itemize}
 \item Solu\c{c}\~{a}o geral para $a_n-4a_{n-1}+4a_{n-2}=2^n$.
 
       \begin{itemize}
        \item solu\c{c}\~{a}o geral da parte homog\^{e}nea $a_n-4a_{n-1}+4a_{n-2}=0$:
              \[g(n)=C_12^n+C_2n2^n\mbox{.}\]
        \item $p(n)$ \'{e} da forma $An^22^n$:
        
              \begin{itemize}
               \item $An^22^n-4A(n-1)^22^{n-1}+4A(n-2)^22^{n-2}=2^n$;
               \item desenvolvendo, tem-se: $A=1/2$;
               \item portanto, tem-se: \[p(n)=(1/2)n^22^n\mbox{.}\]
              \end{itemize}
        \item solu\c{c}\~{a}o geral da parte recorrente:
             \[g(n)+p(n)= C_12^n+C_2n2^n+n^22^{n-1}\mbox{.}\]          
       \end{itemize}
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{RRs lineares N\~{a}o-homog\^{e}neas com coeficientes constantes}

\vspace*{20mm}
\noindent O \textcolor{black}{princ\'{\i}pio da superposi\c{c}\~{a}o} pode ser usado para
\textcolor{black}{combinar os casos}.

%--------------------------------------------------------------------------------------------

\newslide{Combinação de casos: Exemplo}

\begin{itemize}
 \item Solu\c{c}\~{a}o geral para $a_n+3a_{n-1}=4n^2-2n+2^n$.
 
       \begin{itemize}
        \item solu\c{c}\~{a}o geral da parte homog\^{e}nea $a_n+3a_{n-1}=0$:
              \[g(n)=C_1(-3)^n\mbox{.}\]
        \item $p_1(n)$ para $a_n+3a_{n-1}=4n^2-2n$ \'{e}:
               \[p_1(n)=n^2+n\mbox{.}\]
        \item $p_2(n)$ para $a_n+3a_{n-1}=2^n$ \'{e}:
               \[p_2(n)=(2/5)2^n\mbox{.}\]
               
        \item pelo princ\'{\i}pio da superposi\c{c}\~{a}o, $p(n)$ para
              $a_n+3a_{n-1}=4n^2-2n+2^n$ \'{e}:
               \[p(n)=p_1(n)+p_2(n)=n^2+n+(2/5)2^n\mbox{.}\]
        \item solu\c{c}\~{a}o geral da parte recorrente:
             \[g(n)+p(n)= C_1(-3)^n+n^2+n+(2/5)2^n\mbox{.}\]          
       \end{itemize}
\end{itemize}      

%--------------------------------------------------------------------------------------------

\section{OUTRAS TÉCNICAS PARA RESOLUÇÃO DE RELAÇÕES DE RECORRÊNCIA}
\hypertarget{outras-tecnicas-1}{}

\newslide{Relação de recorrência linear de primeira ordem}

\[a_0=c, a_n=p(n)a_{n-1}+f(n)\mbox{.}\]

\vspace*{5mm}
\begin{description}
 \item[\textcolor{black}{Caso particular: $p(n)=1$}] \
 
  Neste caso,

  \[a_n=c+\sum_{k=1}^nf(k)\mbox{.}\]
  
  Basta usar a f\'{o}rmula fechada para a somat\'{o}ria.

\vspace*{5mm}
  \underline{Exemplo}:
  
  \begin{itemize}
   \item $a_0=1$, $a_n=a_{n-1}+n$ para $n\geq 1$.
 
       Evidentemente, \[a_n=1+\sum_{k=1}^nk=1+n(n+1)/2\mbox{.}\]
  \end{itemize}
\end{description}
%--------------------------------------------------------------------------------------------

\newslide{Relação de recorrência linear de primeira ordem}

\[a_0=c, a_n=p(n)a_{n-1}+f(n)\mbox{.}\]

\vspace*{5mm}
\begin{description}
 \item[\textcolor{black}{Caso geral: $p(n)$ qualquer}] \
 
  \begin{itemize}
   \item Solu\c{c}\~{a}o $u_n$ para a parte homog\^{e}nea $a_n=p(n)a_{n-1}$,
        supondo $u_0=1$:
        \[u_n=p(n)a_{n-1}=\cdots=p(n)p(n-1)\cdots p(1)\mbox{.}\]
   \item A solu\c{c}\~{a}o da RR ser\'{a} da forma \framebox{$u_nv_n$}. Logo, deve-se ter:
         \[v_0=a_0, \mbox{ e } (u_nv_n)=p(n)(u_{n-1}v_{n-1})+f(n)\mbox{.}\]
         Como $u_n=p(n)u_{n-1}$, a parte recorrente torna-se:
         \[u_nv_n=u_nv_{n-1}+f(n)\mbox{.}\]
         
%--------------------------------------------------------------------------------------------

\newslide{Caso geral (continuação)}

   \item Logo, basta fazer o seguinte:
         \begin{itemize}
          \item obter $u_n$;
          \item obter $v_n$, resolvendo
               \[v_0=a_0, v_n=v_{n-1}+f(n)/u_n \mbox{ para } n\geq 1\mbox{; e}\]
          \item multiplicar $u_n$ e $v_n$.
         \end{itemize}
  \end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{Exemplo}
 
   \begin{itemize}
    \item $a_1=1$, $a_n-\frac{n}{n-1}a_{n-1}=n^3$ para $n\geq 2$.
    
          \begin{itemize}
           \item $u_n=\frac{n}{n-1}\frac{n-1}{n-2}\cdots\frac{2}{1}1=n$.
           \item $v_1=a_1=1, v_n=v_{n-1}+n^3/u_n$ para $n\geq 2$, ou ainda:
                 \[v_1=1, v_n=v_{n-1}+n^2 \mbox{ para } n\geq 2\mbox{,}\]
                 cuja solu\c{c}\~{a}o \'{e}:
                 \[v_n=\sum_{k=1}^{n}k^2=n(n+1)(2n+1)/6\mbox{.}\]
           \item A solu\c{c}\~{a}o \'{e}, portanto: 
                 \[a_n=u_nv_n=n^2(n+1)(2n+1)/6\mbox{.}\]
          \end{itemize}      

%--------------------------------------------------------------------------------------------

\newslide{Exemplo}
   \item $D_0=1$, $D_n=nD_{n-1}+(-1)^n$ para $n\geq 1$.
    
          \begin{itemize}
           \item $u_n=n!$.
           \item $v_0=D_0=1, v_n=v_{n-1}+(-1)^n/u_n$ para $n\geq 1$, ou ainda:
                 \[v_0=1, v_n=v_{n-1}+(-1)^n/n! \mbox{ para } n\geq 1\mbox{,}\]
                 cuja solu\c{c}\~{a}o \'{e}:
                 \[v_n=1/2!-1/3!+\cdots+(-1)^n/n!\mbox{.}\]
           \item A solu\c{c}\~{a}o \'{e}, portanto: 
                 \[D_n=u_nv_n= n!(1/2!-1/3!+\cdots+(-1)^n/n!)\mbox{.}\]
          \end{itemize}
   \end{itemize}
 
\end{description}

%--------------------------------------------------------------------------------------------

%\newslide{OUTRAS TÉCNICAS PARA RESOLUÇÃO DE RR'S (7)}
%\hypertarget{outras-tecnicas-7}{}

%\noindent \underline{Uso de fun\c{c}\~{o}es geradoras para exemplos mais complexos}

%\vspace*{5mm}
%\begin{itemize}
% \item $a_0=0, a_1=1$, $a_n=\sum_{k=0}^{n}a_ka_{n-k}$ para $n\geq 2$.
 
%       \begin{itemize}
%        \item Seja $g(x)=\sum_{n=0}^{\infty}a_nx^n$, ou seja,
        
%              $\begin{array}{ll} 
%                g(x)=&a_0+a_1x+(a_0a_2+a_1a_1+a_2a_0)x^2+\cdots+ \\
%                     &(a_0a_n+a_1a_{n-1}+\cdots+a_na_0)x^n+\cdots
%               \end{array}$
%        \item Pela defini\c{c}\~{a}o de multiplica\c{c}\~{a}o de s\'{e}ries de pot\^{e}ncias,
%                     \[a_0a_n+a_1a_{n-1}+\cdots+a_na_0\]
%              \'{e} o coeficiente de $x^n$ em $g^2(x)$.
              
%--------------------------------------------------------------------------------------------

%\newslide{OUTRAS TÉCNICAS PARA RESOLUÇÃO DE RR'S (8)}
%\hypertarget{outras-tecnicas-8}{}
              
%        \item Logo, tem-se que
%              \[g(x)-a_0-a_1x=g^2(x)-a_0^2-(a_0a_1+a_1a_0)x\mbox{.}\]
%              Substituindo-se $a_0$ e $a_1$, tem-se:
%              \[g(x)-x=g^2(x)\mbox{.}\]
%              Escolhendo a raiz que leva a coeficientes positivos:
%              \[g(x)=\frac{1-\sqrt{1-4x}}{2}\mbox{.}\]
              
%--------------------------------------------------------------------------------------------

%\newslide{OUTRAS TÉCNICAS PARA RESOLUÇÃO DE RR'S (9)}
%\hypertarget{outras-tecnicas-9}{}
              
%        \item Usando o Teorema Binomial Estendido: 
%              \[\begin{array}{lcl} 
%                (1-4x)^{1/2}&=&\left(\begin{array}{c} 1/2 \\ 0 \end{array}\right)
%                   +\left(\begin{array}{c} 1/2 \\ 1\end{array}\right)(-4x)
%                   +\left(\begin{array}{c} 1/2 \\ 2\end{array}\right)(-4x)^2+
%                   \cdots+ \\
%                   & & \left(\begin{array}{c} 1/2 \\ n
%                   \end{array}\right)(-4x)^n+\cdots \\
%                   &=&1+\frac{1/2}{1!}(-4x)+
%                              \frac{(1/2)(-1/2)}{2!}(-4x)^2+\cdots+\\
%                   & &\frac{(1/2)(-1/2)(-3/2)\cdots(1/2-(n-1))}{n!}(-4x)^n+
%                               \cdots 
%               \end{array}\]
               
%--------------------------------------------------------------------------------------------

%\newslide{OUTRAS TÉCNICAS PARA RESOLUÇÃO DE RR'S (10)}
%\hypertarget{outras-tecnicas-10}{}
               
               
%        \item Portanto, $a_0=0$ e, para $n\geq 1$,
%              \[\begin{array}{ll} 
%                 a_n&=-\frac{(-4)^n(1/2)(-1/2)(-3/2)\cdots(1/2-(n-1))}{2n!} \\
%                    &=\frac{(2n-2)!}{n!(n-1)!} \\
%                    &=C(2n-2,n-1)/n\mbox{.} \\
%               \end{array}\]
%              Os $a_n$ s\~{a}o chamados {\bf n\'{u}meros de Catalan}. 
%       \end{itemize}
%\end{itemize}

%--------------------------------------------------------------------------------------------

\section{RELAÇÕES TIPO DIVISÃO E CONQUISTA}
\hypertarget{div-e-conquista}{}

\newslide{Pesquisa binária}

\begin{quote}
Restrição: $n=2^k$ para algum $k\geq 0$. \\
N\'umero de compara\c{c}\~oes:   $a_1=1; a_n=a_{n/2}+1 \mbox{ para } n\geq 2$.
\end{quote}

\vspace*{5mm}
\noindent Fazendo \textcolor{black}{substituições sucessivas}:

\begin{tabbing}
xxx\=$a_{2^k}$\= \kill
  \> $a_{2^k}$\>$=a_{2^{k-1}}+1$ \\
  \>          \>$=(a_{2^{k-2}}+1)+1=a_{2^{k-2}}+2$ \\
  \>          \>$=(a_{2^{k-3}}+1)+2=a_{2^{k-3}}+3$ \\
  \>          \>$\vdots$ \\
  \>          \>$=(a_{2^{k-k}}+1)+(k-1)=a_{2^{k-k}}+k=a_{2^{0}}+k=a_{1}+k$ \\
  \>          \>$=1+k$.
\end{tabbing}

\vspace*{5mm}
\begin{quote}
Como $n=2^k$, $k=\log_2(n)$ e, portanto, $a_n=\log_2(n) +1$.
\end{quote}
%--------------------------------------------------------------------------------------------

\newslide{Um algoritmo de ordenação (\textit{merge sort})}

\begin{Algorithm}
  Entrada: um vetor v de n\'{u}meros inteiros.
  Sa\'{\i}da: o mesmo vetor em ordem crescente.

  se v tem apenas um elemento ent\~ao
	     ele j\'a est\'a ordenado
  senão
     v1 := ordene a primeira metade de v;
     v2 := ordene a segunda metade de v;
	     v := intercale v1 e v2
  fimse;
  retorne v (ordenado)
\end{Algorithm}

Número de comparações para intercalar $n$ elementos: $n-1$.
%--------------------------------------------------------------------------------------------

\newslide{Desempenho do algoritmo de ordenação}

\begin{quote}
Compara\c{c}\~oes:   $a_1=0; a_n=2a_{n/2}+n-1 \mbox{ para } n\geq 2$.
\end{quote}

\vspace*{5mm}
\noindent Fazendo \textcolor{black}{substituições sucessivas}:

\begin{tabbing}
xxx\=$a_{2^k}$\= \kill
  \> $a_{2^k}$\>$=2a_{2^{k-1}}+2^{k}-1$ \\
  \>          \>$=2(2a_{2^{k-2}}+2^{k-1}-1)+2^{k}-1=4a_{2^{k-2}}+2.2^k-(1+2)$ \\
  \>          \>$=4(2a_{2^{k-3}}+2^{k-2}-1)+2.2^k-(1+2)$ \\
  \>          \>$=8a_{2^{k-3}}+3.2^{k}-(1+2+4)$ \\
  \>          \>$\vdots$ \\
  \>          \>$=2^ka_{2^{k-k}}+k.2^{k}-(1+2+4+\cdots+2^{k-1})$ \\
  \>          \>$=2^ka_{1}+k.2^{k}-(1+2+4+\cdots+2^{k-1})$ \\
  \>          \>$=k.2^{k}-(1+2+4+\cdots+2^{k-1})$ \\
  \>          \>$=k.2^{k}-2^{k}+1$.
\end{tabbing}

\vspace*{4mm}
\begin{quote}
Como $n=2^k$, $k=\log_2(n)$ e, portanto, $a_n=n\log_2(n)-n+1$.
\end{quote}


\defskiptarget{capitulo4}

\lastpage 

\end{document}