\documentclass[11pt,a4paper]{article}

\usepackage[portuguese]{babel}
\usepackage{fullpage}

\newcounter{conta}

\begin{document}
 
\noindent Departamento de Ci\^{e}ncia da Computa\c{c}\~{a}o
\hfill ICEx/UFMG \\
{\it Matem\'{a}tica Discreta}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2005 \\
Professor: Newton Jos\'{e} Vieira \hfill nvieira@dcc.ufmg.br\\
\underline{Primeira Lista de Exerc\'{\i}cios/Solu\c c\~ao do professor}

\vspace*{4mm}
\noindent {\bf Conjuntos}
 
\vspace*{2mm}
\begin{enumerate}
 \item[1.] $A=D=G=H=\{1,3\}$, $B=E=F=\{1,2\}$ e $C=\{0,1,2\}$.

 \item[2.] Diagrama de Venn:
      \begin{center}\footnotesize
       \begin{picture}(200,200)
        \put(0,0){\framebox(200,200){}}
        \put(70,130){\oval(110,110)}
        \put(130,130){\oval(110,110)}
        \put(100,70){\oval(110,110)}

        \put(20,20){\makebox(0,0){\textbf{\#8: 8}}}
        \put(100,40){\makebox(0,0){\textbf{\#7: 8}}}
        \put(160,160){\makebox(0,0){\textbf{\#6: 10}}}
        \put(40,160){\makebox(0,0){\textbf{\#5: 12}}}
        \put(100,160){\makebox(0,0){\textbf{\#4: 5}}}
        \put(140,100){\makebox(0,0){\textbf{\#3: 8}}}
        \put(60,100){\makebox(0,0){\textbf{\#2: 6}}}
        \put(100,100){\makebox(0,0){\textbf{\#1: 3}}}

        \put(17,125){\makebox(0,0)[l]{\normalsize\textbf{C}}}
        \put(183,125){\makebox(0,0)[r]{\normalsize\textbf{N}}}
        \put(100,17){\makebox(0,0)[b]{\normalsize\textbf{D}}}
       \end{picture}
      \end{center}
      S\~ao dados: $|U|=60$, $|D|=25$, $|N|=26$, $|C|=26$,
      $|D\cap C|=9$, $|D\cap N|=11$, $|N\cap C|=8$ e $|D\cap N\cap C|=3$,
      sendo $U$ o conjunto das pessoas, $D$ o conjunto das que assistem
      Discovery, $N$ o das que assistem National Geographic e $C$ o das
      que assistem Cultura.
      C\'alculo do n\'umero de espectadores por regi\~ao do diagrama:
      \begin{enumerate}
       \item[\ ] $N(\#1)=|D\cap N\cap C|=3$ (dado).
       \item[\ ] $N(\#2)=|D\cap C|-N(\#1)=9-3=6$.
       \item[\ ] $N(\#3)=|D\cap N|-N(\#1)=11-3=8$.
       \item[\ ] $N(\#4)=|N\cap C|-N(\#1)=8-3=5$.
       \item[\ ] $N(\#5)=|C|-N(\#1)-N(\#2)-N(\#4)=26-3-6-5=12$.
       \item[\ ] $N(\#6)=|N|-N(\#1)-N(\#3)-N(\#4)=26-3-8-5=10$.
       \item[\ ] $N(\#7)=|D|-N(\#1)-N(\#2)-N(\#3)=25-3-6-8=8$.
       \item[\ ] $N(\#8)=|U|-N(\#1)-N(\#2)-N(\#3)-N(\#4)-N(\#5)-N(\#6)-N(\#7)=
                 60-3-6-8-5-12-10-8=8$.
      \end{enumerate}

%      Schaum: 1.14(a), pag. 16

 \item[3.] As 5 parti\c c\~oes do conjunto $\{a,b,c\}$:
       \begin{center}
       \begin{tabular}{ccc}
                                & $\{\{a\},\{b,c\}\}$  \\
        $\{\{a\},\{b\},\{c\}\}$ & $\{\{b\},\{a,c\}\}$ & $\{\{a,b,c\}\}$\\
                                & $\{\{c\},\{a,b\}\}$
       \end{tabular}
       \end{center}

%      Schaum: 1.23, pag. 19
\end{enumerate}

\vspace*{4mm}
\noindent {\bf Rela\c c\~oes}

\vspace*{2mm}
\begin{enumerate}
 \item[4.] 
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item N\~ao \'e reflexiva, pois um aluno ou aluna n\~ao \'e ``irm\~a''
              de si pr\'oprio. N\~ao \'e sim\'etrica, pois, dados dois alunos $x$ e $y$
              tais que $x$ \'e irm\~a de $y$, se $y$ for do sexo masculino, n\~ao se
              pode dizer que $y$ \'e irm\~a de $x$. Na UFMG existem dois alunos
              do sexo feminino que s\~ao irm\~aos (chamemo-las de $a$ e $b$);
              logo, a rela\c c\~ao n\~ao \'e transitiva, pois, se fosse, dado que
              $a$ \'e irm\~a de $b$ e $b$ \'e irm\~a de $a$, $a$ seria (por
              transitividade) irm\~a de $a$!

%             Townsend: A.2.2, ex. 2, pag. 338
        \item \'E reflexiva: $A\subseteq A$ para todo conjunto $A\in {\cal P}(X)$. N\~ao
              \'e sim\'etrica: se $A\subseteq B$, n\~ao necessariamente $B\subseteq A$; na
              verdade, $A\subseteq B$ e $B\subseteq A$ somente no caso em que $A=B$.
              \'E transitiva: se $A\subseteq B$ e $B\subseteq C$, ent\~ao $A\subseteq C$
              para quaisquer $A,B,C\subseteq X$.

%             Townsend: A.2.2, ex. 3, pag. 338
        \item N\~ao \'e reflexiva, visto que, sendo $X\not=\emptyset$, nunca se tem
              $A=\overline{A}$ (observe que $X$ \'e o universo em considera\c c\~ao).
              \'E sim\'etrica: dados $A$ e $B$ tais que $A=\overline{B}$, tem-se que
              $\overline{A}=\overline{\overline{B}}$, ou seja, $B=\overline{A}$.
              N\~ao \'e transitiva: sejam $A$, $B$ e $C$ tais que $A=\overline{B}$ e
              $B=\overline{C}$; desta \'ultima tem-se que $\overline{B}=C$ e,
              portanto (j\'a que $A=\overline{B}$), $A=C$; ora, se a rela\c c\~ao
              fosse transitiva, ter-se ia tamb\'em que $A=\overline{C}$, o que
              implicaria que $C=\overline{C}$!

%             Townsend: A.2.2, ex. 4, pag. 338
        \item N\~ao \'e reflexiva, pois $0$ n\~ao \'e divis\'{\i}vel por $0$. N\~ao
              \'e sim\'etrica, pois $4$ \'e divis\'{\i}vel por $2$ e $2$ n\~ao
              \'e divis\'{\i}vel por $4$. \'E transitiva, pois, para quaisquer
              n\'umero naturais $x$, $y$ e $z$, se $y$ \'e divis\'{\i}vel por $x$
              ($y=qx$), e $z$ \'e divis\'{\i}vel por $y$ ($z=ry$), ent\~ao $z$
              \'e divis\'{\i}vel por $x$ ($z=qrx$).

%             Townsend: A.2.2, ex. 5, pag. 338
       \end{list}

 \item[5.] 
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item S\~ao 366 classes de equival\^encia induzidas por $R_1$, uma para cada
              data poss\'{\i}vel de anivers\'ario. Por exemplo, para a data
              ``$1^{\underline{\circ}}$ de janeiro'', existe a classe $\{x\in B\,\,|\,\, x$
              nasceu em $1^{\underline{\circ}}$ de janeiro$\}$.

        \item Como $x-y \mbox{ mod } 10=0$ se, e somente se, $x \mbox{ mod } 10=
              y \mbox{ mod } 10$, existem 10 classe de equival\^encia induzidas por
              $R_2$, uma para cada resto da divis\~ao por 10. A classe de equival\^encia
              para o resto $r$ \'e constitu\'{\i}da dos n\'umeros naturais $n$ tais
              que $n \mbox{ mod }10=r$.
       \end{list}
\end{enumerate}

\vspace*{4mm}
\noindent {\bf Fun\c c\~oes}

\vspace*{2mm}
\begin{enumerate}
 \item[6.] Fun\c c\~oes de {\bf N} para {\bf N}:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Injetora, mas n\~ao sobrejetora: $f(n)=2n$. \'E injetora, pois
              se $n_1\not=n_2$, ent\~ao $2n_1\not=2n_2$. N\~ao \'e sobrejetora,
              pois se $n$ \'e \'{\i}mpar, n\~ao existe $k$ tal que $2k=n$.
        \item Sobrejetora, mas n\~ao injetora: $g(n)=n/2$ se $n$ for par, e
              $g(n)=(n-1)/2$ se $n$ for \'{\i}mpar. \'E sobrejetora, pois
              para qualquer n\'umero $n$, $g(2n)=n$. N\~ao \'e injetora,
              j\'a que $g(n)=g(n+1)=n/2$, sendo $n$ par.
        \item Nem injetora, nem sobrejetora: $h(n)=n$ se $n$ for par, e
              $h(n)=n-1$ se $n$ for \'{\i}mpar. N\~ao \'e injetora, j\'a que
              $h(n)=h(n+1)=n$ para qualquer n\'umero $n$; e n\~ao \'e sobrejetora,
              j\'a que n\~ao existe $n$ tal que $h(n)=k$, para qualquer n\'umero
              \'{\i}mpar $k$.
       \end{list}

%      Townsend: A.2.2, ex. 14, pag. 338

 \item[7.] $f: \textbf{N}\rightarrow \textbf{N}$ tal que $f(n)=n+1$ \'e
         uma fun\c c\~ao bijetora do conjunto dos n\'umeros naturais pares
         para o dos n\'umeros naturais \'{\i}mpares, j\'a que: (1) \'e injetora,
         pois $n_1+1\not=n_2+1$ se $n_1\not=n_2$; (2) \'e sobrejetora,
         pois, para qualquer n\'umero \'{\i}mpar $n$, $f(n-1)=n$.

%      Townsend: A.2.2, ex. 15, pag. 339
\end{enumerate}

\pagebreak
\noindent {\bf Prova de Teoremas}

\vspace*{2mm}
\begin{enumerate}
 \item[8.] Hip\'otese: $A-B\subseteq C\cap D$ e $a\in A$.

       Suponha que $a\not\in B$. Como $a\in A$, segue-se que $a\in A-B$; e como
       $A-B\subseteq C\cap D$, ent\~ao $a\in C\cap D$. Portanto, $a\in D$.
       Conclui-se, ent\~ao, que se $a\not\in D$, ent\~ao $a\in B$.
 %     Velleman: 3.1, ex. 4, pag. 92

 \item[9.] Hip\'otese: $x$ \'e um n\'umero real e $x\not=4$.

       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item A ``demonstra\c c\~ao'' mostra a rec\'{\i}proca do que deveria
             ser provado, ou seja: se $x=7$, ent\~ao $(2x-5)/(x-4)=3$.
        \item Demonstra\c c\~ao correta: Supponha que $(2x-5)/(x-4)=3$. Como $x\not=4$,
              $2x-5=3(x-4)$. Assim,  $2x-5=3x-12$ e, portanto, $x=7$. Conclui-se
              que se $(2x-5)/(x-4)=3$, ent\~ao $x=7$.
       \end{list}

 %     Velleman: 3.1, ex. 10, pag. 92

 \item[10.] Hip\'otese: $A-B\subseteq C$, e $x$ \'e um elemento qualquer no universo.

       Suponha que $x\in A-C$ e $x\not\in B$. Como $x\in A-C$, $x\in A$ e $x\not\in C$.
       De $x\in A$ e $x\not\in B$, segue-se que $x\in A-B$; dado que $A-B\subseteq C$,
       tem-se, ent\~ao, que $x\in C$. Contradi\c c\~ao! Logo n\~ao pode ser o caso que
       $x\in A-C$ e $x\not\in B$; conclui-se que se $x\in A-C$, ent\~ao $x\in B$.

 %     Velleman: teorema, pag. 99

 \item[11.] Suponha que $n$ \'e um n\'umero inteiro n\~ao divis\'{\i}vel por 3. Sendo
       assim, existe um n\'umero inteiro $q$ tal que $n=3q+1$ ou $n=3q+2$. No
       primeiro caso, tem-se que $n^2=(3q+1)^2=9q^2+6q+1=3(3q^2+2q)+1$; portanto,
       $n^2=3k+1$ para um inteiro $k=3q^2+2q$. No segundo caso, $n^2=(3q+2)^2=
       9q^2+12q+4=3(3q^2+4q+1)+1$; portanto, $n^2=3k+1$ para um inteiro $k=3q^2+4q+1$.
       Assim, em qualquer caso existe um inteiro $k$ tal que  $n^2=3k+1$.
       Conclui-se que se $n$ \'e um n\'umero inteiro n\~ao divis\'{\i}vel por 3,
       ent\~ao $n^2=3k+1$ para algum um inteiro $k$.

 \item[12.]
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Seja $x$ um elemento arbitr\'ario.
              \begin{tabbing}
               $x\in \overline{A\cup B}$ \=$\Leftrightarrow x\in \overline{A}$ e $x\in \overline{B}$ xxx\= \kill
               $x\in \overline{A\cup B}$ \>$\Leftrightarrow x\not\in A\cup B$ \> pela defini\c c\~ao de complemento\\
                        \>$\Leftrightarrow x\not\in A$ e $x\not\in B$ \> pela defini\c c\~ao de uni\~ao\\
                        \>$\Leftrightarrow x\in \overline{A}$ e $x\in \overline{B}$ \> pela defini\c c\~ao de complemento \\
                        \>$\Leftrightarrow x\in \overline{A}\cap\overline{B}$ \> pela defini\c c\~ao de interse\c c\~ao
              \end{tabbing}
              Assim, para todo $x$, $x\in \overline{A\cup B}$ se, e somente se,
              $x\in\overline{A}\cap\overline{B}$.
              Portanto, $\overline{A\cup B}=\overline{A}\cap\overline{B}$.
        \item Seja $x$ um elemento arbitr\'ario.
              \begin{tabbing}
               $x\in \overline{A\cap B}$ \=$\Leftrightarrow x\in \overline{A}$ ou $x\in \overline{B}$ xxx\= \kill
               $x\in \overline{A\cap B}$ \>$\Leftrightarrow x\not\in A\cap B$ \> pela defini\c c\~ao de complemento\\
                        \>$\Leftrightarrow x\not\in A$ ou $x\not\in B$ \> pela defini\c c\~ao de interse\c c\~ao\\
                        \>$\Leftrightarrow x\in \overline{A}$ ou $x\in \overline{B}$ \> pela defini\c c\~ao de complemento \\
                        \>$\Leftrightarrow x\in \overline{A}\cup\overline{B}$ \> pela defini\c c\~ao de uni\~ao
              \end{tabbing}
              Assim, para todo $x$, $x\in \overline{A\cap B}$ se, e somente se,
              $x\in\overline{A}\cup\overline{B}$.
              Portanto,  $\overline{A\cap B}=\overline{A}\cup\overline{B}$.
       \end{list}

%      Townsend: A.2.1, ex. 6, pag. 333

 \item[13.] Seja um conjunto arbitr\'ario $X\in {\cal P}(A)\cup{\cal P}(B)$. Ent\~ao $X\in {\cal P}(A)$
       ou $X\in {\cal P}(B)$. No primeiro caso, $X\subseteq A$ e, portanto, $X\subseteq A\cup B$.
       No segundo, como $X\subseteq B$, tem-se tamb\'em que $X\subseteq A\cup B$. Assim, em
       qualquer caso, $X\subseteq A\cup B$ e, portanto, $X\in {\cal P}(A\cup B)$. Como $X$
       \'e um elemento arbitr\'ario de ${\cal P}(A)\cup{\cal P}(B)$, conclui-se que
       ${\cal P}(A)\cup{\cal P}(B)\subseteq {\cal P}(A\cup B)$.

       
       Nem sempre ${\cal P}(A\cup B)\subseteq {\cal P}(A)\cup{\cal P}(B)$. Por exemplo,
       se $A=\{a\}$ e $B=\{b\}$, ent\~ao ${\cal P}(A\cup B)=\{\emptyset,\{a\},\{b\},\{a,b\}\}$
       e ${\cal P}(A)\cup{\cal P}(B)=\{\emptyset,\{a\}\}\cup\{\emptyset,\{b\}\}=\{\emptyset,\{a\},\{b\}\}$.

%      Townsend: A.2.1, ex. 14, pag. 334

 \item[14.] 
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Fa\c ca corresponder a cada casal uma casa de pombos, e a cada pessoa escolhida
              para a cole\c c\~ao um pombo. Ent\~ao, pelo princ\'{\i}pio da casa de pombos,
              em todas as escolhas poss\'{\i}veis de $n+1$ pessoas, pelo menos um casal \'e
              repetido (correspondendo \`a escolha do casal para a cole\c c\~ao).
        \item Este s\'o tem sentido com $n>1$ computadores.
             
              Suponha que exista um computador n\~ao conectado ao outro; neste caso,
              cada computador s\'{o} pode estar conectado com  0 a $n-2$ outros
              (nenhum computador est\'a conectado a ele mesmo nem \`aquele que n\~ao
              esteja conectado). Por outro lado, se todo  computador est\'a conectado
              com algum outro, ent\~{a}o cada um pode estar conectado com 1 a $n-1$
              outros. Nos dois casos, pelo princ\'{\i}pio da casa de pombos, existem
              2 computadores conectados ao mesmo n\'{u}mero de computadores.

       \end{list}
\end{enumerate}

\vspace*{4mm}
\noindent {\bf Indu\c c\~ao Matem\'atica}

\vspace*{2mm}
\begin{enumerate}
\item[15.] 
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\sum_{k=0}^{0}(k2^k)=02^0=0$. E $(0-1)2^{0+1}+2=-2+2=0$. Seja $n\in\textbf{N}$.
              Suponha, como hip\'otese de indu\c c\~ao, que
              $\sum_{k=0}^{n}(k2^k)=(n-1)2^{n+1}+2$. Basta, ent\~ao, mostrar que
              $\sum_{k=0}^{n+1}(k2^k)=n2^{n+2}+2$. De fato:
              $\sum_{k=0}^{n+1}(k2^k)=\sum_{k=0}^{n}(k2^k)+(n+1)2^{n+1}=
              (n-1)2^{n+1}+2+(n+1)2^{n+1}$, pela hip\'otese de indu\c c\~ao,
              e esta \'ultima \'e igual a $(n-1+n+1)2^{n+1}+2=n2^{n+2}+2$.

        \item $\sum_{i=0}^{0}(0\times 0!)=0=1-1=(0+1)!-1$. Seja $n\geq 0$.
              Suponha, como hip\'otese de indu\c c\~ao, que 
              $\sum_{i=0}^{n}(i\times i!)=(n+1)!-1$. Tem-se:
              $\sum_{i=0}^{n+1}(i\times i!)=\sum_{i=0}^{n}(i\times i!) + (n+1)\times (n+1)!
              =(n+1)!-1+(n+1)\times (n+1)!$, pela hip\'otese de indu\c c\~ao.
              E $(n+1)!-1+(n+1)\times (n+1)!=(n+2)(n+1)!-1=(n+2)!-1$. Portanto,
              pelo princ\'{\i}pio de indu\c c\~ao, $\sum_{i=0}^{n}(i\times i!)=(n+1)!-1$
              para todo $n\geq 0$.

        \item $0^3-0=0$ que \'e divis\'{\i}vel por 3. Seja $n$ um n\'umero natural
              arbitr\'ario. Suponha, como hip\'otese de indu\c c\~ao, que 
              $n^3-n$ \'e divis\'{\i}vel por 3. Resta mostrar que
              $(n+1)^3-(n+1)$ \'e divis\'{\i}vel por 3. Tem-se:
              $(n+1)^3-(n+1)=n^3+3n^2+3n+1-n-1=(n^3-n)+3n^2+3n$. Isto \'e
              divis\'{\i}vel por 3, visto que $n^3-n$ \'e divis\'{\i}vel por 3,
              pela hip\'otese de indu\c c\~ao, e que $3n^2+3n$ tamb\'em \'e,
              o que completa a prova.

 %      Velleman: Exemplo 6.1.2, pag. 248

        \item No caso de $3$ pontos, o pol\'{\i}gono \'e um tri\^angulo, e sabe-se que
              a soma dos \^angulos internos de um tri\^angulo \'e $180^\circ=(3-2)180^\circ$.
              Seja um n\'umero natural $n\geq 3$. Suponha, como hip\'otese de indu\c c\~ao,
              que se $n$ pontos distintos sobre um
              c\'{\i}rculo s\~ao conectados consecutivamente com segmentos
              de reta, ent\~ao a soma dos \^angulos internos do pol\'{\i}gono
              resultante \'e $(n-2)180^\circ$.
              Sejam $n+1$ pontos distintos sobre um
              c\'{\i}rculo conectados consecutivamente com segmentos de reta. Deve-se
              mostrar que a soma dos \^angulos internos do pol\'{\i}gono
              resultante \'e $((n+1)-2)180^\circ=(n-1)180^\circ$. Seja o pol\'{\i}gono de
              $n$ pontos resultante de se retirar 1 ponto qualquer do
              pol\'{\i}gono de $n+1$ pontos. Pela hip\'otese de indu\c c\~ao,
              ele tem a soma dos \^angulos internos igual a $(n-2)180^\circ$. A soma dos
              \^angulos internos do pol\'{\i}gono de $n+1$ pontos \'e igual ao de
              $n$ pontos mais os \^angulos internos do tri\^angulo cujos v\'ertices s\~ao
              o ponto retirado mais os dois adjacentes a ele, ou seja,
              $(n-2)180+180=(n-2+1)180=(n-1)180^\circ$. Isto conclui a demonstra\c c\~ao.
       \end{list} 

 \item[16.] 
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item   Observe, inicialmente, que $F_1=1$ e 
                $\frac{1}{\sqrt{5}}\left( \frac{1+\sqrt{5}}{2}\right)^1-
                \frac{1}{\sqrt{5}}\left( \frac{1-\sqrt{5}}{2}\right)^1=1$, e tamb\'em que
                $F_2=1$ e $\frac{1}{\sqrt{5}}\left( \frac{1+\sqrt{5}}{2}\right)^2-
                \frac{1}{\sqrt{5}}\left( \frac{1-\sqrt{5}}{2}\right)^2=1$.
                Seja $k\geq 2$. 
                Suponha, como hip\'otese de indu\c c\~ao, que o enunciado seja
                verdadeiro para $1\leq n \leq k$. Como $k+1\geq 3$, tem-se que, por
                defini\c c\~ao, $F_{k+1}=F_{k}+F_{k-1}$. Aplicando-se a
                hip\'otese de indu\c c\~ao, tem-se ent\~ao que:
                \[F_{k+1}=\frac{1}{\sqrt{5}}\left( \frac{1+\sqrt{5}}{2}\right)^k-
                \frac{1}{\sqrt{5}}\left( \frac{1-\sqrt{5}}{2}\right)^k +
                \frac{1}{\sqrt{5}}\left( \frac{1+\sqrt{5}}{2}\right)^{k-1}-
                \frac{1}{\sqrt{5}}\left( \frac{1-\sqrt{5}}{2}\right)^{k-1}\]
                e, portanto,
                \[F_{k+1}=\frac{1}{\sqrt{5}}\left( \frac{1+\sqrt{5}}{2}\right)^{k-1}
                \left(1+\frac{1+\sqrt{5}}{2}\right)
                -
                \frac{1}{\sqrt{5}}\left( \frac{1-\sqrt{5}}{2}\right)^{k-1}
                \left(1+\frac{1-\sqrt{5}}{2}\right)\]
                \'E f\'acil verificar que:
                \[1+\frac{1+\sqrt{5}}{2} =
                \left( \frac{1+\sqrt{5}}{2}\right)^2 \mbox{ e }
                1+\frac{1-\sqrt{5}}{2} =
                \left( \frac{1-\sqrt{5}}{2}\right)^2\]
                e, portanto,
                \[F_{k+1}=\frac{1}{\sqrt{5}}\left( 
                \frac{1+\sqrt{5}}{2}\right)^{k+1}-
                \frac{1}{\sqrt{5}}\left(
                 \frac{1-\sqrt{5}}{2}\right)^{k+1}\mbox{.}\]
                o que conclui a demonstra\c c\~ao.

        \item $\sum_{i=1}^1F_i=F_1=1=2-1=F_3-1$. Seja $n\geq 1$, e suponha,
              como hip\'otese de indu\c c\~ao, que $\sum_{i=1}^nF_i=F_{n+2}-1$.
              Segue-se que $\sum_{i=1}^{n+1}F_i=\sum_{i=1}^nF_i + F_{n+1}=
              F_{n+2}-1+F_{n+1}$, pela hip\'otese de indu\c c\~ao. Como $n\geq 1$,
              a defini\c c\~ao diz que $F_{n+2}+F_{n+1}=F_{n+3}$. Portanto,
              $\sum_{i=1}^{n+1}F_i=F_{n+3}-1$. Isto conclui a prova.
              
        \item $F_1=1<7/4$ e $F_2=1<49/16=(7/4)^2$. Seja $n\geq 2$. Suponha, como
              hip\'otese de indu\c c\~ao, que $F_k<(7/4)^k$ para $1\leq k\leq n$.
              Tem-se: $F_{n+1}=F_n+F_{n-1}$, pela defini\c c\~ao, j\'a que $n\geq 2$.
              Pela hip\'otese de indu\c c\~ao, $F_n<(7/4)^n$ e $F_{n-1}<(7/4)^{n-1}$.
              Logo, $F_{n+1}<(7/4)^n+(7/4)^{n-1}$, ou seja,
              $F_{n+1}<(7/4)^{n-1}((7/4)+1)$. Como $(7/4)+1=11/4=44/16$ e
              $(44/16)<(49/16)=(7/4)^2$, segue-se que $(7/4)^{n-1}((7/4)+1)<
              (7/4)^{n-1}(7/4)^2=(7/4)^{n+1}$. Portanto, $F_{n+1}<(7/4)^{n+1}$.

        \item $\sum_{i=1}^1(F_i)^2=F_1^2=1^2=1=1\times 1=F_1F_2$. Seja $n\geq 1$.
              Suponha, como hip\'otese de indu\c c\~ao, que $\sum_{i=1}^n(F_i)^2=
              F_{n}F_{n+1}$. Tem-se, ent\~ao: $\sum_{i=1}^{n+1}
              (F_i)^2=\sum_{i=1}^n(F_i)^2 + (F_{n+1})^2$. Pela hip\'otese de indu\c c\~ao,
              segue-se que $\sum_{i=1}^{n+1}(F_i)^2=F_{n}F_{n+1}+(F_{n+1})^2=
              F_{n+1}(F_{n+1}+F_{n})$. Como $n\geq 1$, $F_{n+1}+F_{n}=F_{n+2}$ e, portanto,
              $\sum_{i=1}^{n+1}(F_i)^2=F_{n+1}F_{n+2}$, o que conclui a
              demonstra\c c\~ao.
       \end{list}

\end{enumerate}
 
\end{document}

 



