Artigos

1.3: Os Números Naturais e Indução Matemática


Assumiremos familiaridade com o conjunto ( mathbb {N} ) de números naturais, com as operações aritméticas usuais de adição e multiplicação em ( mathbb {n} ), e com a noção do que isso significa para um o número natural seja menor que o outro.

Além disso, também assumiremos a seguinte propriedade dos números naturais.

Propriedade de boa ordem dos números naturais

Se (A ) é um subconjunto não vazio de ( mathbb {N} ), então existe um elemento ( ell in A ) tal que ( ell leq x ) para todos (x em A ).

Para parafrasear a propriedade anterior, cada subconjunto não vazio de inteiros positivos tem um menor elemento.

O princípio da indução matemática é uma ferramenta útil para provar fatos sobre sequências.

Teorema ( PageIndex {1} ): Princípio da Indução Matemática

Para cada número natural (n in mathbb {N} ), suponha que (P (n) ) denota uma proposição que é verdadeira ou falsa. Seja (A = {n in mathbb {N}: P (n) text {é verdadeiro} } ). Suponha que as seguintes condições sejam válidas:

  1. (1 em A ).
  2. Para cada (k in mathbb {N} ), se (k in A ), então (k + 1 in A ).

Então (A = mathbb {N} ).

Prova

Suponha que as condições (a) e (b) sejam válidas. Suponha, por meio de contradição, que (A neq mathbb {N} ). Defina (B = mathbb {N} barra invertida A ), ou seja, (B = {n in mathbb {N}: P (n) texto {é falso} } ). Então (B ) é um subconjunto não vazio de ( mathbb {N} ). Pela propriedade de boa ordem dos números naturais, existe um menor elemento ( ell in B ) e, portanto, temos que (P (k) ) é verdadeiro. Pela condição (b), obtemos que (P (k + 1) ) é verdadeiro. Mas (k + 1 = ell ), e (P ( ell) ) é falso, pois ( ell in B ). Isso é uma contradição, então a conclusão segue. (quadrado)

Parafraseando, o princípio diz que, dada uma lista de proposições (P (n) ), uma para cada (n in mathbb {N} ), se (P (1) ) for verdadeira e , além disso, (P (k + 1) ) é verdadeiro sempre que (P (k) ) é verdadeiro, então todas as proposições são verdadeiras.

Iremos nos referir a este princípio como indução matemática ou simplesmente indução. A condição (a) acima é chamada de caso base e condição (b) o passo indutivo. Ao provar (b), a declaração (P (k) ) é chamada de hipótese indutiva.

Exemplo ( PageIndex {1} )

Prove usando indução que para todos (n in mathbb {N} )

[1 + 2 + cdots + n = frac {n (n + 1)} {2}. ]

Solução

A afirmação (P (n) ) é a igualdade (1 + 2 + cdots + n = frac {n (n + 1)} {2} ). Agora, o caso base diz que (1 = frac {1 (1 + 1)} {2} ), o que é claramente verdade.

Suponha que (P (k) ) seja verdadeiro para algum (k in mathbb {N} ). Ou seja, suponha que (1 + 2 + cdots + n = frac {k (k + 1)} {2} ) (esta é a hipótese indutiva). Agora temos

[1 + 2 + cdots + k + (k + 1) = frac {k (k + 1)} {2} + (k + 1) = frac {k (k + 1) +2 (k + 1)} {2} = frac {(k + 1) (k + 2)} {2}. ]

Isso mostra que (P (k + 1) ) é verdadeiro. Agora provamos as condições (a) e (b) do Teorema 1.3.1. Portanto, pelo princípio da indução matemática, concluímos que

[1 + 2 + cdots + n = frac {n (n + 1)} {2} text {para todos} n in mathbb {N}. ]

Exemplo ( PageIndex {2} )

Prove usando indução que para todos (n in mathbb {N}, 7 ^ {n} -2 ^ {n} ) é divisível por 5.

Solução

Para (n = 1 ), temos (7-2 = 5 ), que é claramente um múltiplo de 5.

Suponha que (7 ^ {k} -2 ^ {k} ) seja um múltiplo de 5 para algum (k in mathbb {N} ). Ou seja, existe um inteiro (j ) tal que (7 ^ {k} -2 ^ {k} = 5 j ). Vamos escrever (7 ^ {k} -2 ^ {k} = 5 j ). Agora, substituindo esta expressão abaixo, temos

