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_uM0xv7O6tXMnY-0NvUp-aU-vkAX0OoJTMqsga4J8Psg-4sZc85S_fk354B9a3EJC5aCvsMSrRZ2VPXITEgnMdr9SRZ1i0RjPwlqwAAaUmUoNyPTc6FZepxPOk-yv4rIHY1ax8fQ44Uq_TuIkiLd7aCEz4ynZXWDRgn-1u3HGGNFZEe-SwsiO3aXQ=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_v1ejDdmtyue9J4f30jgnp0IONv0iAhZA_J1HJwWPC7jpWHrmfAljM8KeSbSZYifcwlbyTL7HVN1iJlZGJrpTmvbNzNdJMsGLaB1WgRmjf_peEXrcCVABLkilq7lyX8A9Q5RWK3hICYTVetHc4TNmL22vJFIYi2D2gxrJemCe36p6sepffMN8ckhPIeHitnvTrMplrzjgWWA8Za8YmNuYAT4UugxrCPImcT7_sWdCddmikT_S80EirMkwAy=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_vA5XZHEDXuHW0NT83rshM311IpUmqHYekPGd0uHy-2drnl8I5z5tA4ne3I2pqmtNBYwuUWo5U29gLOpN2OpmzCij2ZviVJffgHfFSKlosnQOyMZNqIqGZy2Dbo3qYXr7P5tqCKm-OFb7EhzYLWYKQLvSZmi1ygPeuP7Giagos15_g1Av6KA0PsO_8xJ6HKHjnB=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_ugntHVWNHARHBfMb2Oj-VTwXtyRf059RMueehtxAqHk2euz7ngXrg54urS9uYyCKHegBLCFJBfN09u6hXZ4ZY_ZYp1P5SbosE3hYWGUOU5JIxmwa1p310fbuiG8ikSJIEffMJcQMW43VPnnBjt_p5BwbZO3yIp2dGwtb0ltm-6kMbDBESXEBj8H1olH1rHDg=s0-d)
Primeiro, temos a base da indução,![n=1 [; n=1;]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_vj11djBe3Jd43R51XcqksvMwqzc394j_JPh7hmIpX1pGlnqW-miYqsSbSDeiYlPydPrKGAF606Qd0s9s_Flw=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_uiXdVOqIRmlGToMVpnppyj6hyC4SIg49R3J37J-8o4D8s8J_xQkXL6uTJaSempRpbaDhZntx4X61ppAAlfM1LKCNa1J3he4tyNJR-Q_Qs6wQDqSgIJsy18PANCksK2CESrbEzL6nRvNw1VARGFSw9QEybKkf9MN1qxXJN1v-UGqUXWb4M7LgAYqcPgpE5PXgqeXWr9i5PQqcZSPnfhYWA0rknRj0nRFM4d_84Y7mYM-bAxGu9lXl5469_puSIpOUudlC5ZPW_c1AHOq-ENtKHk9HYxtWkU_2YJ4jyxX4TSKxeQ=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_vEkk9G9JSu0u9rxYE0HfMCBAXRIi3pVavk3chnr_2V6qckGfn85qdy2NPTiUisod6_W5A_BYZOSExMLFbM4vt4rtV-SDqpOiYZuxLIPUg6PD5vOOEsDu04XnGQQlNsVO2A_TOVhk9BhtG47Z0XH6d1DcOh-PVcJ_2IjAW0k8KRiheoVA_0vbTu5XW87PPKfd1JrKFVOmvHpTOKO1Dk7rNCaQbRsBqrj25wiQxaYrpr13A33DY=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_sSRkOo_gEhnwQ59IMzSD7k7RQMxRSQxcBRKzWOoSY3E0V9_h55l7VMb_b32ddRUML9cOfd830qrNcKv2b6FbbPq4XXTViQqZQVsFQAyAm8rrgn385zUzwtwZEoWvlaJPPdhZ7Fg8XhTfDG56NNGOHZkhFrilzGPRIy6I-vRC7YqRJFWtlzt6rwpKvuD3e1slATknL_IHhsS_J5ZDsInYVbsMo_HnJFZ8HkwER9YvwhgbCLyrn4VrhCsONLSsZN2_DTAHf6tPggJRIogOsZejWpI7wLfH_L5mY1yxTNaeet7XeCch6K71JE9ta5MJDVV9YeRebnaEd4zS1tshhO=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_tksmwn7vvxvPcocXIWPogw0ZQXdEEBzJp2uK_tg_CHAao1vmWaW837zU2rRCklJaLi3NzIDzXF9EOgxUyJwtIdU3cGDABQ1dQc3wYcjLJvbftzkyX5Re7OP_TzJxipglhvKDGlg_R23-NBmcACBI0=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_tx_QZhBikh8DJ3m00TnHc6Xmykuqii4fk0Z3ikkaeoRxnABiHt7BlPfZe_ZHniU_qpj-5N_cub1UoBlh5EXzbFCyIpTmSHpxiqK5i5qvw5o2nVM4vR8MLaZxAzAowH3Se-K71RTLVWPU0zfqwR_PjcxKZGeT3cR26-SuSPVn7BTA=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_vWrrl1UM4rcErnvVh9C0ZHXaD9KntfOJSpi6UkcsQa3iQkkMN6hkM_uqZIRw2ZRh80oYyP6FBkMrfCbK3IbRypaLHgEBcush_CdbpGMMnjszsdAo8NThD8ULr7zp4kRbo7Gk8NifRfk-79LcCjR6YxXayIcqfPxKIBOT6FQVtkXdhVAdsHgmM=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_u2Ez0gUfmy5WKjIckxhZT08yP4yddCe1Tf8KSL3X9RZKCZjM7CXBjkot5dKjUGP-9y-sYbIjXW9C6LhM61ZyBO0U9xp0ZeiX3Mvrxofo37HqZHcCwtCleewJRi4pH4joMe4lhEYdTkGMG70FFBbXe3Q59ytmktWwxPQs8=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_uGQ5odHF-MA6mDCbMp1sxloH-4zlCZWeywXCjo37OPb2dBV37AcbK2o8UGUvpkUscwErq2DnPVcFCQtanIDn9jgxAMvb3iCeY-DkrKPuLyz9TfPwBIdRhUOWJDaU9Oj29I0jytfxRHp5ziiuwGOEmbJbR1JKR8P2i2KGTVFldu97UDMFTenZNBccMajJ9fGE-YhxyHTkJo2XITnA3wqIfHsuxp3oRbJf9MfCuWkKxPJj-Bl4IkaILCOrE_=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_tcnRjXT4YRaVi3_abreEcOpbqikTKXZUqDxKdVVVvr5kP-KtBEK7oBUKTf3GAoDk5Dx0XCHJae_Kjuq7VSNNsvOxJH1-9946pr-V5z-rfwbZfCoR74Df_J7IB1peDhJ72ok7z8FYcsKg2vhcteWEgHcAHsmoigQs-7RvPpXdLP_vuejgOXWQPYrqLkyL14dpUI2BpFASuR_ZBXvT8g4MW9BNd7EyhRrlk=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_sVAB7-hShjgbox_uRmHY_yyxM78WUMp39jTrp7rtxhrA7B-SyChsEITl3mjS7uSUhjs299fV34T00eXV3QwJ7xAHMjZqk1MTgO4ilKbYwqxRfoxsiVUlN1LzPUXL4TgbuevNGE5kg_BITis83c0HHmgD6z9-_BuA=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_vlcuwUQ-G-4tL4cy_OScaVu9Mogs-aITJ-GTJpe-gwEK5Od13JjsUCRn1valOFR8WoMem7q3c_6SHSK7zZgHc8ZAu1cMmAzcq_NJML8_ZgoVI6Vo9PSEJvVELyKlOYVvWJnMAvj-S0pV35mWyLa9DNGq8-LlORdsdecLGBue3QC5WkNJ3duPB9hca-=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_vYjwByIKlaxmA26cDuOzTMdcmH7oVnoXm91bym8SaopskpQh2X0Fj77cb_RTnN0E5Z8RUNklcLX2QTrstMt_muy1OqSIg=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_s9FZscNZUtGvCeI4stqDdFNJJmkRqHMFR5rKWuveSOFzb_8Js5-SDVeCctH8_JhOlGQhvqBITCN8U5pEMgu7CJL8bqF9dTqarCIaVph6re6alXIcJ0Scikq43GBVMTADY=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_uYUol3p9Ht2RYgK-qZZz36utEHAMckBAKtTYk7kcxScVGvGh4ozsKK63P8sXsLKu-_T6LLQr5OSSMSV36GU2gLtefGk8ucqS8ualBGEQbBH3ty6nF34BITjv1j1A9hJJL1YtyiVUYPxSU3FyCUf3VVCnhKInPeYfqPkuBL0PYFuJI3vrDW4FL6ezp0hIEnRHQoWRPMzg=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.