Indução matemática

Mathematical induction, é uma técnica para provar resultados ou estabelecer declarações para números naturais. Esta parte ilustra o método por meio de uma variedade de exemplos.

Definição

Mathematical Induction é uma técnica matemática que é usada para provar uma afirmação, uma fórmula ou um teorema verdadeiro para todo número natural.

A técnica envolve duas etapas para provar uma afirmação, conforme afirmado a seguir -

Step 1(Base step) - Prova que uma afirmação é verdadeira para o valor inicial.

Step 2(Inductive step)- Prova que se a afirmação é verdadeira para a ^enésima iteração (ou número n ), então também é verdadeira para (n + 1) ^a iteração (ou número n + 1 ).

Como fazer isso

Step 1- Considere um valor inicial para o qual a afirmação é verdadeira. Deve ser mostrado que a afirmação é verdadeira para n = valor inicial.

Step 2- Suponha que a afirmação seja verdadeira para qualquer valor de n = k . Em seguida, prove que a afirmação é verdadeira para n = k + 1 . Na verdade, dividimos n = k + 1 em duas partes, uma parte é n = k (o que já está provado) e tentamos provar a outra parte.

Problema 1

$ 3 ^ n-1 $ é um múltiplo de 2 para n = 1, 2, ...

Solution

Step 1 - Para $ n = 1, 3 ^ 1-1 = 3-1 = 2 $ que é um múltiplo de 2

Step 2 - Vamos supor que $ 3 ^ n-1 $ seja verdadeiro para $ n = k $, portanto, $ 3 ^ k -1 $ seja verdadeiro (é uma suposição)

Temos que provar que $ 3 ^ {k + 1} -1 $ também é um múltiplo de 2

$ 3 ^ {k + 1} - 1 = 3 \ vezes 3 ^ k - 1 = (2 \ vezes 3 ^ k) + (3 ^ k - 1) $

A primeira parte $ (2 \ vezes 3k) $ é certamente um múltiplo de 2 e a segunda parte $ (3k -1) $ também é verdadeira, conforme nossa suposição anterior.

Portanto, $ 3 ^ {k + 1} - 1 $ é um múltiplo de 2.

Portanto, fica provado que $ 3 ^ n - 1 $ é um múltiplo de 2.

Problema 2

$ 1 + 3 + 5 + ... + (2n-1) = n ^ 2 $ para $ n = 1, 2, \ pontos $

Solution

Step 1 - Para $ n = 1, 1 = 1 ^ 2 $, Portanto, a etapa 1 é satisfeita.

Step 2 - Suponhamos que a afirmação seja verdadeira para $ n = k $.

Portanto, $ 1 + 3 + 5 + \ dots + (2k-1) = k ^ 2 $ é verdadeiro (é uma suposição)

Temos que provar que $ 1 + 3 + 5 + ... + (2 (k + 1) -1) = (k + 1) ^ 2 $ também é válido

$ 1 + 3 + 5 + \ dots + (2 (k + 1) - 1) $

$ = 1 + 3 + 5 + \ dots + (2k + 2 - 1) $

$ = 1 + 3 + 5 + \ pontos + (2k + 1) $

$ = 1 + 3 + 5 + \ pontos + (2k - 1) + (2k + 1) $

$ = k ^ 2 + (2k + 1) $

$ = (k + 1) ^ 2 $

Portanto, $ 1 + 3 + 5 + \ dots + (2 (k + 1) - 1) = (k + 1) ^ 2 $ mantém o que satisfaz a etapa 2.

Portanto, $ 1 + 3 + 5 + \ dots + (2n - 1) = n ^ 2 $ está provado.

Problema 3

Prove que $ (ab) ^ n = a ^ nb ^ n $ é verdadeiro para todo número natural $ n $

Solution

Step 1 - Para $ n = 1, (ab) ^ 1 = a ^ 1b ^ 1 = ab $, Portanto, a etapa 1 é satisfeita.

Step 2 - Suponhamos que a afirmação seja verdadeira para $ n = k $. Portanto, $ (ab) ^ k = a ^ kb ^ k $ é verdadeira (é uma suposição).

Temos que provar que $ (ab) ^ {k + 1} = a ^ {k + 1} b ^ {k + 1} $ também valem

Dado, $ (ab) ^ k = a ^ kb ^ k $

Ou $ (ab) ^ k (ab) = (a ^ kb ^ k) (ab) $ [Multiplicando ambos os lados por 'ab']

Ou $ (ab) ^ {k + 1} = (aa ^ k) (bb ^ k) $

Ou $ (ab) ^ {k + 1} = (a ^ {k + 1} b ^ {k + 1}) $

Portanto, a etapa 2 é comprovada.

Portanto, $ (ab) ^ n = a ^ nb ^ n $ é verdadeiro para todo número natural n.

Indução forte

A indução forte é outra forma de indução matemática. Através desta técnica de indução, podemos provar que uma função proposicional, $ P (n) $ é verdadeira para todos os inteiros positivos, $ n $, usando os seguintes passos -

• Step 1(Base step) - Prova que a proposição inicial $ P (1) $ verdadeira.

• Step 2(Inductive step) - Prova que a afirmação condicional $ [P (1) \ land P (2) \ land P (3) \ land \ dots \ land P (k)] → P (k + 1) $ é verdadeira para inteiros positivos $ k $.