Olá, gente, hoje iniciarei uma seção em que darei algumas dicas importantes para a resolução de diversos problemas. Essa Seção ficará aberta para sempre, para que eu possa acrescentar artigos com alguma frequência. Como plano inicial, espero que até o final de Julho esta secção esteja com alguns artigos sobre métodos de demonstrações matemáticas e outras dicas bem importantes. Hoje falarei sobre o Principio da Indução Finita ou Método de Indução Matemática e suas variações.
Antes de explicar esse tema muito amplo, citarei alguns exemplos.
* mostre que: ![1+2+3+4+5+...+n= \frac{(n+1).n}{2} \forall n \ge 1 [;1+2+3+4+5+...+n= \frac{(n+1).n}{2} \forall n \ge 1;]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_vlLC7tLo1UBA2d2Tg1P8zQvy9TM78Yz5cho5PHB9ydS-udeBDbPKKAnEWzFXJzdnbRrGg8-4hWiAYM_F2xzjzbO0EeSWd-LbhBjdyMHKcwCsC2qIb-Jmxat0DUiaTnkguiBqdJBTcdt5NUZhxWj-0Q-uEEkPBo4tBjj3Rfkq3IiNL2C7Zo-lL_9Q=s0-d)
* mostre que: ![1^2+2^2+3^2+...+n^2= \frac{n \times(n+1) \times(2n+1)}{6} \forall n \ge 1 [;1^2+2^2+3^2+...+n^2= \frac{n \times(n+1) \times(2n+1)}{6} \forall n \ge 1;]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_vGJlAn1WuDRLeRyAw3uOwto5BQWezSpRuC8z-zESY4egLI0jDhlj7Vs1AX7gLALAzyxtcr3LJfxdSIgtQAeDXGCXCW9HD_CiLmDHwIOgfcCo_xQSOql-j4PV79eZh52eXb7dXCXq63-Cc9PX7qp4_pbbgz9xTwP7v-RKy0GnSIjKq3Pny6W4DuIkdInYgZrVH4NBz4bQbVXr-a3oyw-0XDhEGgpoSegvOjEEtRZktswzCHIplDhmMilhdO=s0-d)
* mostre que: ![1^3+2^3+3^3+...+n^3= (1+2+3+...+n)^2 \forall n \ge 1 [;1^3+2^3+3^3+...+n^3= (1+2+3+...+n)^2 \forall n \ge 1;]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_tPtgSu5mtAQjlEmV2RRJjN6CluQJBZZVz2G-wn_Qd3C9DBGVQyNFA5hiX16rnPTkre7CZLRTea18jCXB2ivzdIVZhzTDSgE5WHYbJOd1gXOdTH7tYzDCqubop0XbGQLOltWogni2xqJcdenSMcieF70cOnOvMCDdRluOYfGcYqD65ZPgYgx56ZK_pEIXe2x6Zg=s0-d)
(Após demonstradas essas propriedades, tentem gravá-las e refazer as demonstrações, pois são bem importantes!)
O MIM ou PIF consiste basicamente em uma maneira de provar uma propriedade
para todo
. Para isso você deve verificar
coisas:
i) (Base da Indução, passo base ou passo básico) Verificar se
é verdadeira e
ii) (Passo indutivo) Verificar que se
é valido para algum n natural,
, implica que
também é valido.
Em geral, há uma certa confusão pois pode parecer que é usar a hipótese para demonstrá-la, o que claramente não é valido, senão qualquer hipótese seria verdadeira. De forma mais didática, a demonstração pelo MIM equivale a demonstrar que, se vale para
e que se toda vez que vale para n, vale para seu SUCESSOR.
Por exemplo: imagine que eu subo uma escada, e que eu garanto que, se eu subir um degrau, então eu subirei mais um, com isso, eu subirei 2 degraus, e como eu subi 2, eu subirei 3 e assim por diante. Ao final, eu terei demonstrado que é possível subir uma escada de n degraus para todo n natural (a menos que eu fique cansado hahaha).
Vamos agora a mais alguns detalhes técnicos e exemplos.
No passo base, verificamos a validade dessa propriedade pra um valor inicial. A Hipótese de Indução (aqui no blog abreviarei para H.I.) é a propriedade aplicada a n, ou seja,
, e o passo indutivo consiste em mostrar que, se a Hipótese é Válida para um n, então ela valerá para um n+1, mas veremos como funciona na prática.
*Mostre que: ![1+2+3+4+5+...+n= \frac{(n+1).n}{2} \forall n \ge 1 [;1+2+3+4+5+...+n= \frac{(n+1).n}{2} \forall n \ge 1;]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_tzo0t8xEYLYKSGXmGDksLqxiUarqJgLDNW-avAsREFN-9V4skpbj0Ki6j658QhAsWWAfgrzCBwo9RESXiXumHOhK9a5HI-PIqAQniNUxIGIDTBuZsiwt8g3RELEA6WgIf9zGbwJg20zHP85J9PWVFwBTZAmWGlgXwlPBf2hs7Z0CAxHilZEji1gS2gkepvpQ=s0-d)
Primeiro, temos a base da indução,![n=1 [; n=1;]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_tRqPXriCMxlfw5FilrOtmYy1yyu21wD244Ndq6zxlbdcZ5r0Lradxn9_WWPbgdLotuGR-dhLHa4fKwEuWPDg=s0-d)
Logo, o passo base é verdadeiro.
Depois, supondo que
seja verdadeiro para algum n, então
, de fato,
![1+2+3+4+5+...+n+(n+1)= \underbrace{\frac{(n+1).n}{2}}_{1+2+3+4+5+...+n} + (n+1)= \frac{(n+1).n + 2(n+1)}{2} [;1+2+3+4+5+...+n+(n+1)= \underbrace{\frac{(n+1).n}{2}}_{1+2+3+4+5+...+n} + (n+1)= \frac{(n+1).n + 2(n+1)}{2};]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_slRU1_tPwD7ONvtoRskjxDlaGFw7hxp5nXtL96Fejixe8AWtlgFvcS5GWR02ZPrf-HwzwyxcVxCZBRC3NCaSVcq5Rw5VXk2bR9cQobYqoGqlVhQfUmTFtwSr8LkG1xrspFpHi2JyR-Z0fRfdJhGG3ZfKM53KALewX4nJjBsWL_gEfyINe2QjdfIWtcLogRr1llJJ9jHZAaWsI988bIUXsqv3m2f1bl1NxsALZJ80HNVryfIgWqp30GmIkJTjEBoSxba1ETb82nzoJbtTjHRKLwc1fFEVoX-XOrt2jdxM4usVc1=s0-d)
botando
em evidência,
C.Q.D.
botando
C.Q.D.
Acho que com esse exemplo ficou claro como é feita a demonstração pelo MIM. Aqui vão mais dois exemplos para ajudar.
*Mostre que: ![1^2+2^2+3^2+...+n^2= \frac{n \times(n+1) \times(2n+1)}{6} \forall n \ge 1 [;1^2+2^2+3^2+...+n^2= \frac{n \times(n+1) \times(2n+1)}{6} \forall n \ge 1;]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_sSh7Npdxl4l_Mq-W7fu-pPh09oYBccgymvXre1TWeE2IWrD9Hk8q8x8Wz4OouAmPwZYOqdtcIeInEs45e82ciNN_hMwcOqpIyqzCF1hRE267qXb6pfPa9WG2JQuh_lQZAClW9e_Sbpqw35NnrAWjf6yCqU40QJTOuSRsG_MMXaWwSWL0jcnjPezigslQcZIZx2lvLOhyKxnRjKOZ-_xZ5xLv9Ry1EdMT0d3OCCIpz9C6FkzeU=s0-d)
Inicialmente, vamos mostrar o passo básico.
Logo, o Passo básico é verdadeiro.
Nossa Hipotese de Indução é:
Vamos mostrar a veracidade do passo indutivo.
![1^2+2^2+3^2+...+n^2+(n+1)^2 = \underbrace{\frac{n \times(n+1) \times(2n+1)}{6}}_{ = 1^2+2^2+3^2+...+n^2 } + (n+1)^2 = [;1^2+2^2+3^2+...+n^2+(n+1)^2 = \underbrace{\frac{n \times(n+1) \times(2n+1)}{6}}_{ = 1^2+2^2+3^2+...+n^2 } + (n+1)^2 =;]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_sHH8aZQTpK432rYgMKKkqxuLneeyGcMGe6FC2TJs__aqnY9hfV0GP-BMYwzCcEZujeUcn0vvxg0a3PQJ5YUg4J2nQscekBBLC6QSJj7QUwyne84bfMF0kdyAQjZv9LRQMmswoQSexs0tecMlYKW7Sa6EYc7_oTkXEkxm5TRxi1rC4ftDmDNdCH6M1dka1tVT31UjBLxTe1AFiQ7YAFsyE_8L3xAykLP3Qv_W6cA3TxEcOAEWGFUM8rlFpkHsdCUKvtL6Gf_OtyiK-PXo7SxJ0A4yvpkouKFpBMTyCyUXtymTE3sHYHlnPWTvg1aErCCUXdNZfFkxvabOC9qGC8=s0-d)
Botando
em evidencia e fazendo algumas contas...
porém
, logo
![1^2+2^2+ \cdots + n^2 + (n+1)^2= [;1^2+2^2+ \cdots + n^2 + (n+1)^2=;]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_vS5k-fyAFtRVhBiH3okYi0sYFF2FwxL-xuX5-EssRmEaWU0D7tJ12wN5eWXnUGKfGB4XViLDdcbMr9Ia7PLYIS1jbt2TXBqvKUC2ke--oUQSMDUOqLXs88AJ7gM4WTOad4MVMsQl_mRHTT7KHT9Ho=s0-d)
![\frac{(n+1) \times(n+2) \times (2n+3)}{6} [;\frac{(n+1) \times(n+2) \times (2n+3)}{6};]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_uo_UME7QALY1oakjKNdlPr0qK_h8JwJYPdOqj0aZF5gx0BkVEOj_vtcwEpzRfjMr5eIWS6lwaBezxNegWWQCdi0W7ncdgdNgf_a-eJmumT4jgE5QIavnKN7CFz_Uxi5Uhfk-njomJ6zkXuTXSBv5d7shyS80QHOh58ueN3IFRf-g=s0-d)
que é exatamente nosso
C.Q.D.
C.Q.D.
Uma boa dica é escrever como deve ficar seu
para que isso indique um possivel caminho para a solução do exercicio. Tal ideia será muito util na resolução do exercício a seguir.
*Mostre que: ![1^3+2^3+3^3+...+n^3= (1+2+3+...+n)^2 \forall n \ge 1 [;1^3+2^3+3^3+...+n^3= (1+2+3+...+n)^2 \forall n \ge 1;]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_t_xYGrKoUpiGT2FA-XcYtYxRPQuSAaPBGyUSk79vnWaqkd6V0jARBpE4ndcme6HYB1WSD51g7DiOEDShqX2rSRiXuBPeSjVVG5HKVDmtnkktiMQtIfXkKZLM3WwrgvcPHLgHZ_fkAU1bVyXT-6mtfZonDLseyBO_mjtug6dZvsf_N86rnjlD8=s0-d)
Passo Base.
Passo Indutivo.
Inicialmente, para facilitar, temos que tentar entender quanto aumenta em relação a
quando passamos para
, primeiro,
escreveremos
após isso, fica facil ver que:
![[1+2+3+4+...+n+(n+1)]^2 - (1+2+3+4+...+n)^2 = [;[1+2+3+4+...+n+(n+1)]^2 - (1+2+3+4+...+n)^2 =;]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_utRUj6aYOchc-S-abDDGZqa6j48OlOgBRwlGEWDlRC1XdkMJaa2WwNtLSGEYRNLKFQpa29oqujVMOt3WSJLQQH-3AdX6AcY_HDYmLdBN0nFcvF_VLERkBuv5bKV0GWb3mgcmK4d7KEouHSMN0JhTa-RwtLtFFZUkfR-ZI=s0-d)
(é só ver que cada termo de 1 até n multiplica (n+1) 1 vez, depois (n+1) multiplica cada termo (incluindo n+1) 1 vez).
Isso é o dobro da soma dos termos de uma P.A de razão
Esse processo informalmente demonstra o teorema, porém como isso pode parecer usar a hipótese para demonstrar a hipótese, quero terminar com calma a demonstração.
Passo Indutivo (formalizado)
por Hipotese de Indução
porém como mostramos acima,
![(n+1)^3= (n+1)+2(n+1)+3(n+1)+...+n(n+1)+(n+1)+2(n+1)+3(n+1)+...+n(n+1)+(n+1)(n+1). [;(n+1)^3= (n+1)+2(n+1)+3(n+1)+...+n(n+1)+(n+1)+2(n+1)+3(n+1)+...+n(n+1)+(n+1)(n+1).;]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_uvSHDtDUKNNHFs7bRu-FpGX-DXAxt62Ab9xkSSKkQDYImHanKXi3OBOaJwHYRkHPOy9p41FwU0jOYgLd1-HNOgVS3Af9k0VFrXDPzwPI_2vjlf4ygfdudhAf2mgB6YugpCAxwhbfdn29G-OutwU8X2juee3xJXmXl19FzDjBJ7mL6AcHr26lw93LJthYISxFYkfuHiEGQEd7I2X0GXpyar5LXHHW4krc87IuKSfIgE8WxStMVJxVjWA8PF=s0-d)
Porém, como mostramos acima,
![(n+1)+2(n+1)+3(n+1)+...+n(n+1)+(n+1)+2(n+1)+3(n+1)+...+n(n+1)+(n+1)(n+1) [;(n+1)+2(n+1)+3(n+1)+...+n(n+1)+(n+1)+2(n+1)+3(n+1)+...+n(n+1)+(n+1)(n+1);]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_uO4yPVOSefkE6aafB_Mo9Fwt-cfbMswnulZhjbDnqHFh_t35gpkAiLZLzgr5N9-zBLukgW9jY4MnLdOlTKI6FUOdBFfwE8S2q0ilniz_8y50qmzmKizNunrjfRl16Bk6gAwC0jmiN-D2jyN9eE89cgxHxbHhg9B5-4iOqWMOF5Agcg_xVfqpMbpPVdJlDYolOMKzrpAXaO08mk6cg9LUyxTb28T_Q6yYE=s0-d)
é a diferença![[1+2+3+4+...+n+(n+1)]^2 - (1+2+3+4+...+n)^2 [;[1+2+3+4+...+n+(n+1)]^2 - (1+2+3+4+...+n)^2;]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_usnkfEvcgLO0lbJfSS3tQWGtTnF4Heu42-ot0Cm3PCM6bBOtjXggzj5LpheZvfkybfJrPN6y3A-x1eZbY9ppx4Q0BiWiDYg9ZeD8IitdroxWSsS7xQZLRC4Def_ZtxjDpMhjrkx286eflGK7FDxPQBGOhPkl5PNg=s0-d)
Porém, como mostramos acima,
é a diferença
logo, ![(1+2+3+4+...+n)^2 + (n+1)^3 = [1+2+3+4+...+n+(n+1)]^2 [;(1+2+3+4+...+n)^2 + (n+1)^3 = [1+2+3+4+...+n+(n+1)]^2;]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_u2_VIT4rQRsZwydQyONRwQY8bN-0TvazAImQIMyR9lMe0trqmN-OccBSsphpzscMzxApeXcfsHmY3T3WBANk_uJzKPhnbLIwClWl80JjVYYcr8EqxDm5yVEmcvRUEvIsAwoKuw4rWSR1plRPSYpcIf3cHveYBjTVotWb1qsSioUtdPkSLQ0h-wVe97=s0-d)
C.Q.D.
C.Q.D.
Antes de terminar esse post, para que não fique muito longo, pois o assunto é bem extenso, eu gostaria de mostrar um erro comum ao usar o PIF.
Por exemplo, demonstrar que a soma dos n primeiros números ímpares é ![n^2 + 1 [;n^2 + 1;]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_stPmIY31CiS0TFPLQD8zgwxACtpwgHVx6L8bZNzIsVZSm5tPBy8c4bSAy-NOZBbNHMC5MGPWc1yljO7GDF3DXvndiO22w=s0-d)
Definiremos um número ímpar como um número da forma
(note que o n-ésimo número ímpar vale
).
Nossa Hipotese de Indução é de que
![1+3+5+...+(2n-1) = n^2 + 1 [;1+3+5+...+(2n-1) = n^2 + 1;]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_sT5NCC12b9oJ9t6mLXV0BOk2noLECEvE3qClOx_Z7gAf0cI3g4ZGn2pK-k7kVJUZ4qlQ7OdbLFTDk0LRMd0dsQEoJHZJjq1DXeOLmuYSZqIRC3SYDcb2nrAJtA_18NtYk=s0-d)
então
![1+3+5+...+(2n-1)+(2n+1)= n^2 + 1 + 2n + 1 = (n+1)^2 + 1 [;1+3+5+...+(2n-1)+(2n+1)= n^2 + 1 + 2n + 1 = (n+1)^2 + 1;]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_v2_crWDk6EAb2L7DpfoLFcq_I81ttY4BHeg5KShz3Hg75kJwVkRS-R3rFvRc-fPhO0XrXyOps4pwkUDaJe5tZ4B7OmipWqhtVsBYsqbntEt4g_R1yLUtXnXkHlQb9_i6AaxnLw6yTIT4bYsaxnW4ghDP6yX6YQGukZp743ABOK3oTEKlCMn8xRhjCgaTF_4gu5eVJijg=s0-d)
então
CLARAMENTE ISSO ESTÁ ERRADO!
O erro é simples, o passo base não é valido, em geral, algumas pessoas não verificam o passo base por acharem muito trivial, mas não é e ele é tão importante quanto o passo indutivo.
O erro é simples, o passo base não é valido, em geral, algumas pessoas não verificam o passo base por acharem muito trivial, mas não é e ele é tão importante quanto o passo indutivo.
Só por curiosidade, a soma dos n primeiros números ímpares é
Até mais!
*** Lembre-se: Para melhorar a qualidade do nosso blog, avalie esse post.
*** Lembre-se: Para melhorar a qualidade do nosso blog, avalie esse post.
Boa noite! Estou pesquisando alguns posts em Teoria dos Números e percebi que em vários deles as expressões não estão aparecendo. Há um motivo? Obrigado!
ResponderExcluirOi, Diogo!
ExcluirInfelizmente, é um problema recorrente em postagens antigas.
Em breve vamos consertar tudo isso.
Abraço,
A Equipe do Blog.