\documentclass[12pt, a4paper]{article}

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

\pagestyle{empty}

\newcounter{conta}
\newcounter{conta2}
\begin{document}

\noindent Bacharelado em Matem\'atica Computacional
\hfill UFMG \\
{\it Matem\'{a}tica Discreta}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2002 \\
Professor: Newton Jos\'{e} Vieira  \\
{\bf Terceira Prova/Solu\c c\~ao do professor} \hfill 11/09/2002

\begin{enumerate}\footnotesize
 \item {\em Suponha que $R$ \'e uma rela\c c\~ao de $A$ para $B$ e que $S$ e $T$ s\~ao
       rela\c c\~oes de $B$ para $C$. Mostre que sim ou que n\~ao:
       \[\mbox{se } S\subseteq T \mbox{ ent\~ao } S\circ R\subseteq T\circ R\mbox{.}\]}

       \vspace*{2mm}
       {\em Solu\c c\~ao\/}: Suponha que $S\subseteq T$. Seja $(a,c)$ um par
       arbitr\'ario de $A\times C$ tal que $(a,c)\in S\circ R$. Neste caso, existe
       $b\in B$ tal que $(a,b)\in R$ e $(b,c)\in S$. E como $(b,c)\in S$ e $S\subseteq T$,
       deduz-se que $(b,c)\in T$. De $(a,b)\in R$ e $(b,c)\in T$, tem-se que
       $(a,c)\in T\circ R$. Como $(a,c)$ \'e um par arbitr\'ario de $S\circ R$,
       segue-se que $S\circ R\subseteq T\circ R$. Portanto, se $S\subseteq T$
       ent\~ao $S\circ R\subseteq T\circ R$.

 \item {\em Considere o seguinte candidato a teorema:
       \begin{quote}
       {\bf Teorema?} {\em Suponha que $R$ \'e uma rela\c c\~ao sobre $A$. Se $R$ \'e
       sim\'etrica e transitiva, ent\~ao $R$ \'e reflexiva}
       \end{quote}
       A prova a seguir est\'a correta? Se estiver, que estrat\'egias ela usa? Se n\~ao
       estiver correta, qual \'e o problema? Afinal, o enunciado acima constitui mesmo
       um teorema?

       {\em Prova\/} Seja $x$ um elemento arbitr\'ario de $A$. Seja $y$ um elemento de
       $A$ tal que $x R y$. Como $R$ \'e sim\'etrica, segue-se que $y R x$. Mas ent\~ao
       por transitividade, como $x R y$ e $y R x$ conclui-se que $x R x$. Como $x$ \'e
       arbitr\'ario, mostrou-se que $\forall x\in A (x R x)$, e portanto $R$ \'e reflexiva.}

       \vspace*{2mm}
       {\em Solu\c c\~ao\/}: A prova n\~ao est\'a correta. A segunda
       frase da prova ``seja $y$ um elemento de $A$ tal que $x R y$'' n\~ao poderia ser
       dita ali, visto que pode n\~ao existir $y$ tal que $x R y$.

       O enunciado n\~ao constitui um teorema. Existem rela\c c\~oes sim\'etricas e
       e transitivas que n\~ao s\~ao reflexivas. A prova incorreta acima j\'a d\'a
       uma dica: se h\'a um certo elemento $a\in A$ para o qual n\~ao exista $y\in A$
       tal que $a R y$, $R$ n\~ao \'e reflexiva (pois, em particular, n\~ao \'e o
       caso que $a R a$), mesmo que seja sim\'etrica e transitiva.

 \item {\em Seja $A=\mbox{\bf R}\backslash \{1\}$, e seja $f:A\rightarrow A$ definida como
       segue: \[f(x)=\frac{x+1}{x-1}\mbox{.}\]
       Mostre que $f$ \'e bijetora.}

       \vspace*{2mm}
       {\em Solu\c c\~ao\/}:

       \underline{\em $f$ \'e injetora.} Sejam $x$ e $y$ elementos arbitr\'arios de $A$
       tais que $f(x)=f(y)$. Basta, ent\~ao mostrar que $x=y$. De fato, de
       \[\frac{x+1}{x-1}=\frac{y+1}{y-1}\] deduz-se que $(x+1)(y-1)=(x-1)(y+1)$, da
       qual deduz-se que $xy-x+y-1=xy+x-y-1$. Fazendo-se os cancelamentos de termos
       id\^enticos, obt\'em-se $-x+y=x-y$. Somando-se $x$ e $y$ a ambos os termos
       desta equa\c c\~ao, obt\'em-se $2y=2x$, de onde se conclui que $x=y$.

       \underline{\em $f$ \'e sobrejetora.} Seja $y$ um elemento arbitr\'ario de $A$.
       Basta mostrar que existe $x\in A$ tal que $f(x)=y$. De fato, basta fazer
       $x=(y+1)/(y-1)$, j\'a que, neste caso:
       \[f(x)=\frac{\frac{y+1}{y-1}+1}{\frac{y+1}{y-1}-1}
             =\frac{\frac{y+1+y-1}{y-1}}{\frac{y+1-y+1}{y-1}}
             =\frac{2y}{2}=y\mbox{.}\]

 \item {\em Encontre uma f\'ormula para $\sum_{i=1}^{n}(2i-1)$, e prove que sua f\'ormula
       \'e correta usando indu\c c\~ao matem\'atica. (Para encontrar a f\'ormula, basta
       fazer a soma para alguns valores iniciais $n=1, 2, 3, 4, \ldots$.)}

       \vspace*{2mm}
       {\em Solu\c c\~ao\/}: Conjectura: $\sum_{i=1}^{n}(2i-1)=n^2$. Tal conjectura ser\'a
       provada por indu\c c\~ao matem\'atica sobre $n$. Para $n=1$, tem-se que
       $\sum_{i=1}^{1}(2i-1)=2\times 1-1=1=1^2$. Seja $n\geq 1$ arbitr\'ario. Suponha,
       como hip\'otese de indu\c c\~ao, que  $\sum_{i=1}^{n}(2i-1)=n^2$. Basta, ent\~ao,
       provar que $\sum_{i=1}^{n+1}(2i-1)=(n+1)^2$, o que \'e feito a seguir:
       \begin{tabbing}
        $\sum_{i=1}^{n+1}(2i-1)$\=$=\sum_{i=1}^{n}(2i-1)+2(n+1)-1$\ \ \ \=\  \kill
        $\sum_{i=1}^{n+1}(2i-1)$\>$=\sum_{i=1}^{n}(2i-1)+2(n+1)-1$ \\
                                \>$=n^2+2(n+1)-1$ \>pela hip\a'otese de indu\c c\~ao \\
                                \>$=n^2+2n+1$  \\
                                \>$=(n+1)^2$.
       \end{tabbing}

 \item A sequ\^encia $a_0, a_1, a_2, \ldots$ \'e definida recursivamente como segue:
       \begin{enumerate}
        \item[\ ] $a_0=0$;
        \item[\ ] para todo $n\in\mbox{\bf N}$, $a_{n+1}=2a_n+n$.
       \end{enumerate}
       Prove que para todo $n\in\mbox{\bf N}$, $a_n=2^n-(n+1)$.

       \vspace*{2mm}
       {\em Solu\c c\~ao\/}: Por indu\c c\~ao sobre $n$. Para $n=0$, tem-se:
       $2^0-(0+1)=1-1=0=a_0$. Seja $n$ um n\'umero natural arbitr\'ario, e suponha
       como hip\'otese de indu\c c\~ao que $a_n=2^n-(n+1)$. Basta mostrar que
       $a_{n+1}=2^{n+1}-(n+2)$, o que \'e feito abaixo:
       \begin{tabbing}
        $a_{n+1}$\=$=2(2^n-(n+1))+n$\ \ \ \=\  \kill
        $a_{n+1}$\>$=2a_n+n$ \> pela defini\c c\~ao\\
                 \>$=2(2^n-(n+1))+n$ \>pela hip\a'otese de indu\c c\~ao \\
                 \>$=2^{n+1}-2n-2+n$  \\
                 \>$=2^{n+1}-n-2$  \\
                 \>$=2^{n+1}-(n+2)$.
       \end{tabbing}

 \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 que para todo $n\in\mbox{\bf N}$, $\sum_{i=0}^n F_i=F_{n+2}-1$.

       \vspace*{2mm}
       {\em Solu\c c\~ao\/}: Usando indu\c c\~ao sobre $n$, considere inicialmente
       $n=0$: $\sum_{i=0}^0 F_i=F_0=0=1-1=F_2-1=F_{0+2}-1$. Seja $n$ arbitr\'ario
       e seja a hip\'otese de indu\c c\~ao: $\sum_{i=0}^n F_i=F_{n+2}-1$. Segue-se
       que:

       \begin{tabbing}
        $\sum_{i=0}^{n+1} F_i$\=$=F_{n+2}-1 +F_{n+1}$\ \ \ \=\  \kill
        $\sum_{i=0}^{n+1} F_i$\>$=\sum_{i=0}^n F_i + F_{n+1}$ \\
                              \>$=F_{n+2}-1 +F_{n+1}$ \>pela hip\a'otese de indu\c c\~ao \\
                              \>$=F_{n+1}+F_{n+2}-1$  \\
                              \>$=F_{n+3}-1$  \> pela defini\c c\~ao.
       \end{tabbing}

\end{enumerate}

\end{document}