Ir ao conteúdo principal

Matemática Discreta: notas de aula

Ricardo Machado

Seção 2.1 Definições por Indução ou Recorrência

Neste capítulo, examinamos diversas situações que usam o método da indução, seja para situações expressas em linguagem matemática, seja para outras de natureza mais lúdica, expressas em uma linguagem não tão obviamente matemática.

Subseção 2.1.1 Definições por Indução ou Recorrência

Uma sequência real é uma função \(s:\mathbb{N}\rightarrow \mathbb{R}\text{.}\) Em muitas sequência a definição é feita por meio de uma expressão matemática que permite calcular \(s_n\) a partir de \(n\text{.}\) É o caso, por exemplo, da sequência \(s_n=n^2\text{,}\) cujos primeiros termos são \(s_1=1, s_2=4, s_3=9\text{,}\) etc. Há casos, porém, em que a forma natural de definir uma sequência é por recorrência.

Exemplo 2.1.1.

O fatorial do número natural \(n\) é definido como o produto \(1\cdot2\cdot 3\cdots n\) dos números naturais menores ou iguais a \(n\text{.}\) Naturalmente, entendemos o significado das reticências na definição acima, mas a definição por ser tornada mais rigorosa usando o mecanismo de indução. Basta definir:
  • \(\displaystyle 1!=1;\)
  • \((n+1)! = n!(n+1)\text{,}\) para todo \(n\in \mathbb{N}\text{.}\)
Com isto, estamos definindo, por recorrência, a sequência definida por \(s_n=n!\text{,}\) para todo \(n\in \mathbb{N}\text{.}\)

Exemplo 2.1.2.

O método de Newton para calcular a raiz quadrada de um número real positivo \(a\) fornece aproximações sucessivas desta raiz. Este método é definido recursivamente por
  • \(\displaystyle x_1=1;\)
  • \(x_{n+1}=\frac{1}{2}\left(x_n+\frac{a}{x_n} \right)\text{,}\) para todo \(n\in \mathbb{N}\text{.}\)
Recorrência é também a forma apropriada para definir o somatório:
\begin{equation*} \sum_{i=1}^n a_i = a_1+a_2+\cdots+a_n \end{equation*}
e o produtório:
\begin{equation*} \prod_{i=1}^n a_i = a_1\cdot a_2\cdots a_n\text{,} \end{equation*}
na qual \((a_n)\) é uma sequência real qualquer.

Definição 2.1.3.

  • \(\displaystyle \sum_{i=1}^1 a_i=a_1;\)
  • \(\displaystyle\sum_{i=1}^{n+1}a_i = \left(\sum_{i=1}^n a_i\right)+a_{n+1}\text{,}\) para todo \(n\in \mathbb{N}\text{.}\)

Definição 2.1.4.

  • \(\displaystyle \prod_{i=1}^1 a_i=a_1;\)
  • \(\displaystyle\prod_{i=1}^{n+1}a_i = \left(\prod_{i=1}^n a_i\right)\cdot a_{n+1}\text{,}\) para todo \(n\in \mathbb{N}\text{.}\)

Subseção 2.1.2 Demonstrando Igualdades

Uma das aplicações mais simples do método de indução é comprovar que a expressão para um somatório (ou produtório), muitas vezes sugerida pelo exame de alguns casos, está correta. Isto já foi feito no Exemplo 1.1.2.
O que torna o uso de indução nestes casos particularmente fácil é que a passagem de \(P(n)\) para \(P(n+1)\) é quase automática: basta acrescentar o novo termo do somatório a cada membro da igualdade e manipular o lado direito de modo que ele adquira a forma necessária para verificar a veracidade de \(P(n+1)\text{.}\)

Exemplo 2.1.5.

