2 Indução Matématica - Passo a Passo

Prévia do material em texto

<p>ENTENDENDO A DEMONSTRAÇÃO POR INDUÇÃO</p><p>O princípio de indução funciona da seguinte forma:</p><p>Suponha que se deseja provar determinada propriedade envolvendo números inteiros a qual</p><p>chamaremos de P(n). Para fazer isto, basta verificar a validade de P(1) e mostrar que se P(k) é</p><p>válida para algum número natural 𝑘 ≥ 1, então P(k+1) é também válida.</p><p>Veja como se dá o processo: verificado que P(1) é verdadeira, então P(1+1) = P(2) será</p><p>verdadeira. Mas sendo P(2) verdadeira, então P(2+1) = P(3) será verdadeira; se P(3) é verdadeira,</p><p>então P(3+1) = P(4) será verdadeira; e assim por diante. Desta forma, teremos concluído que</p><p>P(n) será verdadeira para todo n a partir de n=1.</p><p>Muitas vezes a propriedade só começa a ser válida a partir de um certo número natural 𝑎. Veja</p><p>por exemplo que a sentença 2𝑛 > 𝑛2 só é válida a partir de 𝑛 = 5. Neste caso, 𝑎 seria 5.</p><p>Assim, temos que verificar inicialmente que P(𝑎) é verdadeira, e então supor que se P(k) for</p><p>verdadeira, para 𝑘 ≥ 𝑎, então P(k+1) é também válida.</p><p>MÉTODO PRÁTICO PARA USAR O PRINCÍPIO DA INDUÇÃO</p><p>Passo 1: Verifique que P(𝑎) é verdadeira, onde 𝑎 tem que ser um número maior ou igual a 0.</p><p>Passo 2: Escreva P(k) como sendo verdadeira para este k (sem dar valor para k).</p><p>Passo 3: Demonstre que P(k+1) é verdadeira, tendo como hipótese P(k).</p><p>Conseguido isto, teremos provado que P(n) é verdadeira, para todo 𝑛 ≥ 𝑎</p><p>Exemplo 1: Mostre que, para todo 𝑛 ≥ 1, é verdadeiro que</p><p>1 + 5 + 9 + ⋯ + (4𝑛 − 3) = 2𝑛2 − 𝑛,</p><p>Interpretando a sentença: A sentença acima diz que se somarmos a partir de 1, números naturais</p><p>aumentando-os de 4 em 4, tal soma resultará exatamente no valor 2𝑛2 − 𝑛, onde 𝑛 é o número</p><p>de termos somados, a partir de 1 (primeiro termo) até o 4𝑛 − 3 (último termo somado). Temos</p><p>que provar que a soma dá sempre igual a 2𝑛2 − 𝑛, sem contudo somar termo a termo.</p><p>Demonstrando a sentença por indução:</p><p>Passo 1: Verificamos que P(1) é verdadeira.</p><p>P(1) significa que vamos ter um só termo na soma, ou seja, o primeiro, que neste caso, será o</p><p>próprio número 1. Assim, do lado esquerdo da igualdade, temos 1. E do lado direito? Queríamos</p><p>provar que a soma é sempre 2𝑛2 − 𝑛. Como só temos um termo, 𝑛 = 1, e substituindo 𝑛 = 1</p><p>em 2𝑛2 − 𝑛 obtemos: 2(1)2 − 1 = 2 − 1 = 1, ou seja, obtivemos como resposta o valor da</p><p>soma para um só termo, o próprio número 1, concordando com o lado esquerdo da igualdade.</p><p>Portanto, para n=1, a fórmula é verdadeira.</p><p>Passo 2: Escrevemos P(k) como sendo verdadeira, sem dar valor para k.</p><p>Assim, teremos que:</p><p>1 + 5 + 9 + ⋯ + (4𝑘 − 3) = 2𝑘2 − 𝑘</p><p>Ou seja, supomos ser verdade que a soma de 4 em 4 a partir do 1 até o termo 4k-3 seja mesmo</p><p>igual a 2𝑘2 − 𝑘 , que é o que diz a sentença, para n substituído por este k. (Neste passo, só</p><p>escrevemos e nada demonstramos, apenas usaremos isto como hipótese para o próximo passo).</p><p>Passo 3: Agora sim queremos demonstrar que P(k+1) seja verdadeira, ou seja, temos que provar</p><p>que a soma de 1 até o termo de ordem (k+1), que seria o 4(k+1) -3 (substituindo n por k+1) vai</p><p>dar como resultado o que diz a fórmula, substituindo n por k+1, que deveria ser</p><p>2(𝑘 + 1)2 − (𝑘 + 1).</p><p>Ou seja, agora queremos provar que vale a sentença abaixo:</p><p>1 + 5 + 9 + ⋯ + (4(𝑘 + 1) − 3) = 2(𝑘 + 1)2 − (𝑘 + 1).</p><p>No passo 2, assumimos a sentença como verdade, e agora, neste passo 3, vamos demonstrar a</p><p>sentença acima ser válida para k+1 termos.</p><p>Como isto é feito? Façamos a análise em relação aos dois lados da igualdade acima descrita.</p><p>Primeiro, temos a seguinte soma (lado esquerdo da igualdade acima)</p><p>1 + 5 + 9 + ⋯ + (4(𝑘 + 1) − 3) = 1 + 5 + 9 + ⋯ + (4𝑘 + 1).</p><p>Repare que a soma acima vai até o termo (4k+1), enquanto que a soma do passo 2 ia até (4k-3).</p><p>Logo, a soma acima tem o termo (4k+1) a mais do que a soma do passo 2. Ou seja, a soma acima</p><p>seria:</p><p>1 + 5 + 9 + ⋯ + (4𝑘 − 3) + (4𝑘 + 1).</p><p>Isto é,</p><p>Soma do passo 3 = (soma do passo 2) + (4𝑘 + 1).</p><p>Como a soma do passso 2 é igual a 2𝑘2 − 𝑘 (por nossa hipótese feita), então temos que:</p><p>Soma do passo 3 = (2𝑘2 − 𝑘) + (4𝑘 + 1), o que dá, simplificando a soma:</p><p>Soma do passo 3 = 2𝑘2 + 3𝑘 + 1.</p><p>Agora, vamos analisar o lado direito da igualdade da equação que queremos provar:</p><p>2(𝑘 + 1)2 − (𝑘 + 1).</p><p>Vamos desenvolver estes termos e esperar que ele resulte numa expressão igual a expressão</p><p>obtida como soma do passo 3. Temos que:</p><p>2(𝑘 + 1)2 − (𝑘 + 1) = 2(𝑘2 + 2𝑘 + 1) − (𝑘 + 1) = 2𝑘2 + 4𝑘 + 2 − 𝑘 − 1 = 2𝑘2 + 3𝑘 + 1.</p><p>Exatamente igual a expressão que chegamos usando a hipótese do passo 2. Isto demonstra o</p><p>passo 3, e comprova, pelo Princípio da Indução, que a sentença é verdadeira, para todo 𝑛 ≥ 1.</p><p>□</p><p>Exemplo 2: Mostre que, para todo 𝑛 ≥ 1, é verdadeiro que</p><p>4 + 7 + 10 + ⋯ + (3𝑛 + 1) =</p><p>𝑛(3𝑛 + 5)</p><p>2</p><p>,</p><p>Interpretando a sentença: A sentença acima diz que se somarmos a partir de 4, números naturais</p><p>aumentando-os de 3 em 3, tal soma resultará exatamente no valor</p><p>𝑛(3𝑛+5)</p><p>2</p><p>, onde 𝑛 é o número</p><p>de termos somados, a partir de 4 (primeiro termo) até o 3𝑛 + 1 (último termo somado). Temos</p><p>que provar que a soma dá sempre igual a</p><p>𝑛(3𝑛+5)</p><p>2</p><p>, sem contudo somar termo a termo.</p><p>Demonstrando a sentença por indução:</p><p>Passo 1: Verificamos que P(1) é verdadeira.</p><p>Novamente como no exemplo anterior, P(1) significa que vamos ter um só o primeiro termo na</p><p>que neste caso será o número 4. Queremos provar que a soma é sempre</p><p>𝑛(3𝑛+5)</p><p>2</p><p>. Como só temos</p><p>um termo, substituímos 𝑛 = 1 em</p><p>𝑛(3𝑛+5)</p><p>2</p><p>obtendo:</p><p>1.(3+5)</p><p>2</p><p>=</p><p>8</p><p>2</p><p>= 4, ou seja, obtivemos como</p><p>resposta o valor da soma para um só termo, o próprio número 4, concordando com o lado</p><p>esquerdo da igualdade. Portanto, para n=1, a fórmula é verdadeira.</p><p>Passo 2: Escrevemos P(k) como sendo verdadeira, sem dar valor para k.</p><p>Assim, teremos que:</p><p>4 + 7 + 10 + ⋯ + (3𝑘 + 1) =</p><p>𝑘(3𝑘 + 5)</p><p>2</p><p>Ou seja, supomos ser verdade que a soma de 3 em 3 a partir do 4 até o termo 3k+1 seja mesmo</p><p>igual a</p><p>𝑘(3𝑘+5)</p><p>2</p><p>.</p><p>Passo 3: Agora vamos demonstrar que P(k+1) é verdadeira se P(k) o for, ou seja, temos que</p><p>provar que a soma de 4 até o termo de ordem (k+1), que seria o 3(k+1) +1 (substituindo n por</p><p>k+1) vai dar como resultado o que diz a fórmula, substituindo n por k+1, que deveria ser</p><p>(𝑘 + 1)(3(𝑘 + 1) + 5)</p><p>2</p><p>.</p><p>Ou seja, agora queremos provar que vale a sentença abaixo:</p><p>4 + 7 + 10 + ⋯ + (3(𝑘 + 1) + 1) =</p><p>(𝑘 + 1). (3(𝑘 + 1) + 5)</p><p>2</p><p>Façamos a análise em relação aos dois lados da igualdade. Primeiro, temos a seguinte soma</p><p>(lado esquerdo da igualdade acima)</p><p>4 + 7 + 10 + ⋯ + (3(𝑘 + 1) + 1) = 4 + 7 + 10 + ⋯ + (3𝑘 + 4).</p><p>Repare que a soma acima vai até o termo (3k+4), enquanto que a soma do passo 2 ia até (3k+1).</p><p>Logo, a soma acima tem o termo (3k+4) a mais do que a soma do passo 2. Ou seja, a soma acima</p><p>seria:</p><p>4 + 7 + 10 + ⋯ + (3𝑘 + 1) + (3𝑘 + 4).</p><p>Ou ainda, temos que:</p><p>Soma do passo 3 = (soma do passo 2) + (3𝑘 + 4).</p><p>Como a soma do passso 2 é igual a</p><p>𝑘(3𝑘+5)</p><p>2</p><p>(por nossa hipótese feita), então temos que:</p><p>Soma do passo 3 = (</p><p>𝑘(3𝑘+5)</p><p>2</p><p>) + (3𝑘 + 4), o que dá, simplificando a soma:</p><p>Soma do passo 3 =</p><p>𝑘(3𝑘 + 5) + 2. (3𝑘 + 4)</p><p>2</p><p>=</p><p>3𝑘2 + 5𝑘 + 6𝑘 + 8</p><p>2</p><p>=</p><p>3𝑘2 + 11𝑘 + 8</p><p>2</p><p>Agora, vamos analisar o lado direito da igualdade da equação que queremos provar:</p><p>(𝑘 + 1). (3(𝑘 + 1) + 5)</p><p>2</p><p>.</p><p>Vamos desenvolver estes termos e esperar que ele resulte numa expressão igual a expressão</p><p>obtida como soma do passo 3. Temos que:</p><p>(𝑘 + 1). (3(𝑘 + 1) + 5)</p><p>2</p><p>=</p><p>(𝑘 + 1). (3𝑘 + 8)</p><p>2</p><p>=</p><p>3𝑘2 + 8𝑘 + 3𝑘 + 8</p><p>2</p><p>=.</p><p>3𝑘2 + 11𝑘 + 8</p><p>2</p><p>Exatamente igual a expressão que chegamos usando a hipótese do passo 2. Isto demonstra o</p><p>passo 3, e comprova, pelo Princípio da Indução, que a sentença é verdadeira, para todo 𝑛 ≥ 1.</p><p>□</p><p>Exemplo 3: Vamos demonstrar que 5𝑛 + 7 é divisível por 4, para todo 𝑛 ≥ 0.</p><p>Observação: Veja que 5𝑛 representa a potência de 5 elevado ao expoente n, ou seja, como se o</p><p>número 5 tivesse sido multiplicado</p><p>n vezes por ele mesmo. Além disso, dizemos que o número</p><p>𝑎 é múltiplo de um número b, ou que 𝑎 é divisível por b, quando existe um inteiro m tal que</p><p>𝑎 = 𝑏 × 𝑚</p><p>Demonstração da validade da afirmação por indução:</p><p>Passo 1: Vamos mostrar que a sentença é verdadeira para n=0. Temos que 50 + 7 = 1 + 7 = 8,</p><p>que é múltiplo de 4, uma vez que 8 = 2 × 4.</p><p>Passo 2: supomos ser verdade (sem demonstrar) que P(k) é verdadeira, para algum 𝑘 ≥ 0, ou</p><p>seja, afirmamos que 5𝑘 + 7 é divisível por 4. Isto é o mesmo que dizer que 5𝑘 + 7 é múltiplo</p><p>de 4, isto é, que existe algum 𝑚 inteiro tal que 5𝑘 + 7 = 4𝑚, ou seja, 5𝑘 = 4𝑚 − 7.</p><p>Passo 3: Vamos provar que P(k+1) é verdadeira, se P(k) o for, ou seja, que 5𝑘+1 + 7 será divisível</p><p>por 4 se for verdade que 5𝑘 + 7 é divisível por 4. Temos que saber, pela propriedade das</p><p>potências, que 5𝑘+1 = 5𝑘 ⋅ 51 = 5𝑘 ⋅ 5. Por outro, da nossa hipótese do passo 2, temos que</p><p>5𝑘 = 4𝑚 − 7. Substituindo a expressão do passo 2 na expressão do passo 3, temos que:</p><p>5𝑘+1 + 7 = 5𝑘 ⋅ 5 + 7 = (4𝑚 − 7) ⋅ 5 + 7 = 20𝑚 − 35 + 7 = 20𝑚 − 28 = 4(5𝑚 − 7).</p><p>Ou seja, conseguimos mostrar que 5𝑘+1 + 7 se escreve como um número múltiplo de 4 (ou seja,</p><p>divisível por 4), como queríamos demonstrar. □</p>