[7 ^ {k + 1} -2 ^ {k + 1} = 7 cdot 7 ^ {k} -2 cdot 2 ^ {k} = 7 left (2 ^ {k} +5 j right ) -2 cdot 2 ^ {k} = 7 cdot 2 ^ {k} -2 cdot 2 ^ {k} +7 cdot 5 j = 2 ^ {k} (7-2) +5 cdot 7 j = 5 left (2 ^ {k} +7 j right) ]

Segue-se que (7 ^ {k + 1} -2 ^ {k + 1} ) é um múltiplo de 5. Isso prova a etapa indutiva.

Concluímos por indução que (7 ^ {n} -2 ^ {n} ) é divisível por 5 para todos (n in mathbb (N) ).

Exemplo ( PageIndex {3} )

Prove usando indução que para todos (n in mathbb {N} )

[n + 1 leq 2 ^ {n} ]

Solução

Para (n = 1 ), temos (1 + 1 = 2 = 2 ^ {1} ), então o caso base é verdadeiro.

Suponha a seguir que (k + 1 leq 2 ^ {k} ) para algum (k in mathbb {N} ). Então (k + 1 + 1 leq 2 ^ {k} +1 ). Como (2 ^ {k} ) é um número inteiro positivo, também temos (1 leq 2 ^ {k} ). Portanto,

[(k + 1) +1 leq 2 ^ {k} +1 leq 2 ^ {k} + 2 ^ {k} = 2 cdot 2 ^ {k} = 2 ^ {k + 1}. ]

Concluímos pelo princípio da indução matemática que (n + 1 leq 2 ^ {n} ) para todos (n in mathbb {N} ).

O seguinte resultado é conhecido como Princípio Generalizado de Indução Matemática. Ele simplesmente afirma que podemos iniciar o processo de indução em qualquer número inteiro (n_ {0} ), e então obtemos a verdade de todas as afirmações (P (n) ) para (n geq n_ {0} )

Teorema ( PageIndex {2} ) - Princípio Generalizado da Indução Matemática.

Seja (n_ {0} in mathbb {N} ) e para cada (n geq n_ {0} ) natural, suponha que (P (n) ) denota uma proposição que é verdadeira ou falso. Seja (A = {n in mathbb {N}: P (n) text {é verdadeiro} } ). Suponha que as seguintes duas condições sejam válidas:

  1. (n_ {0} em A ).
  2. Para cada (k in mathbb {N} ), (k geq n_ {0} ), se (k in A ), então (k + 1 in A ).
Prova

Suponha que as condições (a) e (b) sejam válidas. Suponha, por meio de contradição, que (A nsupseteq {k in mathbb {N}: left.k geq n_ {0} right } ). Defina (B = left {n in mathbb {N}: n geq n_ {0}, P (n) text {is false} right } ). Pela propriedade de boa ordem dos números naturais, existe um menor elemento ( ell in B ). Pela condição (a), (n_ {0} notin B ). Portanto, ( ell geq n_ {0} +1 ). Segue-se que (k = ell-1 geq n_ {0} ). Uma vez que (k < ell ), (k notin B ) e, portanto, temos que (P (k) ) é verdadeiro. (quadrado)

Exemplo ( PageIndex {4} )

Prove por indução que (3 n <2 ^ { prime} ) para todos (n geq 4 ).

Solução

A afirmação é verdadeira para (n = 4 ) desde (12 <16 ). Suponha a seguir que (3 k <2 ^ {k} ) para algum (k in mathbb {N} ), (k geq 4 ). Agora,

[3 (k + 1) = 3 k + 3 <2 ^ {k} +3 <2 ^ {k} + 2 ^ {k} = 2 ^ {k + 1}, ]

onde a segunda desigualdade segue desde (k geq 4 ) e, portanto, (2 ^ {k} geq 16> 3 ). Isso mostra que (P (k + 1) ) é verdadeiro. Assim, pelo princípio generalizado de indução, a desigualdade vale para todos (n geq 4 ).

A seguir, apresentamos outra variante do princípio de indução que torna mais fácil provar a etapa indutiva. Apesar do nome, este princípio é equivalente ao padrão.

Teorema ( PageIndex {3} ) - Princípio da Indução Forte.

Para cada (n in mathbb {N} ) natural, suponha que (P (n) ) denota uma proposição que é verdadeira ou falsa. Suponha que as seguintes duas condições sejam válidas:

  1. (1 em A ).
  2. Para cada (k in mathbb {N} ), se (1,2, ldots, k in A ), então (k + 1 in A )

Então (A = mathbb {N} ).

Prova

Adicione a prova aqui e ela será automaticamente ocultada

Comentário ( PageIndex {4} )

