\documentclass[a4paper,12pt,brazil,landscape]{article}
\newcommand{\ultimamodificacao}{30 de agosto 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{definicao-recursiva-1}{Definição Recursiva}
\item \hyperlink{inducao-fraca-1}{Princípio da Indução Matemática Fraca}
\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}

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

\newslide{DEFINIÇÃO RECURSIVA (1)}
\hypertarget{definicao-recursiva-1}{}
\setskiplink{capitulo1}

\noindent {\bf Defini\c{c}\~{a}o Recursiva} de um conjunto $X$:

\vspace*{5mm}
\begin{list}{(\alph{conta})}{\usecounter{conta}}
 \item BASE: explicitar um conjunto $B_0 \subset X$;
 \item PASSO RECURSIVO: mostrar como obter \underline{novos elementos} de $X$,
       pela aplica\c{c}\~{a}o de certas opera\c{c}\~{o}es a elementos de $X$;
 \item FECHAMENTO: dizer que um objeto pertence a $X$ \underline{somente se}
       poder ser obtido como especificado em (a) e (b).      
\end{list}

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

\newslide{DEFINIÇÃO RECURSIVA (2)}
\hypertarget{definicao-recursiva-2}{}


\noindent \underline{Exemplo}:

\vspace*{5mm}
\noindent O conjunto dos n\'{u}meros naturais, {\bf N}, pode ser assim definido:

\begin{list}{(\alph{conta})}{\usecounter{conta}}
 \item $0 \in \mbox{\bf N}$;
 \item se $n \in \mbox{\bf N}$ ent\~{a}o $n+1 \in \mbox{\bf N}$;
 \item s\'{o} pertencem a {\bf N} os n\'{u}meros que podem ser obtidos como especificado
       em (a) e (b).
\end{list}

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

\newslide{DEFINIÇÃO RECURSIVA (3)}
\hypertarget{definicao-recursiva-3}{}


\noindent \underline{Outros exemplos}:

\vspace*{5mm}
\begin{itemize}
 \item O conjunto das {\bf express\~{o}es posfixadas} sobre {\bf N}, pode ser
       assim definido:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item a representa\c{c}\~{a}o decimal de qualquer n\'{u}mero natural \'{e} uma express\~{a}o
              posfixada;
        \item se $e_1$ e $e_2$ s\~{a}o express\~{o}es posfixadas e $p \in \{+, -, \times\}$,
              ent\~{a}o $e_1 e_2 p$ \'{e} uma express\~{a}o posfixada;
        \item s\'{o} s\~{a}o express\~{o}es posfixadas aquelas que podem ser obtidas como
              especificado em (a) e (b).
       \end{list}

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

\newslide{DEFINIÇÃO RECURSIVA (4)}
\hypertarget{definicao-recursiva-4}{}


\item O {\bf fatorial} de $n$, $n!$, \'{e} definido recursivamente assim: 

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $0! = 1$;
        \item $(n+1)! = (n+1)(n!)$.
       \end{list}

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

\newslide{DEFINIÇÃO RECURSIVA (5)}
\hypertarget{definicao-recursiva-5}{}


 \item $\sum_{k=0}^nf(k)$ \'{e} definido recursivamente assim: 

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\sum_{k=0}^0f(k) = f(0)$;
        \item $\sum_{k=0}^{n+1}f(k) = (\sum_{k=0}^{n}f(k))+f(n+1)$. 
       \end{list}

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

\newslide{DEFINIÇÃO RECURSIVA (6)}
\hypertarget{definicao-recursiva-6}{}


\item A {\bf sequ\^{e}ncia de Fibonacci}, $a_1, a_2, a_3, \ldots$ \'{e} definida
       recursivamente assim: 

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $a_1=1$, $a_2=1$;
        \item $a_n=a_{n-1}+a_{n-2}$ para $n\geq 2$. 
       \end{list}
\end{itemize}

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

\newslide{DEFINIÇÃO RECURSIVA (7)}
\hypertarget{definicao-recursiva-7}{}


\noindent Uma defini\c{c}\~{a}o recursiva de um conjunto $A$ especifica uma
sequ\^{e}ncia de conjuntos \[B_0, B_1, B_2, \ldots, B_i, \ldots\]
tal que:
\begin{itemize}
 \item $B_0$ \'{e} o conjunto especificado no passo base;
 \item cada $B_i$, para $i>0$, consta dos elementos obtidos a partir de
       $B_{i-1}$, no passo recursivo, por aplica\c{c}\~{a}o de \underline{uma \'{u}nica
       opera\c{c}\~{a}o}; e
 \item $\cup_{i=0}^\infty B_i = A$.
\end{itemize}

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

\newslide{DEFINIÇÃO RECURSIVA (8)}
\hypertarget{definicao-recursiva-8}{}


\noindent Defini\c{c}\~{o}es recursivas propiciam:

