\documentclass[12pt, a4paper]{article}

\addtolength{\topmargin}{-2cm}
\addtolength{\textheight}{4cm}

\pagestyle{empty}

\newcounter{conta}
\begin{document}


\noindent Departamento de Ci\^encia da Computa\c c\~ao
\hfill UFMG \\
{\it Matem\'{a}tica Discreta}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2002 \\
Professor: Newton Jos\'{e} Vieira  \\
{\bf Terceira Prova} \hfill 12/02/2003

\vspace*{2mm}
\begin{enumerate}
 \item Deve-se distribuir 7 moedas id\^enticas entre 7 crian\c cas. Maria deve
       receber no m\'{\i}nimo 3 moedas e Jo\~ao deve receber no m\'aximo 2
       moedas.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Fa\c ca uma fun\c c\~ao geradora para o n\'umero de
              distribui\c c\~oes pos\-s\'{\i}\-veis.
        \item Determine o n\'umero de distribui\c c\~oes a partir da fun\c c\~ao
              geradora.
       \end{list}

 \item Avalie a seguinte soma usando fun\c c\~ao geradora:
       \[\sum_{k=0}^{n}\frac{1}{2^k}\mbox{.}\]

 \item Um banco paga 4,5\% de juros ao ano para certa aplica\c c\~ao. Al\'em disso,
       no final do ano, ap\'os o c\^omputo dos juros, ele d\'a um b\^onus de R\$50,00.
       Supondo um investimento inicial de R\$1.000,00:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Encontre uma rela\c c\~ao de recorr\^encia para o saldo da aplica\c c\~ao
              ap\'os $n$ anos (n\~ao havendo nenhuma retirada durante o per\'{\i}odo).
        \item Resolva a rela\c c\~ao de recorr\^encia.
       \end{list}

 \item Seja a rela\c c\~ao de recorr\^encia:
       \begin{enumerate}
        \item[\ ] $a_0=1$,
        \item[\ ] $a_n=a_{n-1}+2^{n-1}-1$ para $n\geq 1$.
       \end{enumerate}
       Encontre uma f\'ormula fechada para $a_n$.
\end{enumerate}

\noindent \rule {16cm}{.2mm}

\noindent Lembretes:
\begin{itemize}
 \item $ \frac{1}{1-x} = 1+x+x^{2}+\cdots$ 

 \item ${(1+x+x^{2}+\cdots)}^{n} = 
 C(n-1+0,0) + C(n-1+1,1)~ x + \cdots + C(n-1+r,r)~ x^{r} + \cdots$

 \item ${(1+x+x^{2}+\cdots+x^{m-1})}^{n} = 
 {(1-x^{m})}^{n} ~  {(1+x+x^{2}+\cdots)}^{n}$

 \item ${(1-x^{m})}^{n} = \sum_{k=0}^{n} ~ (-1)^{k} ~ C(n,k)~ x^{km} $

 \item Se $g(x)$ \'e a fun\c c\~ao geradora para $a_n$,
       \begin{itemize}
        \item $xg'(x)$ \'e a fun\c c\~ao geradora para $na_n$.
        \item $g(x)/(1-x)$ \'e a fun\c c\~ao geradora para $\sum_{k=0}^n a_k$.
        \item $(1-x)g(x)$ \'e a fun\c c\~ao geradora para $a_n-a_{n-1}$.
       \end{itemize}
\end{itemize}

\end{document}
