\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} -- \underline{Solu\c{c}\~oes da Parte 1}: \underline{Rela\c{c}\~{o}es de Recorr\^{e}ncia}

\vspace*{2mm}
\begin{enumerate}
 \item {\footnotesize Um banco paga 4,5\% de juros por ano. Al\'em disso, ele paga um b\^onus de \$100
       no final de cada ano (ap\'os pagos os juros). Encontre uma rela\c c\~ao de recorr\^encia
       para o total pago ap\'os $n$ anos, se o investimento inicial for de \$200.}
       %Townsend 4.1/9

       \textit{Solu\c{c}\~ao}:
       
       $a_0=200$; \\
       $a_n=1,045a_{n-1}+100$ para $n\geq 1$.

 \item {\footnotesize Encontre uma rela\c{c}\~{a}o de recorr\^{e}ncia para o n\'{u}mero de
       sequ\^{e}ncias quatern\'{a}rias de $n$ d\'{\i}gitos:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item sem 1's consecutivos.
        \item com n\'{u}mero par de 0's.
       \end{list}}
       %Townsend 4.1/10

       \textit{Solu\c{c}\~ao}:
       
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $a_0=1$, $a_1=4$; \\
              $a_n=3a_{n-1}+3a_{n-2}$ para $n\geq 2$.
        \item $a_0=1$; \\
              $a_n=3a_{n-1}+(4^{n-1}-a_{n-1})=2a_{n-1}+4^{n-1}$ para $n\geq 1$.
       \end{list}

 \item {\footnotesize Encontre uma rela\c{c}\~{a}o de recorr\^{e}ncia para o n\'{u}mero de maneiras de
       colocar id\^{e}nticos Toyotas, Cadillacs e Mercedes em um espa\c{c}o cujo
       tamanho \'{e} $n$ ``unidades'', sabendo que Mercedes e Cadillacs ocupam
       2 unidades cada um, e que Toyotas ocupam uma unidade cada um.}
       %Townsend 4.1/11

       \textit{Solu\c{c}\~ao}:

       $a_1=1$, $a_2=3$; \\
       $a_n=a_{n-1}+2a_{n-2}$ para $n\geq 2$.
       
 \item {\footnotesize Considere $n$ quadrados dispostos lado a lado, como mostra a figura:
       \begin{center} 
       \begin{picture}(175,25)
        \put(50,0){\line(1,0){30}}
        \put(50,15){\line(1,0){30}}
        \put(50,0){\line(0,1){15}}
        \put(65,0){\line(0,1){15}}
        \put(80,0){\line(0,1){15}}
        \put(95,8){\makebox(0,0){$\cdots$}}
        \put(110,0){\line(1,0){15}}
        \put(110,15){\line(1,0){15}}
        \put(110,0){\line(0,1){15}}
        \put(125,0){\line(0,1){15}}
        \put(57,17){\makebox(0,0)[b]{$1$}}
        \put(72,17){\makebox(0,0)[b]{$2$}}
        \put(117,17){\makebox(0,0)[b]{$n$}}
       \end{picture}
       \end{center}
       Seja $a_n = $ {\it n\'{u}mero de maneiras de colorir os quadrados, de forma
       que n\~{a}o fiquem dois quadrados vermelhos adjacentes\/}. Encontre uma
       rela\c{c}\~{a}o de recorr\^{e}ncia para $a_n$, para cada um dos seguintes casos:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Cada quadrado pode ser colorido de vermelho ou de verde.
        \item Cada quadrado pode ser colorido de vermelho, de verde, ou de
              amarelo.
        \item Generalize para $k$ cores (incluindo vermelho).
       \end{list}}

       \textit{Solu\c{c}\~ao}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $a_0=1$, $a_1=2$; \\
              $a_n=a_{n-1}+a_{n-2}$ para $n\geq 2$.
        \item $a_0=1$, $a_1=3$; \\
              $a_n=2a_{n-1}+2a_{n-2}$ para $n\geq 2$.
        \item $a_0=1$, $a_1=k$; \\
              $a_n=(k-1)a_{n-1}+(k-1)a_{n-2}$ para $n\geq 2$.
       \end{list}

 \item {\footnotesize Encontre uma rela\c{c}\~{a}o de recorr\^{e}ncia para o n\'{u}mero de maneiras
       de subir $n$ degraus, se em cada est\'{a}gio pudermos avan\c{c}ar 1, 3 ou 5
       degraus de uma vez.}
       %Townsend 4.1/12

       \textit{Solu\c{c}\~ao}:

       $a_0=1$, $a_1=1$, $a_2=1$, $a_3=2$, $a_4=3$; \\
       $a_n=a_{n-1}+a_{n-3}+a_{n-5}$ para $n\geq 5$.

 \item {\footnotesize Seja o conjunto de d\'{\i}gitos e letras $X=\{1,2,3,4,a,b,c,d,e,f,g\}$.
       Encontre uma rela\c{c}\~{a}o de recorr\^{e}ncia para o n\'{u}mero de
       sequ\^{e}ncias de $n$ s\'{\i}mbolos de $X$, para cada uma das seguintes
       situa\c c\~oes:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item n\~ao h\'a letras consecutivas (id\^enticas ou n\~ao).
        \item n\~ao h\'a d\'{\i}gito seguido de letra.
        \item o n\'{u}mero de letras \'e par.
       \end{list}}

       \textit{Solu\c c\~ao\/}:
       
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item n\~ao h\'a letras consecutivas (id\^enticas ou n\~ao).
        
              $a_0=1$, $a_1=11$, $a_n=4a_{n-1}+28a_{n-2} \; (n\geq 2)$
        
        \item n\~ao h\'a d\'{\i}gito seguido de letra.
        
              $a_0=1$, $a_1=11$, $a_n=4a_{n-1}+49a_{n-2} \; (n\geq 2)$
        
        \item o n\'{u}mero de letras \'e par.
        
              $a_0=1$, $a_n=4a_{n-1}+7(11^{n-1}-a_{n-1}) \; (n\geq 1)$, ou seja,
              
              $a_0=1$, $a_n=7.11^{n-1}-3a_{n-1} \; (n\geq 1)$
        
       \end{list}

 \item {\footnotesize Encontre uma rela\c{c}\~{a}o de recorr\^{e}ncia para o n\'{u}mero de regi\~oes
       em que o plano \'e dividido por $n$ c\'{\i}rculos se cada par de c\'{\i}rculos se
       interceptam em dois pontos, mas tr\^es c\'{\i}rculos nunca se interceptam em um
       \'unico ponto.}
       %Townsend 4.1/17

       \textit{Solu\c{c}\~ao}:

       $a_1=2$;\\
       $a_n=a_{n-1}+2(n-1)$ para $n\geq 2$.

 \item {\footnotesize Encontre uma rela\c{c}\~{a}o de recorr\^{e}ncia para o n\'{u}mero de
       sequ\^{e}ncias tern\'{a}rias de $n$ d\'{\i}gitos sem a
       subsequ\^{e}ncia 012.}
%      EX. 7, pag. 283. Tucker

       \textit{Solu\c{c}\~ao}:

       $a_0=1$, $a_1=3$, $a_2=9$;\\
       $a_n=2a_{n-1}+(a_{n-1}-a_{n-3})=3a_{n-1}-a_{n-3}$ para $n\geq 3$.

       Obs: supondo que $a_{n-1}$ seqs de $n-1$ d\'{\i}gitos n\~ao t\^em 012:
       $a_{n-1}$ seqs de $n$ d\'{\i}gitos terminam em 2 e podem ter
       012 apenas como \underline{sufixo}; logo, $a_{n-1}-a_{n-3}$ seqs de
       $n$ d\'{\i}gitos n\~ao t\^em 012 ($a_{n-3}$ \'e o n\'umero de seqs
       de $n-1$ d\'{\i}gitos sem 012, terminadas em 01).

 \item {\footnotesize Encontre uma rela\c{c}\~{a}o de recorr\^{e}ncia para o n\'{u}mero de
       regi\~oes criadas por $n$ linhas sobre uma folha de papel se $k$ das
       linhas s\~ao paralelas e cada uma das outras $n-k$ intersepta todas
       as linhas (e n\~ao mais de 2 linhas se interseptam em um \'unico ponto).}
%      Ex. 13(a), pag. 289. Tucker

       \textit{Solu\c{c}\~ao}:

       $a_k=k+1$; \\
       $a_n=a_{n-1}+n$ para $n\geq k+1$.

 \item {\footnotesize Encontre uma rela\c{c}\~{a}o de recorr\^{e}ncia para o n\'umero de sequ\^encias de $r$
       elementos tomados de um conjunto de $n$ elementos.}
       %Townsend 4.1/20

       \textit{Solu\c{c}\~ao}:

       $S_{n,0}=1$; \\
       $S_{n,r}=nS_{n,r-1}$ para $n\geq 1$.

 \item {\footnotesize Encontre uma rela\c{c}\~{a}o de recorr\^{e}ncia para o n\'umero de multiconjuntos de $r$
       elementos tomados de um conjunto de $n$ elementos.}
       %Townsend 4.1/20

       \textit{Solu\c{c}\~ao}:

       $M_{n,1}=n$, $M_{1,r}=1$; \\
       $M_{n,r}=M_{n-1,r}+M_{n,r-1}$ para $r>1$, $n>1$.

 \item {\footnotesize Encontre uma rela\c{c}\~{a}o de recorr\^{e}ncia para o n\'umero de decomposi\c{c}\~oes
       de um conjunto de $n$ elementos em exatamente $k$ partes (conjuntos n\~ao vazios disjuntos).}
       %Townsend 4.1/23

       \textit{Solu\c{c}\~ao}:

       $P_{n,1}=P_{n,n}=1$; \\
       $P_{n,k}=P_{n-1,k-1}+ kP_{n-1,k}$ para $1<k<n$.

 \item {\footnotesize Sejam $n$ caixas distintas dispostas em uma fila. Encontre uma rela\c{c}\~{a}o
       de recorr\^{e}ncia para o n\'{u}mero de maneiras de distribuir $k$ bolas
       id\^{e}nticas de forma que cada caixa receba no m\'{a}ximo 1 bola, e que n\~{a}o
       haja caixas consecutivas com bolas.}
       %Townsend 4.1/24

       \textit{Solu\c{c}\~ao}:

       $D_{n,0}=D_{1,1}=1$, $D_{n,n}=0$ para $n>1$; \\
       $D_{n,k}=D_{n-1,k}+ D_{n-2,k-1}$ para $0<k<n$.

 \item {\footnotesize Mostre que $C_1(1+\sqrt{5})^n+C_2(1-\sqrt{5})^n$ \'{e} a solu\c{c}\~{a}o geral para
       $a_n-2a_{n-1}-4a_{n-2}=0$.}

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

       \begin{tabbing}\small
        xxx\= \kill
        $C_1(1+\sqrt{5})^n+C_2(1-\sqrt{5})^n-2[C_1(1+\sqrt{5})^{n-1}+C_2(1-\sqrt{5})^{n-1}]$ \\
           \>\hspace*{1cm}$-4[C_1(1+\sqrt{5})^{n-2}+C_2(1-\sqrt{5})^{n-2}]$ \\
           \>$=[C_1(1+\sqrt{5})^n-2C_1(1+\sqrt{5})^{n-1}-4C_1(1+\sqrt{5})^{n-2}]$ \\
           \>\hspace*{1cm}$+[C_2(1-\sqrt{5})^n-2C_2(1-\sqrt{5})^{n-1}-4C_2(1-\sqrt{5})^{n-2}]$ \\
           \>$=C_1(1+\sqrt{5})^{n-2}[(1+\sqrt{5})^2-2(1+\sqrt{5})-4]$ \\
           \>\hspace*{1cm}$+C_2(1-\sqrt{5})^{n-2}[(1-\sqrt{5})^2-2(1-\sqrt{5})-4]$ \\
           \>$=C_1(1+\sqrt{5})^{n-2}[1+2\sqrt{5}+5-2-2\sqrt{5}-4]$ \\
           \>\hspace*{1cm}$+C_2(1-\sqrt{5})^{n-2}[1-2\sqrt{5}+5-2+2\sqrt{5}-4]$ \\
           \>$=C_1(1+\sqrt{5})^{n-2}.0+C_2(1-\sqrt{5})^{n-2}.0$ \\
           \>$=0$.
       \end{tabbing}
 \item {\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 {\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 {\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 {\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}