\vspace*{5mm}
\begin{itemize}
 \item Confec\c{c}\~{a}o de {\bf algoritmos recursivos}.
 \item {\bf Provas por indu\c{c}\~{a}o}.
\end{itemize}

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

\newslide{Princípio da Indução Matemática (Fraca) (1)}
\hypertarget{inducao-fraca-1}{}

\noindent {\bf Princ\'{\i}pio da Indu\c{c}\~{a}o Matem\'{a}tica} (fraca) para um conjunto $A$
definido recursivamente: Sejam $A$, $B_0, B_1, \ldots$ como definidos
anteriormente. Suponha que:
\begin{itemize}
 \item $P(a)$ \'{e} verdadeira para todo $a\in B_0$; e
 \item se $P(x)$ \'{e} verdadeira para $x\in B_i$, ent\~{a}o $P(x)$ \'{e} verdadeira para
       $x\in B_{i+1}$.
\end{itemize}
Pode-se, ent\~{a}o, concluir que $P(x)$ \'{e} verdadeira para todo $x \in A$.

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

\newslide{Princípio da Indução Matemática (Fraca) (2)}
\hypertarget{inducao-fraca-2}{}

\noindent Estrutura de uma {Prova por Indu\c{c}\~{a}o}:
\begin{list}{(\alph{conta})}{\usecounter{conta}}
 \item Provar que $P(a)$ \'{e} verdadeira para todo $a\in B_0$.
 \item Supor, como {\bf hip\'{o}tese de indu\c{c}\~{a}o}, que $P(x)$ \'{e} verdadeira para
       $x\in B_i$.
 \item Provar que $P(x)$ \'{e} verdadeira para $x\in B_{i+1}$.
\end{list}

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

\newslide{Princípio da Indução Matemática (Fraca) (3)}
\hypertarget{inducao-fraca-3}{}

\noindent \underline{Exemplos}:

\vspace*{5mm}
\begin{itemize}
 \item $\sum_{k=1}^nk=n(n+1)/2$.
 \item $\sum_{k=1}^n(2k-1)=n^2$.
 \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.
\end{itemize}

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

\newslide{Princípio da Indução Matemática (Forte) (1)}
\hypertarget{inducao-forte-1}{}

\noindent {\bf Princ\'{\i}pio da Indu\c{c}\~{a}o Matem\'{a}tica} (forte) para um conjunto $A$
definido recursivamente: Sejam $A$, $B_0, B_1, \ldots$ como definidos
anteriormente. Suponha que:
\begin{itemize}
 \item $P(a)$ \'{e} verdadeira para todo $a\in B_0$; e
 \item se $P(x)$ \'{e} verdadeira para $x\in \cup_{k=0}^iB_k$, ent\~{a}o $P(x)$ \'{e}
       verdadeira para $x\in B_{i+1}$.
\end{itemize}
Pode-se, ent\~{a}o, concluir que $P(x)$ \'{e} verdadeira para todo $x \in A$.

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

\newslide{Princípio da Indução Matemática (Forte) (2)}
\hypertarget{inducao-forte-2}{}

\noindent \underline{Exemplos}:

\vspace*{5mm}
\begin{itemize}
 \item Qualquer n\'{u}mero natural maior do que 1 pode pode ser expresso como um
       produto de 1 ou mais primos.
 \item O n\'{u}mero de operandos em uma express\~{a}o posfixada com $n$ operadores \'{e}
       $n+1$.
 \item Seja a sequ\^{e}ncia de Fibonacci, definida por $a_1=1$, $a_2=1$, e
       $a_n = a_{n-1}+a_{n-2}$ para $n\geq 3$. Para $n \geq 1$, $a_n\leq
       [(1+\sqrt{5})/2]^n$.     
\end{itemize}

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

\newslide{Princípio da Indução Matemática (Forte) (3)}
\hypertarget{inducao-forte-3}{}

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

\noindent {\bf Prova:}

Ser\'{a} usada prova por indu\c{c}\~{a}o sobre $n$. Evidentemente, se a cole\c{c}\~{a}o tem apenas
1 bola, toda bola tem a mesma cor. Hip\'{o}tese de indu\c{c}\~{a}o: se a cole\c{c}\~{a}o tem $n$
bolas, todas s\~{a}o da 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}

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

\newslide{Princípio da Indução Matemática (Forte) (4)}
\hypertarget{inducao-forte-4}{}

\noindent 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. Com isto, a \underline{\bf interse\c{c}\~{a}o} entre as duas
cole\c{c}\~{o}es implica que as $n+1$ bolas t\^{e}m a mesma cor.

\vspace*{20mm}

\noindent {\bf  Qual o problema com esta prova?}

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

\newslide{Princípio da Indução Matemática (Forte) (5)}
\hypertarget{inducao-forte-5}{}

\noindent {\bf O problema:} a {\bf interse\c{c}\~{a}o} n\~{a}o existe para $n=2$.

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

\defskiptarget{capitulo1}

\lastpage 

\end{document}