Indução Finita

Introdução

Algumas vezes nos defrontamos com afirmações envolvendo os números naturais e a pergunta que surge é: será estas afirmações são verdadeiras sempre, ou seja, vale para qualquer número natural?

Exemplo 1: Será que estas afirmações são sempre verdadeiras? Resp.: SIM.

    1. \(1+2+3+\ldots+n=\frac{n(n+1)}{2}\),
      donde lê-se: “A soma dos \(n\) primeiros números naturais maiores ou iguais a \(1\) é dada pela expressão \(\frac{n(n+1)}{2}\)”;
    • Aplicação no R com n=10. Deseja-se calcular \[1+2+3+ \ldots + 10\]
    • e o resultado é \(55\).
n=10 #atribuímos um valor para n
1:n #sequencia numérica
##  [1]  1  2  3  4  5  6  7  8  9 10
sum(1:n) #soma da sequencia numerica
## [1] 55
n*(n+1)/2 #fórmula para a soma
## [1] 55
    1. \(1+q+q^2+\ldots+q^n=\frac{1-q^{n+1}}{1-q}\),
      donde lê-se: “A soma dos \(n+1\) primeiros termos de uma progressão geométrica (P.G.) de razão igual a \(q\) e primeiro termo igual a \(1\) é dada pela expressão \(\frac{1-q^{n+1}}{1-q}\)”;
    • Aplicação no R com q=0.5 e n=5. Deseja-se calcular: \[0.5^0+0.5^1+0.5^2+\ldots+0.5^5\]
    • E o resultado é \(1.96875\).
q=0.5 #atribuímos um valor para q
n=5 #atribuímos um valor para n
seq=q^seq(0,n,by=1)  #sequencia numérica
seq
## [1] 1.00000 0.50000 0.25000 0.12500 0.06250 0.03125
sum(seq) #soma da sequencia numerica
## [1] 1.96875
(1-q^(n+1))/(1-q) #fórmula para a soma
## [1] 1.96875
    1. \(1^2+2^2+3^2+\ldots+n^2=\frac{n(n+1)(2n+1)}{6}\),
      donde lê-se: “A soma dos quadrados dos \(n\) primeiros números naturais maiores ou iguais a \(1\) é dada pela expressão \(\frac{n(n+1)(2n+1)}{6}\)”;
    • Aplicação no R com n=20. Deseja-se calcular \[1^2+2^2+\ldots + 20^2\]
    • e o resultado é \(2870\)
n=20 #atribuímos um valor para n
seq=(1:n)^2 #sequencia numérica
seq
##  [1]   1   4   9  16  25  36  49  64  81 100 121 144 169 196 225 256 289 324 361
## [20] 400
sum(seq) #soma da sequencia numerica
## [1] 2870
n*(n+1)*(2*n+1)/6 #fórmula para a soma
## [1] 2870
    1. \(2+4+6+\ldots+2n=n(n+1)\),
      lê-se: “A soma dos \(n\) primeiros números pares (a partir de \(2\)) é dada pela expressão \(n(n+1)\)”;
    • Aplicação no R com n=15. Deseja-se calcular \[2+4+6+\ldots + 60\]
    • e o resultado é \(2870\)
n=15 #atribuímos um valor para n
seq=seq(2,2*n,by=2) #sequencia numérica
seq
##  [1]  2  4  6  8 10 12 14 16 18 20 22 24 26 28 30
sum(seq) #soma da sequencia numerica
## [1] 240
n*(n+1) #fórmula para a soma
## [1] 240
    1. \(1^3+2^3+3^3+\ldots+n^3=\frac{n^2(n+1)^2}{4}\),
      donde lê-se: “A soma dos cubos dos \(n\) primeiros números naturais maiores ou iguais a \(1\) é dada pela expressão \(\frac{n^2(n+1)^2}{4}\)”;
    • Aplicação no R com n=50. Deseja-se calcular \[1^3+2^3+\ldots +50^3\]
    • e o resultado é \(1625625\)
n=50 #atribuímos um valor para n
seq=(1:50)^3 #sequencia numérica
seq
##  [1]      1      8     27     64    125    216    343    512    729   1000
## [11]   1331   1728   2197   2744   3375   4096   4913   5832   6859   8000
## [21]   9261  10648  12167  13824  15625  17576  19683  21952  24389  27000
## [31]  29791  32768  35937  39304  42875  46656  50653  54872  59319  64000
## [41]  68921  74088  79507  85184  91125  97336 103823 110592 117649 125000
sum(seq) #soma da sequencia numerica
## [1] 1625625
n^2*(n+1)^2/4 #fórmula para a soma
## [1] 1625625
    1. \(1+3+5+\ldots+(2n-1)=n^2\),
      donde lê-se: “A soma dos \(n\) primeiros números ímpares é dada pela expressão \(n^2\)”.
    • Aplicação no R com n=35. Deseja-se calcular \[1+3+5+\ldots +69\]
    • e o resultado é \(1225\)