Observe que a etapa indutiva acima diz que, para provar que (P (k + 1) ) é verdadeiro, podemos assumir não apenas que (P (k) ) é verdadeiro, mas também que (P ( 1), P (2), ldots, P (k-1) ) são verdadeiros.

Também existe uma versão generalizada deste teorema onde o caso base é para algum inteiro (n_ {0}> 1 ).

Exemplo ( PageIndex {5} )

Prove por indução que todo número inteiro positivo maior que 1 é um número primo ou um produto de números primos.

Solução

Claramente, a afirmação é verdadeira para (n = 2 ). Suponha que a declaração seja válida para qualquer inteiro positivo (m in {2, ldots, k } ), onde (k in mathbb {N} ), (k geq 2 ). Se (k + 1 ) for primo, a afirmação vale para (k + 1 ). Caso contrário, existem inteiros positivos (p, q> 1 ) tais que (k + 1 = pq ). Como (p, q leq k ), pela suposição indutiva aplicada a (p ) e (q ), podemos encontrar números primos (r_ {1}, ldots, r _ { ell} ) e (s_ {1}, ldots, s_ {m} ) de modo que (p = r_ {1} cdots r _ { ell} ) e (q = s_ {1} cdots s_ {m} ) (observe que ( ell ) e (m ) podem ser iguais a 1). Mas então

[k + 1 = r_ {1} cdots r _ { ell} s_ {1} cdots s_ {m} ]

Portanto, a afirmação é verdadeira para (k + 1 ). A conclusão agora segue pelo princípio da indução forte.

Exercício ( PageIndex {1} )

Prove o seguinte usando a indução matemática.

  1. (1 ^ {2} + 2 ^ {2} + cdots + n ^ {2} = frac {n (n + 1) (2 n + 1)} {6} text {para todos} n em mathbb {N} ).
  2. (1 ^ {3} + 2 ^ {3} + cdots + n ^ {3} = frac {n ^ {2} (n + 1) ^ {2}} {4} text {para todos} n in mathbb {N} ).
  3. (1 + 3 + cdots + (2 n-1) = n ^ {2} text {para todos} n in mathbb {N} ).
Responder

Adicione textos aqui. Não exclua este texto primeiro.

Exercício ( PageIndex {2} )

Prove que para todos (n in mathbb {N} ), (9 ^ {n} -5 ^ {n} ) é divisível por (4 ).

Responder

Adicione textos aqui. Não exclua este texto primeiro.

Exercício ( PageIndex {3} )

Prove que para todos (n in mathbb {N} ), (7 ^ {n} -1 ) é divisível por (3 )

Responder

Adicione textos aqui. Não exclua este texto primeiro.

Exemplo ( PageIndex {4} )

Prove o seguinte usando indução.

  1. (2 n + 1 leq 2 ^ {n} ) para (n geq 3 ) ( (n in mathbb {N} )).
  2. (n ^ {2} leq 3 ^ {n} ) para todos (n in mathbb {N} ). (Dica: mostre primeiro que para todos (n in mathbb {N} ), (2 n leq n ^ {2} +1 ). Isso não requer indução ..)
  3. (n ^ {3} leq 3 ^ {n} ) para todos (n in mathbb {N} ). (Dica: Verifique os casos (n = 1 ) e (n = 2 ) diretamente e, em seguida, use a indução para (n geq 3 ).)

Solução

Adicione texto aqui.

Exercício ( PageIndex {5} )

Dado um número real (a neq 1 ), prove que

[1 + a + a ^ {2} + cdots + a ^ {n} = frac {1-a ^ {n + 1}} {1-a} text {for all} n in mathbb {N}. ]

Responder

Adicione textos aqui. Não exclua este texto primeiro.

Exercício ( PageIndex {6} )

A sequência de Fibonacci é definida por

[a_ {1} = a_ {2} = 1 text {e} a_ {n + 2} = a_ {n + 1} + a_ {n} text {for} n geq 1. ]

Provar

[a_ {n} = frac {1} { sqrt {5}} left [ left ( frac {1+ sqrt {5}} {2} right) ^ {n} - left ( frac {1- sqrt {5}} {2} right) ^ {n} right]. ]

Responder

Adicione textos aqui. Não exclua este texto primeiro.

Exercício ( PageIndex {7} )

Let (a geq-1 ). Prove por indução que

[(1 + a) ^ {n} geq 1 + n a text {para todos} n in mathbb {N}. ]

Responder

Adicione textos aqui. Não exclua este texto primeiro.

Exercício ( PageIndex {8} )

Seja (a, b in mathbb {R} ) e (n in mathbb {N} ). Use a indução matemática para provar o teorema binomial

