\documentstyle[12pt]{artigo} 

\setcounter{page}{95}
\newcounter{conta}
\setlength{\topmargin}{-40pt}
\begin{document} \Large

\begin{center} \LARGE\bf
 INDU\c C\~AO MATEM\'ATICA
\end{center}

\vspace*{10mm}
\begin{flushleft} \LARGE\bf
 Para provar $\forall n\in\mbox{\bf N} P(n)$:
\end{flushleft}

\vspace*{5mm}
\hspace*{1cm}\fbox{\parbox{13cm}{\it Provar:
 \begin{enumerate}
  \item $P(0)$ ({\it caso base\/});
  \item $\forall n\in\mbox{\bf N}[P(n)\rightarrow P(n+1)]$ ({\it passo de
         indu\c c\~ao\/}).
 \end{enumerate}}}

\vspace*{15mm}
\begin{flushleft} \LARGE\bf
 Exemplos:
\end{flushleft}

\vspace*{10mm}
\begin{description}
 \item[Teorema.] {\it Para todo n\'umero natural $n$, \[2^0+2^1+\cdots+2^n=
       2^{n+1}-1\mbox{.}\]}
\end{description}

\vspace*{10mm}
\begin{description}
 \item[Teorema.] $\forall n\in \mbox{\bf N}[ 3 \,|\, (n^3-n) ]$.
\end{description}

\pagebreak
\begin{flushleft} \LARGE\bf
 Qual \'e maior?
\end{flushleft}

\vspace*{15mm}
\begin{center}
 \begin{tabular}{c|rrc}
  $n$ & $n^2$ & $2^n$ & Qual \'e maior? \\ \hline
  0 &  0 &  1 &  $2^n$ \\
  1 &  1 &  2 &  $2^n$ \\
  2 &  4 &  4 &  empate \\
  3 &  9 &  8 &  $n^2$ \\
  4 & 16 & 16 &  empate \\
  5 & 25 & 32 &  $2^n$ \\
  6 & 36 & 64 &  $2^n$
 \end{tabular}

\vspace*{7mm}
 Parece que $2^n$ n\~ao perde mais...
\end{center}

\vspace*{15mm}
\begin{description}
 \item[Teorema.] $\forall n\geq 5 (2^n>n^2)$.
\end{description}

\pagebreak
\begin{flushleft} \LARGE\bf
 Indu\c c\~ao matem\'atica vai al\'em dos naturais...
\end{flushleft}

\vspace*{15mm}
\begin{description}
 \item[Teorema.] {\it Suponha que $R$ \'e uma ordem parcial sobre um conjunto
        $A$. Ent\~ao todo conjunto finito, n\~ao vazio, $B\subseteq A$ tem um
        elemento $R$-minimal.}

\vspace*{15mm}
 \item[Teorema.] {\it Para todo $n\geq 3$, 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^o$.}

\vspace*{15mm}
 \item[Teorema.] {\it Para qualquer inteiro positivo $n$, uma grade de
        quadrados $2^n\times 2^n$, com qualquer um de seus quadrados removido,
        pode ser coberta com ladrilhos em forma de {\sf L}:}
        \begin{center}
         \begin{picture}(20,20)
          \put(0,0){\line(0,1){20}}
          \put(0,0){\line(1,0){20}}
          \put(0,10){\line(1,0){20}}
          \put(10,0){\line(0,1){20}}
          \put(0,20){\line(1,0){10}}
          \put(20,0){\line(0,1){10}}
         \end{picture}
        \end{center}

\end{description}

\pagebreak
\begin{flushleft} \LARGE\bf
 Recurs\~ao:
\end{flushleft}

\vspace*{15mm}
\begin{itemize}
 \item {\bf Prova por indu\c c\~ao de $\forall n\in\mbox{\bf N} P(n)$:}
        
       \begin{enumerate}
        \item Provar $P(0)$.
        \item Provar que para todo natural $n$, $P(n)\rightarrow P(n+1)$.
       \end{enumerate}

\vspace*{10mm}
 \item {\bf Defini\c c\~ao recursiva de uma fun\c c\~ao $f\!:\mbox{\bf N}
       \rightarrow\mbox{\bf N}$:}
        
       \begin{enumerate}
        \item Exibir $f(0)$.
        \item Mostrar como calcular $f(n+1)$ a partir de $f(n)$.
       \end{enumerate}

\end{itemize}