n=35 #atribuímos um valor para n
seq=seq(1,69,by=2) #sequencia numérica
seq
##  [1]  1  3  5  7  9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49
## [26] 51 53 55 57 59 61 63 65 67 69
sum(seq) #soma da sequencia numerica
## [1] 1225
n^2 #fórmula para a soma
## [1] 1225

OBS: A seguir, veremos como provar a veracidade destas afirmações. Para tanto, utilizaremos o princípio da indução finita.

Princípio da Indução Finita (P.I.F.)

Quando uma afirmação é enunciada em termos de números naturais, o P.I.F. constitui um eficiente instrumento para demonstrar esta afirmação para o caso geral.

Interpretação do P.I.F. na prática

Vamos supor que temos uma série de soldadinhos de chumbo colocados em fila, que começa por um deles e prossegue indefinidamente. Nosso objetivo é - empurrando apenas um soldadinho - garantir que todos caiam. Como derrubar todos os soldados?

Para tanto, basta nos assegurarmos de que:

  1. O primeiro soldado cai;
  2. Os soldados estão dispostos de tal modo que qualquer um deles, toda vez que cai, automaticamente, empurra o soldado seguinte e o faz cair também.

Assim, mesmo que a fila se estenda indefinidamente, podemos afirmar que todas os soldadinhos cairão.

Descrição formal do P.I.F.

Dada uma afirmação, ou proposição, geralmente denotada pela letra \(P\). Esta propriedade está em função de \(n\), com \(n \geq 1\) (os números naturais a partir do \(1\)). O P.I.F. consiste das seguintes etapas:

  1. Mostrar que \(P\) é verdadeira para \(n=1\), ou seja, que \(P(1)\) é verdadeira;
  2. Definir a hipótese de indução:
    Hipótese de indução: \(P\) é verdadeira para \(n=k\), \(k \geq 1\), ou seja, \(P(k)\) é verdadeira para qualquer \(k\) natural maior ou igual a \(1\),
    Baseada na hipótese de indução, devemos mostrar que \(P\) é verdadeira para \(n=k+1\), ou seja,
    \[ P(k) \text{ é verdadeira } \Rightarrow P(k+1) \text{ é verdadeira}, \] donde lê-se: “-se:”Se \(P(k)\) é verdadeira então \(P(k+1)\) é verdadeira" .

Concluídas as etapas I) e II), fica provado que a proposição \(P\) é verdadeira para qualquer número natural \(n \geq 1\).

Exemplo 2: Demonstre a propriedade “b)” do exemplo 3.1 através do P.I.F.

Solução: A demonstração consiste das seguintes etapas:

  1. Mostrar que \(P(1)\) é verdadeira.
    Para \(n=1\), o lado esquerdo (L.E.) da equação é igual a \(1+q\),
    e o lado direito (L.D.) da equação é igual a \(\frac{1-q^{2}}{1-q}\).
    Como \(1-q^{2}=(1-q)(1+q)\), então L.E.=L.D., ou seja, \(P(1)\) é verdadeira.
  2. Hipótese de indução: \(P(k)\) é verdadeira, \(\forall k \geq 1\).
    A hipótese de indução é \(1+q+q^2+\ldots+q^k=\frac{1-q^{k+1}}{1-q}\).
    Para \(n=k+1\), o L.E. da equação é igual a \(1+q+q^2+\ldots+q^{k}+q^{k+1}\).
    Pela hipótese de indução, \[ \text{ L.E.: } \frac{1-q^{k+1}}{1-q}+q^{k+1}=\frac{1-q^{k+1}+q^{k+1}-q^{k+2}}{1-q}=\frac{1-q^{k+2}}{1-q}, \] donde concluímos que \(1+q+q^2+\ldots+q^{k}+q^{k+1}=\frac{1-q^{k+2}}{1-q}\),
    significa que \(P(k+1)\) é verdadeira.

Como as etapas I) e II) foram concluídas, fica provado que \(1+q+q^2+\ldots+q^n=\frac{1-q^{n+1}}{1-q}, \forall n \geq 1.\)

Exercícios

  • Demonstre as afirmações “c)”, “d)”, “e)” e “f)” do exemplo através do P.I.F..