\documentclass[a4paper,12pt,brazil,landscape]{article}
\newcommand{\ultimamodificacao}{11 de setembro de 2007}
\usepackage[latin1]{inputenc}
\usepackage[brazil]{babel}
\usepackage{epsfig,graphicx,color,latexsym,alltt,calc,ifthen,slides,hyperref} 
 
\newcounter{conta}
\newcounter{conta2} 
 
\begin{document}

\setbackgroundcolor{white}
\settextcolor{blue}
\setslidetitlecolor{red}
\setbordercolor{darkblue}

\setedition{slides.sty}
\newincluder{fulledition}
\setincluder{fulledition}{true}

\sffamily 
\bfseries 
\mathversion{bold}
\Hugesize 
%\Hugefont

\hypertarget{inicio}{}
\title{Indu\c{c}\~ao Matem\'atica \\ Baseado em Townsend (1987), Cap. 1}
\author{Newton José Vieira}
\lhead{Matemática Discreta}
\rhead{Capítulo 1}
\lfoot{UFMG}
%\rfoot{rsb}
\organization{UFMG}
\cfoot{\hyperlink{inicio}{\threebigotimes}~~~\hyperlink{sumario}{\threebigoplus}}
\date{\ultimamodificacao}
\titlepage

%\newslide{SUMÁRIO}
\hypertarget{sumario}{}
%\begin{twoblocks}
%\begin{itemize}
%\item \hyperlink{introducao}{Introdução}
%\item \hyperlink{inducao-forte-1}{Princípio da Indução Matemática Forte}
%\end{itemize}
%\centralbar{13cm}
%\begin{itemize}
%\item \hyperlink{comandos}{Comandos Especiais}
%\end{itemize}
%\end{twoblocks}

\pagenumbering{arabic}

%--------------------------------------------------------------------------------------------

%\section{INTRODUÇÃO}
\hypertarget{introducao}{}
\setskiplink{capitulo1}

\newslide{Um Algoritmo de Ordenação}

\begin{Algorithm}
  Entrada: um vetor v com n n\'{u}meros inteiros.
  Sa\'{\i}da: o mesmo vetor em ordem crescente.

  para i de 1 a n-1 faça
    menor := v[i]; m := i;
    para j de i+1 a n faça
      se \textcolor{red}{v[j] < menor} ent\~{a}o
        menor := v[j]; m := j;
      fimse
    fimpara;
    v[i] :=: v[m]  \{\str{troca valores de v[i] e v[m]}\}
  fimpara
\end{Algorithm}


%--------------------------------------------------------------------------------------------

\newslide{O Desempenho do Algoritmo}

\begin{itemize}
 \item Número de comparações:
       \begin{quote}
        $NC(n)=(n-1)+(n-2)+\cdots+1$.
       \end{quote}
\end{itemize}


%--------------------------------------------------------------------------------------------

\newslide{O Desempenho do Algoritmo}

\begin{itemize}
 \item Número de comparações:
       \begin{quote}
        $NC(n)=(n-1)+(n-2)+\cdots+1$.
       \end{quote}

\vspace*{3mm}
 \item Uma maneira de achar uma fórmula para $NC(n)$:
       \begin{enumerate}
        \item Conjecturar uma fórmula $f(n)$.
        \item Provar que
              \begin{quote}
               $\forall n\in\mbox{\bf N}\,\, NC(n)=f(n)$
              \end{quote}
              usando \textcolor{black}{indução matemática}.
       \end{enumerate}
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{A \aspas lógica\aspas da indução matemática}


\noindent Para provar $\forall x \,P(x)$, quando o universo \'{e} \textcolor{black}{N}:

\begin{itemize}
 \item \underline{Base lógica}:
       \begin{quote}
        $P(0)\wedge\forall x \,(P(x)\Rightarrow P(x+1))\models \forall x\, P(x)$.
       \end{quote}
 \item \underline{M\'{e}todo}:
       \begin{enumerate}
        \item \underline{Passo base}: provar $P(0)$;
        \item \underline{Passo da indução}: provar
              $\forall x \,(P(x)\Rightarrow P(x+1))$.
       \end{enumerate}
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{Princípio da Indução Matemática (Fraca)}

\begin{itemize}
 \item Para provar $\forall n \,P(n)$ para todo $n\geq q$, é suficiente mostrar que:

      \begin{enumerate}
       \item $P(q)$ é verdadeira;
       \item se $k\geq q$ e se $P(k)$ é verdadeira, \\
             então $P(k+1)$ também é verdadeira.
      \end{enumerate}
\end{itemize}

%-------------------------------------------------------------------------------------------

\newslide{Princípio da Indução Matemática (Fraca)}

\begin{itemize}
 \item Para provar $\forall n \,P(n)$ para todo $n\geq q$, é suficiente mostrar que:

      \begin{enumerate}
       \item $P(q)$ é verdadeira;
       \item se $k\geq q$ e se $P(k)$ é verdadeira, \\
             então $P(k+1)$ também é verdadeira.
      \end{enumerate}
\end{itemize}

\vspace*{3mm}
\begin{itemize}
 \item Passo 1: \textcolor{red}{passo base}.
 \item Passo 2: \textcolor{red}{passo da indução}.
 \item A suposição que $P(k)$ é verdadeira no \textcolor{red}{passo da indução}:
       \begin{quote}
        \textcolor{red}{hipótese de indução}.
       \end{quote}
\end{itemize}

%-------------------------------------------------------------------------------------------


\newslide{Exemplos}

\begin{itemize}
 \item $\sum_{k=1}^n k=n(n+1)/2$.
 \item $\sum_{k=1}^n 1/[k(k+1)]=n/(n+1)$.
 \item Qualquer postagem maior ou igual a 8 centavos pode ser feita utilizando
       apenas selos de 3 e de 5 centavos.
 \item Existem $2^n$ sequ\^{e}ncias bin\'{a}rias de $n$ d\'{\i}gitos.
 \item Sejam $n$ retas dividindo o plano em regiões. É possível pintar as
       regiões com as cores preta e branca de forma que regiões adjacentes
       não fiquem com a mesma cor.
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{Princípio da Indução Matemática (Forte)}

\begin{itemize}
 \item Para provar $\forall n \,P(n)$ para todo $n\geq q$, é suficiente mostrar que:

      \begin{enumerate}
       \item $P(i)$ é verdadeira para $q\leq i\leq r$;
       \item se $k\geq r$ e se $P(i)$ é verdadeira para $i\leq k$, \\
             então $P(k+1)$ também é verdadeira.
      \end{enumerate}
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{Princípio da Indução Matemática (Forte)}

\begin{itemize}
 \item Para provar $\forall n \,P(n)$ para todo $n\geq q$, é suficiente mostrar que:

      \begin{enumerate}
       \item $P(i)$ é verdadeira para $q\leq i\leq r$;
       \item se $k\geq r$ e se $P(i)$ é verdadeira para $i\leq k$, \\
             então $P(k+1)$ também é verdadeira.
      \end{enumerate}
\end{itemize}

\vspace*{3mm}
\begin{itemize}
 \item Passo 1: \textcolor{red}{passo base}.
 \item Passo 2: \textcolor{red}{passo da indução}.
 \item A suposição que $P(i)$ é verdadeira para $i\leq k$:
       \begin{quote}
        \textcolor{red}{hipótese de indução}.
       \end{quote}
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{Exemplos}

\begin{itemize}
 \item Qualquer n\'{u}mero natural maior que 1 pode pode ser fatorado como um
       produto de primos.

 \item Seja a seq\"u\^{e}ncia de Fibonacci, definida por:
       \begin{quote}
        $a_1=1$, $a_2=1$, e $a_n = a_{n-1}+a_{n-2}$ para $n\geq 3$.
       \end{quote}
       Esta é uma definição \textcolor{red}{recursiva} ou \textcolor{red}{indutiva}.

\vspace{3mm}
       \begin{quote}
        Para $n \geq 1$, $a_n\leq [(1+\sqrt{5})/2]^n$.
       \end{quote}
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{Uma demonstração incorreta}

\textcolor{black}{Teorema:} ``Em uma cole\c{c}\~{a}o de $n$ bolas, todas s\~{a}o da mesma cor''.

\textcolor{black}{Prova:}

Evidentemente, se a cole\c{c}\~{a}o tem apenas uma bola, toda bola tem a mesma cor. Seja $n\geq 1$.
Hip\'{o}tese de indu\c{c}\~{a}o: em uma cole\c{c}\~{a}o de $n$ bolas todas têm a mesma cor.
Seja, ent\~{a}o, uma cole\c{c}\~{a}o de $n+1$ bolas. Observe a
seguinte figura ilustrando as $n+1$ bolas:
\begin{center}
\begin{picture}(170,60)
 \put(10,30){\circle{10}}
 \put(40,30){\circle{10}}
 \put(70,30){\circle{10}}
 \put(100,30){\makebox(0,0){$\cdots$}}
 \put(130,30){\circle{10}}
 \put(160,30){\circle{10}}

 \put(4,47){\line(0,-1){4}} 
 \put(136,47){\line(0,-1){4}} 
 \put(60,45){\vector(-1,0){55}}
 \put(70,45){\makebox(0,0){$n$}}
 \put(80,45){\vector(1,0){55}}
 
 \put(34,17){\line(0,-1){4}} 
 \put(166,17){\line(0,-1){4}} 
 \put(90,15){\vector(-1,0){55}}
 \put(100,15){\makebox(0,0){$n$}}
 \put(110,15){\vector(1,0){55}}
\end{picture}
\end{center}
Pela hip\'{o}tese de indu\c{c}\~{a}o, as primeiras $n$ bolas t\^{e}m a mesma cor,
assim como as $n$ \'{u}ltimas. Como as bolas na \underline{\bf interse\c{c}\~{a}o}
têm a mesma cor, as $n+1$ bolas t\^{e}m a mesma cor.

\vspace*{4mm}
\noindent {\textcolor{red}{Qual o problema com esta prova?}}

%--------------------------------------------------------------------------------------------

%--------------------------------------------------------------------------------------------

\defskiptarget{capitulo1}

\lastpage 

\end{document}