\vspace*{15mm}
\begin{flushleft} \LARGE\bf
 Exemplos:
\end{flushleft}

\vspace*{10mm}
\begin{description}
 \item[Fatorial:] \
 
\vspace*{5mm}
       $\mbox{\it fat}(0)=1$;
 
       para todo $n\in\mbox{\bf N}$, $\mbox{\it fat}(n+1)=(n+1).\mbox{\it
        fat}(n)$.

\vspace*{10mm}
 \item[Exponencia\c c\~ao:] \
 
\vspace*{5mm}
       para qualquer $a\in\mbox{\bf R}$:
 
       \hspace*{1cm} $a^0=1$;
 
       \hspace*{1cm} para todo $n\in\mbox{\bf N}$, $a^{n+1}=a^n.a$.

\vspace*{10mm}
 \item[Uma somat\'oria:]  \
 
\vspace*{5mm}
       $f(0)=1$;
 
       para todo $n\in\mbox{\bf N}$, $f(n+1)=f(n)+2^{n+1}$.

\vspace*{10mm}
 \item[Somat\'orias, em geral:]  \
 
\vspace*{5mm}
       $\sum_{i=m}^{m}a_i=a_m$;
       
       para todo $n\geq m$, $\sum_{i=m}^{n+1}a_i=\sum_{i=m}^{n}a_i + a_{n+1}$.
\end{description}

\pagebreak
\begin{description}
 \item[Teorema.] {\it para todo $n\geq 4$, $n!>2^n$.}

\vspace*{15mm}
 \item[Teorema.] {\it Para todo n\'umero real $a$ e todos os n\'umeros naturais
        $m$ e $n$, $a_{m+n}=a^m.a^n$.}

\vspace*{15mm}
 \item[Problema:] \
 
       Seja a a sequ\^encia $a_0, a_1,a_2,\ldots$ definida recursivamente
       assim:
       \begin{enumerate}
        \item[\ ] $a_0=0$;
        \item[\ ] para todo $n\in\mbox{\bf N}$, $a_{n+1}=2a_n+1$.
       \end{enumerate}
       Encontre uma f\'ormula para $a_n$, e prove que ela est\'a correta.

\vspace*{15mm}
 \item[Teorema.] {\it Para todo $x>-1$ e n\'umero natural $n$, $(1+x)^n>
       nx$.}

\end{description}

\pagebreak
\begin{flushleft} \LARGE\bf
 Indu\c c\~ao forte:
\end{flushleft}

\vspace*{5mm}
\hspace*{1cm}\fbox{\parbox{13cm}{\it Para provar $\forall n\in\mbox{\bf N} P(n)$,
 provar: \[\forall n\in\mbox{\bf N}[(\forall k<n P(k))\rightarrow P(n)]
 \mbox{.}\]}}

\vspace*{15mm}
\begin{flushleft} \LARGE\bf
 Exemplos:
\end{flushleft}

\vspace*{10mm}
\begin{description}
 \item[Teorema.] (Algoritmo da divis\~ao) {\it Para todos os n\'umeros naturais
       $m$ e $n$, se $m>0$, ent\~ao existem n\'umeros naturais $q$ e $r$ tais
       que $n=mq+r$ e $r<m$.} (Os n\'umeros $q$ e $r$ s\~ao o {\it quociente\/}
       e o {\it resto\/} da divis\~ao de $n$ por $m$.)
\end{description}

\vspace*{10mm}
\begin{description}
 \item[Teorema.] {\it Todo inteiro $n>1$ \'e primo ou um produto de primos.}
\end{description}

\pagebreak
\begin{description}
 \item[A sequ\^encia de Fibonacci:] \
 
\vspace*{5mm}
       $F(0)=0$;
 
       $F(1)=1$;
 
       para todo $n\geq 2$, $F_n=F_{n-2}+F_{n-1}$.

\vspace*{10mm}
 \item[Teorema.] {\it Se $F_n$ \'e o $n$-\'esimo n\'umero de Fibonacci, ent\~ao
        \[F_n=\frac{(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n}
          {\sqrt{5}}\mbox{.}\]}

\vspace*{10mm}
 \item[Teorema.] (Princ\'{\i}pio da boa-ordena\c c\~ao) {\it Todo conjunto n\~ao
        vazio de n\'umeros naturais tem um menor elemento.}

\vspace*{10mm}
 \item[Teorema.] {\it $\sqrt{2}$ \'e irracional.}
\end{description}


\end{document}
