\documentclass[11pt,a4paper]{article}

\usepackage[portuguese]{babel}
\usepackage{fullpage}

\newcounter{conta}

\begin{document}
 
\noindent Departamento de Ci\^{e}ncia da Computa\c{c}\~{a}o
\hfill ICEx/UFMG \\
{\it Matem\'{a}tica Discreta}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2008 \\
Professor: Newton Jos\'{e} Vieira \hfill nvieira@dcc.ufmg.br\\
\underline{Terceira Lista de Exerc\'{\i}cios} -- Para voc\^e conferir seus resultados \\
\underline{Rela\c{c}\~{o}es de Recorr\^{e}ncia --- Exerc\'{\i}cios 15 a 18}

\vspace*{2mm}
\begin{enumerate}
 \item[15.] {\footnotesize Resolva as seguintes rela\c{c}\~{o}es de recorr\^{e}ncia:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $a_1=0$, $a_2=2$, $a_n+5a_{n-1}+6a_{n-2}=0$ para $n\geq 3$.
        \item $a_0=1$, $a_1=2$, $a_n-2a_{n-1}-a_{n-2}=0$ para $n\geq 2$.
        \item $a_1=2$, $a_2=6$, $a_n-4a_{n-1}+4a_{n-2}=0$ para $n\geq 3$.
        \item $a_1=5$, $a_2=-5$, $a_n+6a_{n-1}+9a_{n-2}=0$ para $n\geq 3$.
       \end{list}}

       {\it Solu\c c\~ao\/}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Equa\c{c}\~ao caracter\'{\i}stica: $x^2+5x+6=0$. As ra\'{\i}zes s\~ao $x_1=-2$, $x_2=-3$.
              Logo a solu\c{c}\~ao geral \'e $C_1(-2)^n+C_2(-3)^n$. Para satisfazer as condi\c{c}\~oes
              iniciais deve-se ter $C_1(-2)^1+C_2(-3)^1=0$ e $C_1(-2)^2+C_2(-3)^2=2$, ou seja:
              \begin{enumerate}
               \item[\ ] $-2C_1-3C_2=0$
               \item[\ ] $4C_1+9C_2=2$
              \end{enumerate}
              Resolvendo esse sistema, obt\'em-se $C_1=-1$ e $C_2=2/3$. Logo, a solu\c{c}\~ao da RR
              \'e $a_n=(-1)(-2)^n+(2/3)(-3)^n$.
        \item Equa\c{c}\~ao caracter\'{\i}stica: $x^2-2x-1=0$. Ra\'{\i}zes: $x_1=1+\sqrt{2}$ e $x_2=1-\sqrt{2}$.
              Logo a solu\c{c}\~ao geral \'e $C_1(1+\sqrt{2})^n+C_2(1-\sqrt{2})^n$. Para satisfazer as condi\c{c}\~oes
              iniciais deve-se ter $C_1(1+\sqrt{2})^0+C_2(1-\sqrt{2})^0=1$ e
              $C_1(1+\sqrt{2})^1+C_2(1-\sqrt{2})^1=2$, ou seja:
              \begin{enumerate}
               \item[\ ] $C_1+C_2=1$
               \item[\ ] $(1+\sqrt{2})C_1+(1-\sqrt{2})C_2=2$
              \end{enumerate}
              Assim, obt\'em-se $C_1=(1+\sqrt{2})/2\sqrt{2}$ e $C_2=-(1-\sqrt{2})/2\sqrt{2}$. Logo,
              a solu\c{c}\~ao da RR
              \'e $[(1+\sqrt{2})^{n+1}-(1-\sqrt{2})^{n+1}]/2\sqrt{2}$.
        \item Solu\c{c}\~ao da parte recorrente: $C_12^n+C_2n2^n$.
        \item Solu\c{c}\~ao da parte recorrente: $C_1(-3)^n+C_2n(-3)^n$.
       \end{list}

 \item[16.] {\footnotesize Resolva as seguintes rela\c{c}\~{o}es de recorr\^{e}ncia:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $a_0=1$, $a_n-2a_{n-1}=n^2$ para $n\geq 1$.
        \item $a_0=1$, $a_1=-1$, $a_n-3a_{n-1}+2a_{n-2}=n$ para $n\geq 2$.
        \item $a_0=1$, $a_1=0$, $a_n-2a_{n-1}+a_{n-2}=2$ para $n\geq 2$.
        \item $a_0=0$, $a_n+3a_{n-1}=2^n$ para $n\geq 1$.
        \item $a_1=0$, $a_2=0$, $a_n-4a_{n-1}+4a_{n-2}=(-2)^n$ para $n\geq 3$.
        \item $a_0=1$, $a_n+2a_{n-1}=2^n-n^2$ para $n\geq 1$.
        \item $a_0=2$, $a_n-2a_{n-1}=2^{n-1}$ para $n\geq 1$.
       \end{list}}

       {\it Solu\c c\~ao\/}:
       
       Solu\c{c}\~oes das partes recorrentes:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $g(n)=C_12^n$; $p(n)=-(n^2+4n+6)$.
        \item $g(n)=C_1+C_22^n$; $p(n)=-(n^2+5n)/2$.
        \item $g(n)=C_1+C_2n$; $p(n)=n^2$.
        \item $g(n)=C_1(-3)^n$; $p(n)=2^{n+1}/5$.
        \item $g(n)=C_12^n+C_2n2^n$; $p(n)=(-2)^{n-2}$.
        \item $g(n)=C_1(-2)^n$; $p_1(n)=-(9n^2+12n+2)/27$, $p_2(n)=2^{n-1}$.
        \item $g(n)=C_12^n$; $p(n)=n2^{n-1}$.
       \end{list}

 \item[17.] {\footnotesize Resolva as seguintes rela\c{c}\~{o}es de recorr\^{e}ncia:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $a_1=1$, $a_n^3=2a_{n-1}^3+1$ para $n\geq 2$. (Sugest\~{a}o: fa\c{c}a
              $b_n=a_n^3$.)
        \item $a_0=2$, $a_n=na_{n-1}+n!$ para $n\geq 1$.
       \end{list}}

       {\it Solu\c c\~ao\/}:
       
        \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\sqrt[3]{2^n-1}$.
        \item $(n+2)n!$.
       \end{list}

 \item[18.] {\footnotesize Usando rela\c{c}\~{o}es de recorr\^{e}ncia, avalie as seguintes somas:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $1+2+4+\cdots+2^n$.
        \item $1^2+2^2+\cdots+n^2$.
        \item $1\times 2+2\times 3+\cdots+n(n+1)$.
       \end{list}}

       {\it Solu\c c\~ao\/}:
       
       Basta resolver as rela\c{c}\~oes de recorr\^encia:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $a_0=1$; \\
              $a_n=a_{n-1}+2^n$.
        \item $a_0=0$; \\
              $a_n=a_{n-1}+n^2$.
        \item $a_0=0$; \\
              $a_n=a_{n-1}+n^2+n$.
       \end{list}
\end{enumerate}

\end{document}