Mostre que
\begin{equation*} 1^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}{6}. \end{equation*}
Solução.
Seja
\begin{equation*} P(n): 1^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}{6}. \end{equation*}
  1. \(P(1)\) é verdadeira, já que
    \begin{equation*} \frac{1(1+1)(2\cdot 1+1)}{6}=1=1^2. \end{equation*}
  2. Suponhamos que \(P(n)\) seja verdadeira, para algum \(n\in \mathbb{N}\text{.}\) Isto significa que, para este valor de \(n\text{,}\) temos
    \begin{equation*} 1^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}{6}. \end{equation*}
    Somando o próximo termo do somatório, \((n+1)^2\text{,}\) a ambos os membros da igualdade, obtemos:
    \begin{equation*} 1^2+2^2+\cdots+n^2+(n+1)^2=\frac{n(n+1)(2n+1)}{6}+(n+1)^2. \end{equation*}
    Manipulando o segundo membro da igualdade,
    \begin{align*} \frac{n(n+1)(2n+1)}{6}+(n+1)^2=\amp~\frac{(n+1)(n(2n+1)+6(n+1))}{6}\\ =\amp~ \frac{(n+1)(2n^2+7n+6)}{6}\\ =\amp~ \frac{(n+1)(n+2)(2n+3)}{6}. \end{align*}
    Portanto,
    \begin{equation*} 1^2+2^2+\cdots+n^2+(n+1)^2=\frac{(n+1)(n+2)(2n+3)}{6}, \end{equation*}
    o que mostra que \(P(n+1)\) é verdadeira. Logo, provamos que se \(P(n)\) é verdadeira para \(n\in \mathbb{N}\text{,}\) então \(P(n+1)\) também é verdadeira.
O princípio da Indução Finita permite, então, concluir que \(P(n)\) é verdadeira para todo \(n\in \mathbb{N}\text{.}\)

Subseção 2.1.3 Demonstrando Desigualdades

O emprego de indução para demonstrar desigualdades associadas a somatórios ou produtórios é mais sutil, porque, em geral, a simples inclusão do termo adicional a cada membro não leva de modo automático à forma desejada da desigualdade. Normalmente é necessário demonstrar uma desigualdade adicional para completar a passagem.

Exemplo 2.1.6.

Demonstre a desigualdade de Bernulli:
\begin{equation*} (1+h)^n\geq 1+nh, \end{equation*}
para todo \(n\) natural e todo \(h>-1\text{.}\)
Solução.
Seja \(P(n): (1+h)^n\geq 1+nh\text{.}\)
  1. Como \((1+h)^1\) e \(1+1\cdot h\) são ambos iguais a \(1+h\text{,}\) \(P(1)\) é verdadeira.
  2. Suponhamos que \(P(n)\text{,}\) para algum \(n\in \mathbb{N}\text{,}\) seja verdadeira, ou seja,
    \begin{equation*} (1+h)^n\geq 1+nh. \end{equation*}
    Multiplicando ambos os membros por \((1+h)\text{,}\) como \(1+h>0\text{,}\) obtemos
    \begin{equation*} (1+h)^{n+1}\geq (1+nh)(1+h)=1+(n+1)h+\underbrace{nh^2}_{\geq0}. \end{equation*}
    Logo,
    \begin{equation*} (1+h)^{n+1}\geq 1+(n+1)h. \end{equation*}
    Assim, mostramos que \(P(n)\) implica \(P(n+1)\text{,}\) para todo \(n\in \mathbb{N}.\)
Portanto, pelo Princípio da Indução Finita, \((1+h)^n\geq 1+nh\text{,}\) para todo \(n\) natural e todo \(h>-1\text{.}\)

Exemplo 2.1.7.

