\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 Exame especial} \hfill 26/03/2003

\begin{enumerate}

 \item Seja a sequ\^encia de Fibonacci, definida recursivamente por:
       \begin{enumerate}
        \item[\ ] $F_0=0$;
        \item[\ ] $F_1=1$;
        \item[\ ] para todo $n\geq 2$, $F_n=F_{n-2}+F_{n-1}$.
       \end{enumerate}
       Prove, usando indu\c c\~ao matem\'atica, que
       \[\mbox{para todo } n\in\mbox{\bf N}, \sum_{i=0}^n (F_i)^2=F_nF_{n+1}\mbox{.}\]

 \item De quantas maneiras se pode arranjar as letras AAAABBBCCDEF:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item No total?
        \item Com todos os A's antes de F?
        \item Sem B's consecutivos?
       \end{list}

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

 \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$.

 \item Dos n\'umeros 1 a 1000, inclusive, quantos s\~ao
       divis\'{\i}veis por 7, 9 ou 21? (Observe que os divis\'{\i}veis por $x$
       \underline{e} $y$ s\~ao aqueles divis\'{\i}veis pelo m\'{\i}nimo
       m\'ultiplo comum de ambos.)

 \item Sabe-se que em certa competi\c c\~ao de futebol foram realizadas 20
       partidas. Se cada equipe jogou no m\'{\i}nimo 4 partidas, qual o maior
       n\'umero poss\'{\i}vel de equipes que podem ter participado da
       competi\c c\~ao? (Modele o problema por meio de grafo.)
\end{enumerate}

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

\noindent Veja alguns lembretes no verso.

\pagebreak
\noindent {\bf 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}

