\documentclass[11pt, a4paper]{report}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}
\usepackage{fullpage}
\pagestyle{empty}
\newcounter{conta}
\usepackage{gastex}
\usepackage[usenames]{color}

\begin{document}

\vspace*{2cm}
\noindent {\it Demonstração de Teoremas} \hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2010 \\
\noindent Professor: Newton José Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Segunda Prova}/Solução do professor\hfill {1/7/2010}

\vspace*{2mm}
\begin{enumerate}
 \item {\footnotesize Suponha que $R$ e $S$ sejam relações reflexivas sobre $A$. Prove que $R\circ S$ é reflexiva.}

       \textit{Solução}:

       Seja $x$ um elemento arbitrário de $A$. Como $R$ e $S$ são reflexivas, segue-se que $x R x$ e $x S x$. Portanto,
       $(x,x)\in R\circ S$. Como $x$ é elemento arbitrário de $A$, conclui-se que $R\circ S$ é reflexiva.

 \item {\footnotesize Suponha que $R$ seja uma ordem parcial sobre $A$ e que $B\subseteq A$. Prove que $R\cap(B\times B)$ é uma
       ordem parcial sobre $B$.}

       \textit{Solução}:

       Inicialmente, observe que $R\cap(B\times B)$ é uma relação sobre $B$, pois $B\times B\subseteq A\times A$.
       \begin{enumerate}
        \item[1.] \textit{$R\cap(B\times B)$ é reflexiva}. Seja $b\in B$ arbitrário. Segue-se que $(b,b)\in B\times B$
              e, como $B\subseteq A$, $b\in A$. E como $R$ é reflexiva, $b R b$. Assim, $(b,b)\in R\cap(B\times B)$.
              Logo, $R\cap(B\times B)$ é reflexiva.
        \item[2.] \textit{$R\cap(B\times B)$ é antissimétrica}. Sejam $b_1,b_2\in B$ arbitrários e suponha que
              $(b_1,b_2)\in R\cap(B\times B)$ e $(b_2,b_1)\in R\cap(B\times B)$. Segue-se então que $b_1 R b_2$ e
              $b_2 R b_1$ e, como $R$ é antissimétrica, $b_1=b_2$. Conclui-se que $R\cap(B\times B)$ é antissimétrica.
        \item[3.] \textit{$R\cap(B\times B)$ é transitiva}. Sejam $b_1,b_2,b_3\in B$ arbitrários e suponha que
              $(b_1,b_2)\in R\cap(B\times B)$ e $(b_2,b_3)\in R\cap(B\times B)$. Segue-se então que $b_1 R b_2$ e
              $b_2 R b_3$ e, como $R$ é transitiva, $b_1 R b_3$. E já que $(b_1,b_3)\in B\times B$,
              $(b_1,b_3)\in R\cap(B\times B)$. Portanto, $R\cap(B\times B)$ é transitiva.
       \end{enumerate}

 \item {\footnotesize Prove que para todo $n\geq 1$, $\sum_{k=1}^{n}(k+1).2^k=n.2^{n+1}$.}

       \textit{Solução}:

       Por indução sobre $n$. Para $n=1$, tem-se que
       $\sum_{k=1}^{n}(k+1).2^k=(1+1).2^1=2.2^1=4=1.2^{1+1}=n.2^{n+1}$. Seja $n\geq 1$ arbitrário.
       Suponha, como hipótese de indução, que $\sum_{k=1}^{n}(k+1).2^k=n.2^{n+1}$. Então:
       \begin{tabbing}
        xxxx\=$\sum_{k=1}^{n+1}(k+1).2^k$\=$=\sum_{k=1}^{n}(k+1).2^k + (n+2).2^{n+1}$xx\= \kill
            \>$\sum_{k=1}^{n+1}(k+1).2^k$\>$=(\sum_{k=1}^{n}(k+1).2^k) + (n+2).2^{n+1}$ \\
            \>                           \>$=n.2^{n+1} + (n+2).2^{n+1}$ \> pela hipótese de indução \\
            \>                           \>$=(n+n+2).2^{n+1}$ \\
            \>                           \>$=(2n+2).2^{n+1}$ \\
            \>                           \>$=(n+1).2^{n+2}$.
       \end{tabbing}

 \item {\footnotesize Prove que em uma sequência de dois ou mais números reais, se o último for maior ou igual ao primeiro elemento
       da sequência, então existem dois números $x$ e $y$ na sequência tais que $y$ vem imediatamente após $x$
       e $y\geq x$.}

       \textit{Solução}:

       Por indução sobre o número de elementos da sequência. Para uma sequência de dois elementos, o resultado é
       óbvio, visto que os dois elementos são consecutivos. Considere uma sequência de $n\geq 2$ elementos e suponha,
       como hipótese de indução, que se seu último elemento for maior ou igual ao primeiro, então existem dois números
       $x$ e $y$ na sequência tais que $y$ vem imediatamente após $x$ e $y\geq x$. Seja agora uma sequência de $n+1$
       elementos $k_1, k_2, \ldots, k_{n+1}$ tal que $k_{n+1}\geq k_1$. Dois casos: \\
       \textit{Caso 1}. $k_n\geq k_1$. Neste caso, pela hipótese de indução, existem $x$ e $y$ na sequência
                        dos primeiros $n$ elementos tais que $y$ vem imediatamente após $x$ e $y\geq x$. Esses mesmos
                        dois elementos satisfazem os requisitos para a sequência de $n+1$ elementos. \\
       \textit{Caso 2}. $k_n< k_1$. Segue-se, neste caso, que $k_{n+1}>k_n$. Basta pegar $x=k_n$ e $y=k_{n+1}$.

 \item {\footnotesize Para cada número inteiro positivo $n$, seja $A_n=\{1,2,\ldots,n\}$, e seja $$P_n=\{X\subseteq A_n\,|\,
       X \mbox{ não contém dois inteiros consecutivos}\}\mbox{.}$$ Por exemplo,
       $P_3=\{\emptyset,\{1\},\{2\},\{3\},\{1,3\}\}$. Prove que para todo $n$, o número de elementos em $P_n$
       é $F_{n+2}$, o $n+2$-ésimo número de Fibonacci. (Por exemplo, o número de elementos em $P_3$ é $5=F_5$.)
       \textit{Dica}: considere que elementos de $P_n$ contêm $n$ e que elementos não contêm $n$.}

       \textit{Solução}:

       Por indução sobre $n$. Seja $n\geq 1$  arbitrário. Suponha, como hipótese de indução, que para todo $0<k<n$
       $|P_k|=F_{k+2}$. Tem-se 3 casos: \\
       \textit{Caso 1}. $n=1$. Como $P_1=\{\emptyset,\{1\}\}$ e $F_3=2$, $|P_n|=F_{n+2}$. \\
       \textit{Caso 2}. $n=2$. Como $P_2=\{\emptyset,\{1\},\{2\}\}$ e $F_4=3$, $|P_n|=F_{n+2}$. \\
       \textit{Caso 3}. $n\geq 3$. $|P_n|=|P_{n-1}|+|P_{n-2}|$, visto que (a) os elementos de $P_n$ que não contêm $n$
                        são exatamente aqueles contidos em $P_{n-1}$ e (b) os elementos de $P_n$ que contêm $n$
                        não contêm $n-1$, sendo aqueles formados por algum conjunto de $P_{n-2}$ acrescido de $n$.
                        Como $0<n-1<n$ e $0<n-2<n$, segue-se pela hipótese de indução que $|P_{n-1}|=F_{n+1}$ e
                        $|P_{n-2}|=F_n$. Portanto, $|P_n|=F_{n+1}+F_{n}=F_{n+2}$.
\end{enumerate}

\end{document}