[(a + b) ^ {n} = sum_ {k = 0} ^ {n} left ( begin {array} {l}
n
k
end {array} right) a ^ {k} b ^ {n-k}, ]

onde ( left ( begin {array} {l}
n
k
end {array} right) = frac {n!} {k! (n-k)!} ).

Responder

Adicione textos aqui. Não exclua este texto primeiro.


PLANILHA DE INDUÇÃO MATEMÁTICA COM RESPOSTAS

1! + (2 × 2!) + (3 × 3!) +. + (n × n!) = (n + 1)! - 1.

(10) & # xa0 & # xa0 Usando a indução matemática, mostre que para qualquer número natural n, x 2n & # xa0− y 2n & # xa0é divisível por x + y. & # Xa0 & # xa0 Solução

(11) & # xa0 & # xa0 Pelo princípio da indução matemática, prove que, para n ≥ 1, & # xa0 & # xa0 1 2 & # xa0 + 2 2 & # xa0 + 3 2 & # xa0 + · · · + n 2 & # xa0 & gt & # xa0 n 3/3 & # xa0 & # xa0 & # xa0 & # xa0 Solução

(12) & # xa0 & # xa0 Use indução para provar que n 3 & # xa0− 7n + 3, é divisível por 3, para todos os números naturais n. & # Xa0 & # xa0 & # xa0 Solução

(13) & # xa0 Use a indução para provar que 10 n & # xa0 + 3 × 4 n + 2 & # xa0 + 5 é divisível por 9, para todos os números naturais n. & # xa0 & # xa0 & # xa0 Solução

Além do material fornecido acima, & # xa0 se você precisar de qualquer outro material em matemática, use nossa pesquisa personalizada do Google aqui.

Se você tiver algum comentário sobre nosso conteúdo de matemática, envie-nos um e-mail: & # xa0

Sempre apreciamos seus comentários. & # Xa0

Você também pode visitar as seguintes páginas da web sobre diferentes assuntos em matemática. & # Xa0


Perguntas semelhantes

Use a indução matemática para mostrar que a afirmação 2 + 6 + 10 +. . . + (4n - 2) = 2n ^ 2 é verdadeiro

Pré-cálculo

Você pode verificar minhas respostas? 1. Qual das alternativas a seguir mostra a melhor próxima etapa para provar o seguinte por indução matemática? 3 ^ n> n * 2 ^ n, n≥1 1. Quando n = 1, a fórmula é válida porque 3 ^ 1 1 * 2 ^ 1 3> 2 2. Supondo que 3 ^ k> k * 2 ^ k

Pré-cálculo

Você pode verificar minhas respostas? 1. Encontre Pk + 1 se Pk = 2 ^ K-1 / k! resposta: 2 ^ k + 1 / (k + 1)! 2. Encontre Pk + 1 se Pk = 7 + 13 + 19 +. + [6 (k - 1) +1] + (6k + 1) resposta: 7 + 13 + 9. (6k-1 + 1) + 6k + 1 + (6k + 2) 3. Qual é a primeira etapa ao escrever um

Indução matemática

Use a indução matemática para provar que o seguinte é verdadeiro. 8 + 11 + 14. + (3n + 5) = 1 / 2n (3n + 13), para todo n no conjunto dos números naturais.

Usando a indução matemática, prove o seguinte: a) 6 ^ n - 1 é divisível por 5, para n> _0.

Pré-cálculo

você pode verificar minha resposta? 2. Qual das alternativas a seguir mostra a melhor próxima etapa para provar o seguinte por indução matemática? n!> 2 ^ n, n≥4 1. Quando n = 1 a fórmula é válida porque 4!> 2 ^ 4 24> 16 2. Supondo que k!> 2 ^ k mostre que

Indução matemática. Eu & # 039 estou preso. Até agora eu tenho ..

Para todos os inteiros n ≥ 1, prove a seguinte afirmação usando indução matemática. 1 + 2 ^ 1 + 2 ^ 2 +. + 2 ^ n = 2 ^ (n + 1) −1 Aqui está o que eu tenho até agora 1. Prove o passo base seja n = 1 2 ^ 1 = 2 ^ (1 + 1) -1 Falso. Alguém sugeriu que o


Prova por Indução Matemática

É necessário provar uma sequência infinita de afirmações para a prova por indução, uma forma rigorosa de raciocínio dedutivo.

Objetivos de aprendizado

Use a indução matemática para provar uma sequência infinita de afirmações

Principais vantagens