Mostre que
\begin{equation*} \frac{1}{2}\cdot\frac{3}{4}\cdot\frac{5}{6}\cdots\frac{2n-1}{2n}\leq \frac{1}{\sqrt{2n+1}}, \end{equation*}
para todo \(n\in \mathbb{N}\text{.}\)
Solução.
Seja \(P(n): \frac{1}{2}\cdot\frac{3}{4}\cdot\frac{5}{6}\cdots\frac{2n-1}{2n}\leq \frac{1}{\sqrt{2n+1}}.\)
  1. Como \(\frac{1}{2}=\frac{1}{\sqrt{4}}\lt \frac{1}{\sqrt{2\cdot 1+1}}, P(1)\) é verdadeira.
  2. Suponhamos que \(P(n)\text{,}\) para algum \(n\in \mathbb{N}\text{,}\) seja verdadeira, ou seja,
    \begin{equation*} \frac{1}{2}\cdot\frac{3}{4}\cdot\frac{5}{6}\cdots\frac{2n-1}{2n}\leq \frac{1}{\sqrt{2n+1}}. \end{equation*}
    É natural multiplicar os dois membros pelo termo seguinte do produtório, \(\frac{2n+1}{2n+2}\text{,}\) obtendo-se:
    \begin{equation*} \frac{1}{2}\cdot\frac{3}{4}\cdot\frac{5}{6}\cdots\frac{2n-1}{2n}\cdot\frac{2n+1}{2n+2} \leq \frac{1}{\sqrt{2n+1}}\cdot\frac{2n+1}{2n+2}. \end{equation*}
    Agora, precisamos mostrar que a expressão do segundo membro é menor ou igual a \(\frac{1}{\sqrt{2(n+1)+1}}=\frac{1}{\sqrt{2n+3}}\text{.}\) De fato,
    \begin{align*} \frac{1}{\sqrt{2n+1}}\cdot\frac{2n+1}{2n+2}\leq\amp~\frac{1}{\sqrt{2n+3}} \Leftrightarrow\\ \sqrt{2n+1}\sqrt{2n+3}\leq\amp~(2n+2)\Leftrightarrow\\ (2n+1)(2n+3)\leq\amp~(2n+2)^2\Leftrightarrow\\ 4n^2+8n+3\leq \amp~4n^2+8n+4 \Leftrightarrow\\ 3\leq \amp~4. \end{align*}
    Assim, mostramos que \(P(n)\) implica \(P(n+1)\text{.}\)
Portanto, pelo Princípio da Indução Finita, \(P(n)\) é verdadeiro para todo \(n\in \mathbb{N}\text{.}\)

Subseção 2.1.4 Aplicações em Aritmética

O método da indução é útil também para demonstrar resultados em aritmética, particularmente envolvendo divisibilidade.

Exemplo 2.1.8.

Mostre que, para todo \(n\in \mathbb{N}\text{,}\) \(4^n+6n-1\) é divisível por \(9\text{.}\)
Solução.
Seja \(P(n)\) a afirmativa: \(4^n+6n-1\) é divisível por \(9\text{.}\)
  1. Como \(4^1+6\cdot 1-1=9, P(1)\) é, de fato, verdadeira.
  2. Suponhamos que \(P(n)\) seja válida para algum \(n\text{,}\) ou seja, \(4^n+6n-1\) é divisível por \(9\text{.}\) Isto significa que existe um inteiro \(k\) tal que \(4^n+6n-1=9k\text{.}\) Isto é equivalente a \(4^n=9k-6n+1\text{.}\) Multiplicando os dois membros da igualdade por \(4\text{,}\) obtemos
    \begin{equation*} 4^{n+1} = 36k-24n+4. \end{equation*}
    Logo,
    \begin{align*} 4^{n+1}+6(n+1)-1 =\amp~ 36k-24n+4+6(n+1)-1\\ =\amp~36k-18n+9\\ =\amp~9(4k-2n+1). \end{align*}
    Portanto, \(4^{n+1}+6(n+1)-1\) é divisível por \(9\text{.}\) Assim, provamos que \(P(n)\) implica \(P(n+1)\text{,}\) para todo \(n\) natural.
Logo, pelo Princípio da Indução Finita, \(P(n)\) é verdadeira para todo \(n\in \mathbb{N}\text{.}\)
<Anterior^TopPróximo>
Feito com PreTeXt
Powered by Runestone