\documentclass[12pt, a4paper]{article}

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

\pagestyle{empty}

\newcounter{conta}
\begin{document}\footnotesize


\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 Primeira Prova} \hfill 04/12/2002

\vspace*{2mm}
\noindent {\bf Escolha 4 quest\~oes. Cada quest\~ao vale 4 pontos.}

\begin{enumerate}
 \item Considere o conjunto universo como sendo o conjunto de todas as
       pessoas do mundo. Sejam os conjuntos:
       \begin{itemize}
        \item $M=\{x\,:\, x \mbox{ \'e mineiro}\}$
        \item $P=\{x\,:\, x \mbox{ adora praia}\}$
        \item $C=\{x\,:\, x \mbox{ \'e crian\c ca}\}$
        \item $E=\{x\,:\, x \mbox{ estuda na UFMG}\}$
       \end{itemize}
       Que propriedades deve ter uma pessoa para ela pertencer a cada
       um dos conjuntos abaixo especificados?
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $M\cap (P\cup E)$

              \underline{Solu\c c\~ao}: Mineiro que adora praia ou
              estuda na UFMG.

        \item $M-(C\cap E)$

              \underline{Solu\c c\~ao}: Mineiro que n\~ao \'e crian\c ca ou
              que n\~ao estuda na UFMG.

        \item $M-(C\cup E)$

              \underline{Solu\c c\~ao}: Mineiro que n\~ao \'e crian\c ca e
              que n\~ao estuda na UFMG.

        \item $(M\cap\overline{P})-E$

              \underline{Solu\c c\~ao}: Mineiro que n\~ao adora praia e
              que n\~ao estuda na UFMG.

       \end{list}

 \item Quais dentre as rela\c c\~oes abaixo s\~ao rela\c c\~oes de equival\^encia?
       Quantas classes de equival\^encia tem a parti\c c\~ao induzida por cada
       uma delas?
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $R$ sobre $\bf N$ definida por: $a R b$ se, e somente se,
              $b$ \'{e} divis\'{\i}vel por $a$.

              \underline{Solu\c c\~ao}: N\~ao \'e rela\c c\~ao de equival\^encia
              (n\~ao \'e sim\'etrica).

        \item $R$ sobre $\bf R$ definida por: $a R b$ se, e somente se,
              $a-b$ \'{e} um n\'umero inteiro.

              \underline{Solu\c c\~ao}: \'E rela\c c\~ao de equival\^encia.
              Possui infinitas classes de equival\^encia.

        \item $R$ sobre $\bf N$ definida por: $a R b$ se, e somente se,
              $a-b=1$.

              \underline{Solu\c c\~ao}: N\~ao \'e rela\c c\~ao de equival\^encia
              (n\~ao \'e reflexiva, sim\'etrica nem transitiva).

        \item $R$ sobre $\bf N$ definida por: $a R b$ se, e somente se,
              $a \mbox{ mod } 3=b \mbox{ mod } 3$.

              \underline{Solu\c c\~ao}: \'E rela\c c\~ao de equival\^encia.
              Possui 3 classes de equival\^encia: uma para cada resto de
              divis\~ao por 3.

       \end{list}

 \item Prove que, para quaisquer n\'umeros reais $x$ e $y$, se $x^2+y^2=13$ e $|y|\not=3$
       ent\~ao $x\not=2$.

       \underline{Solu\c c\~ao}: Sejam $x$ e $y$ n\'umeros reais arbitr\'arios.
       Suponha que $x^2+y^2=13$ e $|y|\not=3$. Ser\'a mostrado, por contradi\c c\~ao,
       que $x\not=2$. Assim, suponha que $x=2$. Substituindo-se $x$ na equa\c c\~ao
       acima, obt\'em-se: $2^2+y^2=13$, o que d\'a $y=\sqrt{9}=3$, o que contradiz a
       suposi\c c\~ao anterior que $|y|\not=3$. Logo, se $x^2+y^2=13$ e $|y|\not=3$,
       ent\~ao $x\not=2$. Como $x$ e $y$ s\~ao reais arbitr\'arios, isto vale para
       quaisquer n\'umeros reais $x$ e $y$.

 \item Prove, por indu\c c\~ao matem\'atica, que
       \[\mbox{ para todo } n\geq 1, \sum_{i=1}^{n}\frac{1}{i^2}\leq 2-\frac{1}{n}\mbox{.}\]

       \underline{Solu\c c\~ao}: Para $n=1$: $\sum_{i=1}^{1}1/i^2=1/1^2=1=2-1/1$.
       Seja $n\geq 1$ arbitr\'ario. Suponha, como hip\'otese de indu\c c\~ao, que
       $\sum_{i=1}^{n}1/i^2\leq 2-1/n$. Segue-se que:

       \begin{tabbing}
        \hspace*{5mm} $\sum_{i=1}^{n+1}1/i^2$\= \kill
        \hspace*{5mm} $\sum_{i=1}^{n+1}1/i^2$\>$=\sum_{i=1}^{n}1/i^2 + 1/(n+1)^2$ \\
                        \>$\leq (2- 1/n) + 1/(n+1)^2$ \ pela hip\a'otese de indu\c c\~ao \\
                        \>$= 2- [(n+1)^2-n]/n(n+1)^2$ \\
                        \>$= 2- [n^2+2n+1-n]/n(n+1)^2$ \\
                        \>$= 2- [n^2+n+1]/n(n+1)^2$ \\
                        \>$= 2- [n(n+1)+1]/n(n+1)^2$ \\
                        \>$= 2- 1/(n+1)-1/n(n+1)^2$ \\
                        \>$< 2- 1/(n+1)$ \ pois $1/n(n+1)^2>0$ (j\a'a que $n\geq 1$). \\
       \end{tabbing}

       Portanto, $\sum_{i=1}^{n+1}1/i^2\leq 2- 1/(n+1)$. Conclui-se, ent\~ao, pelo
       princ\'{\i}pio de indu\c c\~ao, que $\sum_{i=1}^{n}1/i^2\leq 2-1/n$ para todo $n\geq 1$.

 \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{.}\]

       \underline{Solu\c c\~ao}: Para $n=0$: $\sum_{i=0}^0(F_i)^2=F_0^2=0^2=0
       =0\times 1=F_0F_1$.
       Seja $n\geq 0$ arbitr\'ario. Suponha, como hip\'otese de indu\c c\~ao, que
       $\sum_{i=0}^n (F_i)^2=F_nF_{n+1}$. Segue-se que:

       \begin{tabbing}
        \hspace*{5mm} $\sum_{i=0}^{n+1} (F_i)^2$\= \kill
        \hspace*{5mm} $\sum_{i=0}^{n+1} (F_i)^2$\>$=\sum_{i=0}^{n}(F_i)^2 + F_{n+1}^2$ \\
                        \>$=F_nF_{n+1} + F_{n+1}^2$ \ pela hip\a'otese de indu\c c\~ao \\
                        \>$=F_{n+1}(F_n + F_{n+1})$ \\
                        \>$=F_{n+1}F_{n+2}$ \ pela defini\c c\~ao de $F$.
       \end{tabbing}

       Portanto, $\sum_{i=0}^{n+1} (F_i)^2=F_{n+1}F_{n+2}$. Conclui-se, ent\~ao, pelo
       princ\'{\i}pio de indu\c c\~ao, que $\sum_{i=0}^n (F_i)^2=F_nF_{n+1}$ para todo
       $n\in\mbox{\bf N}$.


\end{enumerate}

\end{document}