Pontos chave

  • A indução matemática é um método de prova matemática normalmente usado para estabelecer que uma determinada afirmação é verdadeira para todos os números naturais.
  • Isso é feito provando que a primeira afirmação na seqüência infinita de afirmações é verdadeira e, em seguida, provando que se alguma afirmação na seqüência infinita de afirmações é verdadeira, então a próxima também é.
  • Provar uma sequência infinita de afirmações pode ser entendido no contexto do efeito dominó, que por natureza medeia uma ordem sequencial e previsível de eventos.

Termos chave

  • raciocínio indutivo: O processo de fazer inferências com base em padrões observados ou simples repetição. Freqüentemente usado em referência a previsões sobre o que acontecerá ou acontecerá, com base no que aconteceu.

A indução matemática é um método de prova matemática normalmente usado para estabelecer que uma determinada afirmação é verdadeira para todos os números naturais (inteiros não negativos). Isso é feito provando que a primeira afirmação na seqüência infinita de afirmações é verdadeira e, em seguida, provando que, se alguma afirmação na seqüência infinita de afirmações é verdadeira, então a próxima também é.

A forma mais simples e comum de indução matemática prova que uma afirmação envolvendo um número natural [latex] n [/ latex] é válida para todos os valores de [latex] n [/ latex]. A prova consiste em duas etapas:

  1. A base (caso base): mostrando que a afirmação é válida quando [latex] n [/ latex] é igual ao menor valor que [latex] n [/ latex] é dado na questão. Normalmente, [latex] n = 0 [/ latex] ou [latex] n = 1 [/ latex].
  2. A etapa indutiva: mostrando que se a declaração vale para algum [latex] n [/ latex], então a declaração também vale quando [latex] n + 1 [/ latex] é substituído por [latex] n [/ latex].

A suposição na etapa indutiva de que a afirmação é válida para algum [latex] n [/ latex] é chamada de hipótese de indução (ou hipótese indutiva). Para realizar a etapa indutiva, assume-se a hipótese de indução e, em seguida, usa-se essa hipótese para provar a afirmação para [latex] n + 1 [/ latex].

A escolha entre [latex] n = 0 [/ latex] e [latex] n = 1 [/ latex] no caso base é específica para o contexto da prova: Se [latex] 0 [/ latex] é considerado natural número, como é comum nos campos de combinatória e lógica matemática, então [latex] n = 0 [/ latex]. Se, por outro lado, [latex] 1 [/ latex] for considerado o primeiro número natural, então o caso base é dado por [latex] n = 1 [/ latex].

Este método funciona provando primeiro que a afirmação é verdadeira para um valor inicial e, em seguida, provando que o processo usado para ir de um valor para o próximo é válido. Se ambos forem comprovados, qualquer valor pode ser obtido executando o processo repetidamente.

Visualização

Pode ser útil pensar no efeito dominó. Se for apresentado a alguém uma longa fileira de dominós em pé, pode-se ter certeza de que:

Assim, conclui-se que todos os dominós vão cair, e que esse fato é inevitável.

Dominó: A indução matemática pode ser ilustrada informalmente por referência ao efeito sequencial da queda de dominó.

Prove a seguinte afirmação: Para cada número inteiro positivo [latex] n [/ latex],

Caso Base: primeiro temos que verificar se a instrução é válida para [latex] n = 0 [/ latex]. No lado esquerdo da equação, temos apenas [latex] 0 [/ latex]. No lado direito da equação, substituímos [latex] n = 0 [/ latex]. Assim, temos [latex] displaystyle <0 = frac <0 (0 + 1)> <2>> [/ latex], que pode ser simplificado para [latex] 0 = 0 [/ latex]. Provamos que a afirmação é verdadeira para o caso base de [latex] n = 0 [/ latex].

Etapa indutiva: assuma que a afirmação vale para [latex] n = k [/ latex] e verifique se ela vale para [latex] n = k + 1 [/ latex] também. Em outras palavras, queremos mostrar que a afirmação é verdadeira quando substituímos [latex] k + 1 [/ latex] por [latex] n [/ latex]:

Observe que podemos usar a hipótese de indução de que a afirmação vale para [latex] n = k [/ latex] para reescrever o lado esquerdo da equação:

Agora podemos reescrever essa declaração e mostrar que ela é igual ao lado direito da declaração anterior. Em outras palavras, se pudermos mostrar que o seguinte é verdadeiro, mostraremos que [latex] displaystyle <0 + 1 + 2 + cdots + n = frac<2>> [/ latex] é verdadeiro para [latex] k + 1 [/ latex]:

Podemos reescrever [latex] displaystyle < frac <2> + (k + 1)> [/ latex] algebricamente da seguinte forma:

