Prova indutiva: Se n é um inteiro maior que 1, então n pode ser escrito como o produto de primos

Neste post, vamos provar que todo número pode ser escrito como o produto de números primos. Usaremos indução forte, ou seja, não assumiremos a verdade da proposição P apenas para n-1 (indução fraca), mas para todo inteiro menor que n, inclusive n-1. É importante lembrar que as formas forte e fraca são equivalentes, mas as vezes, optar por uma das formas facilita a prova. Confira nosso post sobre os tipos de indução aqui.

              P(n): Todo número inteiro n > 1 pode ser escrito como o produto de números primos.

A prova é por indução em n:

• Caso Base: para n = 2, temos que 2 é primo, logo é o único fator primo.
• Hipótese de Indução: vamos assumir que para $2 \le j \le n-1$, j pode ser escrito como o produto de números primos.
• Caso Geral: Devemos considerar dois caso. Se n for primo, então n pode ser escrito como o produto de um primo, ele mesmo. Caso n seja composto, ou seja, n = a * b com $2 \le a \le b \le n-1$, sabemos que por hipótese de indução a e b podem ser escritos como o produto de primos. Como n = a * b, a decomposição de n em fatores primos, é simplesmente a multiplicação de todos os fatores de a pelos fatores de b.      C.Q.D

@inductioncode

Indução e diferenciação: A derivada da função polinomial

Neste post, vamos usar a indução matemática para provar que a derivada da função $f(x) = x^n$é $f'(x) = nx^{n-1}$. Como podemos perceber, precisamos escolher a variável na qual a indução será aplicada, pois a fórmula envolve as variáveis x e n. Aplicaremos indução em n porque a indução só pode ser aplicada sobre os números naturais, e a variável x é real.

Prova por indução em n:

• Caso Base: para n = 1, temos que $\frac{d  x}{dx} = 1*x^{1-1} = 1$, e de fato, a derivada da função identidade $f(x) = x$ é $f'(x) = 1$. 
• Hipótese de Indução: para n = k-1, vamos assumir que a derivada da função $f(x) = x^n$ é $f'(x) = (k-1)x^{k-2}$.
• Caso Geral: Agora, vamos mostrar que  $f'(x) = (k-1)x^{k-1}$ para n = k:
                                           $\frac{d  x^k}{dx} = kx^{k-1}$
                                           {pela regra da cadeia}
                                           $\frac{d  x^k}{dx} = \frac{d  x*x^{k-1}}{dx}$
                                           $                              = 1*x^{k-1} + x*(k-1)x^{k-2}$
                                           $                              = x^{k-1} +(k-1)x^{k-1}$
                                           $                              = (1 + k - 1)x^{k-1}$
                                           $                              = kx^{k-1}$   C.Q.D.

Apesar de uma abordagem puramente matemática, treinar a elaboração de provas através da indução matemática é um exercício fundamental para que possamos construir algoritmos usando indução com mais facilidade.