Principio de indução matemática
Referência : Tavares, J., Geraldo, A., (2018) Princípio de indução matemática, Rev. Ciência Elem., V6(1):087
Autor: João Nuno Tavares e Ângela Geraldo
Editor: José Ferreira Gomes
DOI: [https://doi.org/10.24927/rce2018.087]
Índice |
Princípio de indução matemática
O Principio de indução matemática diz o seguinte - seja \(\mathcal{P}(n)\) uma proposição que depende de um inteiro natural \(n\in \mathbb{N}\). Então:
- se \(\mathcal{P}(1)\) é verdadeira, e se
- \(\forall n\in \mathbb{N}\) se \(\mathcal{P}(n)\) é verdadeira então \(\mathcal{P}(n+1)\) também o é
a proposição \(\mathcal{P}(n)\) é verdadeira \(\forall n\in \mathbb{N}\). O princípio serve pois para provar proposições do tipo \(\forall n\in \mathbb{N}, \, \mathcal{P}(n)\).
Exemplos
Exemplo 1
Podemos usar o princípio de indução matemática para mostrar que:
\[1+2+3+4+\cdots+n=\frac{n(n+1)}{2}\]
Neste caso \(\displaystyle \mathcal{P}(n)=1+2+3+\cdots+n=\frac{n(n+1)}{2}\). Portanto, \(\mathcal{P}(1)\)\(\displaystyle =1=\frac{1(1+1)}{2}\quad\) e \(\quad \mathcal{P}(n+1)\)\(\displaystyle =1+2+3+\cdots+n+(n+1)=\frac{(n+1)(n+2)}{2}\).
\(\quad\quad\)1. \(\displaystyle \mathcal{P}(1)=1=\frac{1(1+1)}{2}\) é verdadeira.
\(\quad\quad\)2. Supomos agora que \(\mathcal{P}(n)\) é verdadeira, ou seja, a hipótese de indução. Queremos mostrar que \(\mathcal{P}(n+1)\) também é verdadeira.
| \(1+2+3+\cdots+n+(n+1)\) | \(=\) | \((1+2+3+\cdots+n)+(n+1)\) |
| \(=\) | \(\displaystyle \frac{n(n+1)}{2}+(n+1)\), pela hipótese de indução | |
| \(=\) | \(\displaystyle \frac{n(n+1)+2(n+1)}{2} = \frac{(n+1)(n+2)}{2}\) \(\quad\quad \mbox{QED}\) |
Exemplo 2
Outro exemplo da aplicação do princípio de indução matemática pode ser visto na demonstração de:
\[17^n-10^n \mbox{é múltiplo de } 7, \, \forall n \in \mathbb{N}\]
\(\quad\quad\)1. \(\mathcal{P}(1)=1=17^1-10^1=7\), que é múltiplo de 7, portanto \(\mathcal{P}(1)\) é verdadeira.
\(\quad\quad\)2. Supomos agora que \(\mathcal{P}(n)\) é verdadeira, ou seja, a hipótese de indução. Queremos mostrar que \(\mathcal{P}(n+1)\) também é verdadeira.
| \(17^{n+1}-10^{n+1}\) | \(=\) | \(17^n \cdot 17-10^n \cdot 10\) |
| \(=\) | \(17^n \cdot 17 - 10^n \cdot 10 - 17^n \cdot 10 + 17^n \cdot 10\) | |
| \(=\) | \(17^n \cdot 17 - 17^n \cdot 10 + 17^n \cdot 10 - 10^n \cdot 10 \) | |
| \(=\) | \(17^n \cdot (17-10) + 10 \cdot (17^n - 10^n) \) | |
| \(=\) | \(17^n \cdot 7 + 10 \cdot (\mbox{múltiplo de 7})\), pela hipótese de indução | |
| \(=\) | \(\mbox{múltiplo de 7}\) \(\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad \mbox{QED}\) |
Exemplo 3
|
Considere \(n\) rectas no plano que estão em posição geral, isto é, - duas quaisquer intersectam-se (não há paralelas) e - não existem 3 ou mais que se intersectam num único ponto. Em quantas partes dividem o plano? Designemos por \(P(n)=\) número de partes em que as \(n\) rectas em posição geral dividem o plano. Para \(n=1\), é claro que \(P(1)=2\). Suponhamos que conhecemos \(P(n)\) e determinemos \(P(n+1)\). Consideremos pois \(n+1\) rectas em posição geral no plano. As \(n\) primeiras destas rectas dividem o plano em \(P(n)=\) partes. A última, chamemos-lhe \(\ell\), intersecta as \(n\) primeiras em \(n\) pontos distintos que dividem a recta \(\ell\) em \(n+1\) pontos distintos (veja o applet com \(n=3\) rectas, com \(P(3)=7\) partes, e \(n+1=4\) rectas e \(P(4)=11\) partes). |
Portanto, a recta \(\ell\) tem pontos comuns com \(n+1\) das partes determinadas pelas \(n\) primeiras rectas a que se vêm juntar \(n+1\) novas partes (veja o applet: às \(P(3)=7\) partes determinadas pelas \(3\) primeiras rectas, juntam-se \(4\) novas partes).
Concluindo
\(P(n+1)=P(n)+(n+1)\)
Fazendo nesta igualdade \(n\) sucessivamente igual a \(n-1,n-2,\cdots,2,1\), obtemos
\(\begin{eqnarray} P(n)&=&P(n-1)+n \\ P(n-1)&=&P(n-2)+(n-1)\\ &\vdots&\\ P(3)&=&P(2)+3\\ P(2)&=&P(1)+2 \end{eqnarray}\)
Somando estas igualdades, simplificando e atendendo a que \(P(1)=2\), obtemos
\(\begin{eqnarray} P(n)&=&P(1)+[n+(n-1)+\cdots+2]\\ &=& 1+[n+(n-1)+\cdots+1]\\ &=& 1+\displaystyle \frac{n(n+1)}{2} \\ &=& \displaystyle \frac{n^2+n+2}{2} \end{eqnarray}\)
Criada em 8 de Janeiro de 2013
Revista em 11 de Janeiro de 2013
Aceite pelo editor em 31 de Março de 2018