Isso é exatamente o que queríamos provar. Mostramos que [latex] displaystyle <0 + 1 + 2 + cdots + n = frac<2>> [/ latex] é verdadeiro para qualquer [latex] n = k + 1 [/ latex] se for verdadeiro para [latex] n = k [/ latex]. Isto completa a etapa de indução. Concluímos que a afirmação é válida para todo inteiro não negativo [latex] n [/ latex].


Tesouro matemático: Augustus De Morgan e a indução matemática

De acordo com Florian Cajori, a indução matemática foi sugerida por Jakob Bernoulli, John Wallis, Blaise Pascal, Pierre Fermat, Francesco Maurolico e Campanus de Novara. Como afirma Cajori, se lermos & ldquoa um pouco nas entrelinhas, podemos encontrar traços de indução matemática ainda mais cedo, nos escritos dos hindus e gregos, como, por exemplo, no & # 39 método cíclico & # 39 de Bhaskara, e na prova de Euclides de que o número de primos é infinito. & rdquo

Cajori afirma que a publicação importante na fixação do nome & quotindução matemática & quot e contendo o que é considerado o primeiro uso moderno do método é o artigo & quotIndução (Matemática) & quot de Augustus De Morgan & quot no volume 12 do Penny Cyclopedia (Londres, 1838), pp. 465 e ndash466. De Morgan foi um colaborador frequente do Cyclopedia. Embora ele tenha usado o também novo nome de & ldquosuccessive induction & rdquo na maior parte do artigo, sua menção improvisada de & ldquomathematical induction & rdquo no final do artigo foi o termo que pegou com os leitores.

Página de título do volume 12 do Penny Cyclopedia (1838). Arquivo da Internet.

As duas páginas do artigo de De Morgan sobre indução matemática (1838). Da coleção do Dr. Sid Kolpas.

Segue-se a transcrição de parte do artigo.

INDUÇÃO (Matemática). O método de indução, no sentido em que a palavra é usada na filosofia natural, não é conhecido na matemática pura. Certamente há casos em que uma proposição geral é provada por uma coleção de demonstrações de diferentes casos, o que pode lembrar o investigador do processo indutivo, ou a coleção do geral do particular. Tais casos, entretanto, não devem ser considerados permanentes, pois geralmente acontece que uma demonstração geral é descoberta assim que a atenção é voltada para o assunto. No entanto, existe um método particular que é extremamente comum no raciocínio matemático, e

ao qual propomos dar o nome de indução sucessiva. Tem o caráter principal de indução na física, porque é realmente a coleção de uma verdade geral de uma demonstração que implica o exame de cada caso particular, mas difere do processo da física na medida em que cada caso depende do anterior. Substituindo, entretanto, a demonstração pela observação, o processo matemático tem uma analogia com o experimental, que, em nossa opinião, é uma justificativa suficiente para o termo & lsquosuccessive induction. & Rdquo Alguns exemplos do método permitirão ao leitor matemático reconhecer um modo de investigação com a qual ele já está familiarizado.

Exemplo 1.-A soma de qualquer número de números ímpares sucessivos, começando da unidade, é um número quadrado, ou seja, o quadrado da metade do número par que segue o último número ímpar. Seja esta proposição verdadeira em qualquer instância única, isto é, sendo n algum número inteiro, seja 1, 3, 5,. até 2n + 1 juntos dão (n + 1) 2. Então o próximo número ímpar sendo 2n + 3, a soma de todos os números ímpares até 2n + 3 será (n + 1) 2 + 2n + 3, ou n 2 + 4n + 4, ou (n + 2) 2 . Mas n + 2 é a metade do número par a seguir a 2n + 3: conseqüentemente, se a proposição for verdadeira para qualquer conjunto de números ímpares, será verdadeira para mais um. Mas é verdade para o primeiro número ímpar 1, pois este é o quadrado da metade do número par seguinte. Consequentemente, sendo verdadeiro para 1, é verdadeiro para 1 + 3 sendo verdadeiro para 1 + 3, é verdadeiro para 1 + 3 + 5 sendo verdadeiro para 1 + 3 + 5, é verdadeiro para 1 + 3 + 5 + 7 e assim por diante, ad infinitum.

O exemplo 1 é essencialmente como I & rsquove ensinou indução matemática no ensino médio e na faculdade.

Referências

Cajori, Florian. & ldquoOrigem do nome & # 39 Indução matemática & # 39. & rdquo The American Mathematical Monthly 25, não. 5 (maio de 1918): 197 e ndash201.

A Sociedade para a Difusão de Conhecimento Útil. The Penny Cyclopedia, Vol. XII, pp. 465 e ndash466. Londres: Charles Knight and Co., 1838.

