Princípio da indução finita

Técnica utilizada para demonstrar propriedades que se aplicam a uma sequência de objetos.

Exemplo 1

Prove, por PIF, que a relação abaixo é verdadeira para todo n Natural não nulo:

1 + 2 + 3 + \dots + n = \frac{( n + 1 ) \times n}{2}

Resposta:

s (n) = \frac{n ( n + 1 )}{2}

s (1) = \frac{1 ( 1 + 1 )}{2} = 1

s (k) \to s (k + 1)

s (k + 1) = 1 + 2 + \dots + k + k + 1

s (k + 1) = \frac{k ( k + 1 )}{2} + \frac{2 ( k + 1 )}{2}

s (k + 1) = \frac{k ^{2} + k + 2 k + 2}{2}

s (k + 1) = \frac{k ^{2} + 3 k + 2}{2}

s (k + 1) = \frac{( k + 1 ) ( k + 2 )}{2}

Encontre uma expressão para a soma dos $n$ primeiros números ímpares positivos

Resposta:

1 = 1 = 1²
1 + 3 = 4 = 2²
1 + 3 + 5 = 9 = 3²
1 + 3 + 5 + 7 = 16 = 4²
1 + 3 + 5 + 7 + 9 = 25 = 5²

Conjectura:

s (n) = 1 + 3 + 5 + \dots + (2 n - 1) = n^{2}

I) $s (1) = 1 = 1^{2}$

II) $s (k) \to s (k + 1)$

s (k + 1) = 1 + 3 + \dots + 2 k - 1 + 2 k + 1

s (k + 1) = k^{2} + 2 k + 1

s (k + 1) = (k + 1)^{2}