Sidney J. Kolpas (Delaware County Community College), "Mathematical Treasure: Augustus De Morgan and Mathematical Induction," Convergência (Fevereiro de 2019)


Mais um exemplo

Vamos mostrar isso para o conjunto G= <8,9,10. >, cada elemento de G é uma soma de 3 e 5. (Matematicamente, dizemos que esses inteiros são uma & quot combinação linear & quot de 3 e 5.)

A variável na qual estamos fazendo a indução é n.

A propriedade que estamos tentando provar é que para cada n no set G= <8,9,10. >, existem inteiros não negativos você e v de tal modo que n = 3u + 5v.

Base O menor elemento do nosso conjunto é 8 e 8 = 3 + 5. Essa foi fácil. Etapa de indução Assumindo que n é uma soma de 3 e 5, vamos mostrar que n + 1 é também. Assim, nossa hipótese de indução é n = 3u + 5v para alguns você e v, e desejamos provar, com base nessa suposição, que n + 1 = 3u '+ 5v' para alguns você' e v '. Se v & gt 0, então podemos pegar u '= u + 2 e v '= v-1.

Por outro lado, se v = 0, então u & gt = 3, porque o menor número em G é 8. Então, neste caso, temos
n
+1 = 3(você-3) + 5 * 2, para que possamos pegar u '= u-3 e v '= 2.


3 respostas 3

Na verdade, é possível que o princípio da indução seja muito mais geral do que você pode pensar. Existem muitos teoremas de indução que você pode provar para o mais intuitivo deles, se você compreender a ideia principal que é bem fundada, ou bem ordenada. (mas talvez seja muito cedo para você se beneficiar do esforço que você teria que fazer para entender essas noções)

O teorema de indução usual para $ mathbb$ pode ser comprovado usando indução regular. Pode ser declarado como:

Se uma propriedade $ P (x) $ satisfaz $ P (n) $ para algum inteiro $ n $ e $ forall k in mathbb(P (k) longrightarrow P (k-1) $ e $ P (k + 1)) $, então é verdadeiro para todo inteiro.

Se você não sabe como provar o PMI usando o fato de que todo subconjunto não vazio de $ mathbb$ tem menos elemento, sugiro que você procure uma prova. Lembro que fiquei muito feliz ao descobrir isso na época em que pensava que PMI era apenas algum tipo de crença comum entre os matemáticos e ainda é um teorema muito interessante para mim.

Não vejo nenhuma razão para que não seja possível.

Isto é possível - é simplesmente encontrado com menos frequência. Tem havido uma série de postagens (por exemplo, indução em números reais) que tratam da indução como não relacionada a números naturais. Também houve alguns artigos, alguns de código aberto e alguns publicados profissionalmente (não mutuamente exclusivos), publicados sobre o assunto. Lembro-me de um aparecendo o College Mathematics Journal não há muito tempo.

Com relação à sua própria pergunta sobre algo como $ P (-1) $ ou inteiros em geral, há um tempo atrás houve uma pergunta sobre o uso de um número negativo como um caso base. A resposta curta é sim, você pode usar um número negativo em seu (s) caso (s) base. É apenas um pouco atípico. Para qualquer um que não esteja interessado em ver a resposta no outro tópico, abaixo está um exemplo de como provar uma afirmação para todos os $ n geq -5 $ por indução.

Exemplo: Suponha que você tenha a declaração $ S (n) $ onde $ S (n): n + 5 geq 0, $ e você afirma que isso é verdadeiro para todos os $ n geq -5 $, onde $ n in mathbb$. Seu caso base seria $ n = -5 $, e isso é verdade porque $ -5 + 5 = 0 geq 0 $. Conforme explicado acima, quando reformulamos a proposição, o caso base seria $ T (1) = 0 = S (-5) = S (k) $. O seguinte esquema pode ser mais fácil de entender: $ color equiv S (n + k-1): (n + k-1) +5 geq 0 equiv n + k + 4 geq 0 equiv underbrace < color>_cor< geq 0> Downarrow [1em] color. $ Como você pode ver acima, provar que $ S (n) $ é verdadeiro para todos os $ n geq -5 $ é exatamente o mesmo que provar que $ T (n) $ é verdadeiro para todos os $ n geq 1 $.


Conteúdo

A indução matemática é freqüentemente declarada com o valor inicial 0 (em vez de 1). Na verdade, funcionará tão bem com uma variedade de valores iniciais. Aqui está um exemplo quando o valor inicial é 3: "A soma dos ângulos internos de um polígono de n < displaystyle n> lados é (n - 2) 180 < displaystyle (n-2) 180> graus."

Existem muitos objetos matemáticos para os quais as provas por indução matemática funcionam. O termo técnico é um conjunto bem ordenado.

A mesma ideia pode funcionar para definir um conjunto de objetos, bem como para provar afirmações sobre esse conjunto de objetos.

Existe um conjunto de axiomas para a aritmética dos números naturais que se baseia na indução matemática. Isso é chamado de "Axiomas de Peano". Os símbolos indefinidos são | e =. Os axiomas são

Pode-se então definir as operações de adição e multiplicação e assim por diante por indução matemática. Por exemplo:


Dominó e indução matemática

Se você colocasse dez mil dominós na fila em uma mesa muito longa e quisesse deixá-los cair apenas deixando o primeiro dominó cair, como o faria?

A melhor ideia provavelmente é colocá-los em uma fila de forma que:

  1. Quando o primeiro dominó cair, ele atingirá o segundo dominó.
  2. Certifique-se de que cada dominó atingirá o dominó próximo a ele e que cada dominó atingido cairá.
  3. Se as condições (1) e (2) forem satisfeitas, todos os dominós cairão.

Na verdade, não importa quantos dominós colocamos na mesa, desde que as condições (1) e (2) sejam satisfeitas, temos certeza de que todos os dominós cairão.

E quanto à matemática?

Indução matemática afirma que se é uma condição e é verdadeiro, e para um número natural, se então é verdadeiro, então é verdadeiro para todo inteiro positivo.

Por exemplo, queremos adicionar os primeiros números naturais, podemos observar que

Se continuarmos, podemos observar que

e podemos ser tentados a adivinhar que

Você pode querer tentar mais alguns casos.

Observe que o sinal ... significa o tempo todo. Isso significa que queremos adicionar todos os inteiros de até.

Nossa suposição acima está realmente correta (por quê?), Mas não sabemos se essa fórmula ou estratégia sempre funciona para todos os números positivos. Por exemplo, como sabemos se a fórmula funciona se o maior número for, ou, ou. Claro, não podemos enumerar todos os números de contagem, então precisamos ter uma justificativa ou prova de nossa conjectura acima. A estratégia usada para provar tais conjecturas é chamada prova por indução matemática.

Na indução matemática, se nossa condição for verdadeira para o número natural, e uma vez que seja verdadeira para qualquer número natural, também o será para, então a condição será verdadeira para todos os inteiros positivos. Se não estiver claro, faça esta analogia:

Suponha que temos um número infinito de dominós enfileirados e, uma vez que empurramos o primeiro dominó (este é o nosso), ele atinge o próximo dominó e o segundo cai. Agora, se para cada um, se o dominó atingido cair (este é o nosso) e atingir o próximo dominó e novamente aquele (este é o nosso), então temos certeza de que todos os dominós em pé cairão, não importa o tamanho da fila.

Agora, para o nosso problema, queremos mostrar que a soma dos números de a qualquer número diz, ou escrito como

Observe que n é qualquer número inteiro positivo. Verificamos se a condição é verdadeira para.

Sim, isso é verdade. O lado direito do sinal de igual, de fato, é igual.

Devemos mostrar que isso também é verdade. Isso é que devemos mostrar que

Observe que, como apenas substituímos todos por no lado direito do lado da equação.


Usando indução matemática, prove que n ^ 3 + 2n é divisível por 3 para todos os inteiros n

A indução funciona da seguinte maneira: se você mostrar que o resultado sendo verdadeiro para qualquer número inteiro implica que é verdadeiro para o próximo, você só precisa mostrar que é verdadeiro para n = 1 para que seja verdadeiro para n = 2 e então n = 3 e assim por diante.

Etapa 1: mostrar verdadeiro para n = 1

3 é definitivamente divisível por 3, então a afirmação é verdadeira para n = 1.

Etapa 2: assumir verdadeiro para n = k

Assumimos que para qualquer inteiro k, n ^ 3 + 2n é divisível por 3. Podemos escrever isso matematicamente como:

k ^ 3 + 2k = 3m, onde m é um número inteiro

Etapa 3: mostrar verdadeiro para k + 1

Substituição da parte 2 para (k ^ 3 + 2k), Nós temos:

que é divisível por 3.

Isso significa que a afirmação sendo verdadeira para n = k implica que a afirmação é verdadeira para n = k + 1 e, como mostramos que é verdadeira para n = 1, a prova da afirmação segue por indução.


Assista o vídeo: INDUÇÃO FINITA - Exercicio 5 (Novembro 2021).