Análise real/Indução

Naturais

O conjunto $\mathbb{N}=\{1,2,3,\mathrm{...}\}$ é usado para contagens. De tão natural, $\mathbb{N}$ é chamado de conjunto dos números naturais, o primeiro conjunto numérico que aparece na história de qualquer civilização ou em qualquer tratado sobre os fundamentos da Matemática. Admitiremos conhecidos os conjunto $\mathbb{N}e\mathbb{Z}=\{\mathrm{...},-2,-1,0,1,2,\mathrm{...}\}$ (dos números inteiros) bem como suas propriedades algébricas de soma e multiplicação e sua relação de ordem .

No conjunto $\mathbb{N}$ valem dois princípios fundamentais: o “Princípio da Boa Ordem” e o “Princípio da Indução”. Vamos provar mais adiante que são equivalentes.

Axiomas de Peano (sucessão)

A função sucessão é dada por $S(n)=n+1;\mathrm{\forall }n\in \mathbb{N}$

1. (Identidade) A função de sucessão $s:\mathbb{N}\mapsto \mathbb{N}$ é injetiva
   • Prova: Dados $m,n\in \mathbb{N},s(m)=s(n)\Rightarrow m+1=n+1\Rightarrow m=n$.
2. (Menor Elemento) Existe um elemento que não é sucessor de nenhum outro: 1
   • Prova: Suponha ser 1 o sucessor de um número natural t, assim $s(t)=1\Rightarrow t+1=1\Rightarrow t=0\in ̸\mathbb{N}\Rightarrow \mathrm{\exists }m\in \mathbb{N}$ tal que $s(m)=1$.
3. (unicidade) $\mathrm{\forall }n\in \mathbb{N}\Rightarrow s(n)\in \mathbb{N}$
   • Seja $m,n,p\in \mathbb{N};s(n)=p;s(m)=p$, para cada equação temos que n=p e m=p; por transitividade n=m. Logo o sucessor de um número natural é único.
4. (Princípio da Indução) Seja $A\subset \mathbb{N}$ um conjunto com as seguintes propriedades: Se $\{1\in Aen\in A\Rightarrow n+1\in A\}$. Então $A=\mathbb{N}$

O Princípio da Indução (e suas variantes) é usado para demonstrar que certas propriedades são verdadeiras para todo número natural. A estratégia é a seguinte. Definimos o conjunto A constituído pelos números naturais que possuem uma certa propriedade P. A seguir, mostra-se que A satisfaz as propriedades do princípio de indução. Daí, concluímos que $A=\mathbb{N}$ e, portanto, que P é verificada por todo número natural. Este tipo de argumento é chamado de demonstração por indução. É conhecido por indução finita pois existe a indução transfinita.

Exemplo

Vamos demonstrar, por indução, a conhecida fórmula $1+\mathrm{...}+n=\frac{n\cdot (n+1)}{2}$.

• Mostraremos ser válida para n = 1 assim, $1=\frac{1\cdot (1+1)}{2}$.
• Suponhamos válido para n = k, ou seja, é verdadeiro que $1+\mathrm{...}+k=\frac{k\cdot (k+1)}{2}$.
• Pela recíproca da lei do corte $1+\mathrm{...}+k+k+1=\frac{k\cdot (k+1)}{2}+k+1=\frac{k\cdot (k+1)}{2}+\frac{2(k+1)}{2}=\frac{(k+1)(k+2)}{2}$.

Exemplo1

Teorema: $\mathrm{\forall }n\in \mathbb{N},1+3+5+\mathrm{...}+(2n-1)=n^2$

Prova

• Vamos provar por indução sobre n:
  • Para quando n = 1, temos que $2n-1vale2\cdot 1-1=2-1=1$, então nossa soma é $1=1=1^2$.
  • Para quando n = 2, temos que $2n-1vale2\cdot 2-1=4-1=3$, então nossa soma é $1+3=4=2^2$.
  • Suponha ser válido para quando n=k, ou seja, $2n-1vale2\cdot k-1$, então nossa soma é $1+3+\mathrm{...}+2k-1=k^2$.
  • Vamos provar ser válido para quando n=k+1, ou seja, $2n-1vale2\cdot (k+1)-1$, então nossa soma é $1+3+\mathrm{...}+2(k+1)-1=(k+1{)}^2$.
    • $1+3+\mathrm{...}+2(k+1)-1{=}_{1}1+3+\mathrm{...}+2k+2-1{=}_{2}1+3+\mathrm{...}+2k-1+2k+1{=}_3{k}^2+2k+1{=}_4{k}^2+k+k+1{=}_5$ ${=}_{5}k(k+1)+1(k+1){=}_6(k+1{)}^2$
    • onde as igualdades 1, 5 e 6 são pela propriedade distributiva, a propriedade 2 pela definição de termos ocultos numa soma, a igualdade 3 pela hipótese de indução e a igualdade 4 pela definição de multiplicação.
  • Portanto pelo princípio da indução é válido para todo n natural.

Exemplo2

Teorema: $\mathrm{\forall }n\in \mathbb{N},1+2^2+3^2+\mathrm{...}+n^2=\frac{n(n+1)(2n+1)}{6}$

Prova

• Vamos provar por indução sobre n:
  • Para quando n = 1, temos que $1^2=\frac{1\cdot (1+1)\cdot (2\cdot 1+1)}{6}=\frac{1\cdot 2\cdot 3}{6}$ (verdade).
  • Para quando n = 2, temos que $1^2+2^2=\frac{2\cdot (2+1)\cdot (2\cdot 2+1)}{6}\Rightarrow 1+4=\frac{2\cdot 3\cdot 5}{6}$ (verdade).
  • Suponha ser válido para quando n=k, ou seja, $1+2^2+3^2+\mathrm{...}+k^2=\frac{k(k+1)(2k+1)}{6}$.
  • Vamos provar ser válido para quando n=k+1, ou seja, $1+2^2+3^2+\mathrm{...}+(k+1{)}^2=\frac{(k+1)[(k+1)+1][2(k+1)+1]}{6}$.
    • $1+2^2+3^2+\mathrm{...}+(k+1{)}^2{=}_{1}1+2^2+3^2+\mathrm{...}+k^2+(k+1{)}^2{=}_2\frac{k(k+1)(2k+1)}{6}+(k+1{)}^2{=}_3\frac{k(k+1)(2k+1)+6(k+1{)}^2}{6}{=}_4$ ${=}_4\frac{(k+1)[k(2k+1)+6(k+1)]}{6}{=}_5\frac{(k+1)[2k^2+k+6k+6)]}{6}{=}_6\frac{(k+1)(2k^2+4k+3k+6)}{6}{=}_7$ ${=}_7\frac{(k+1)[2k(k+2)+3(k+2)}{6}{=}_8\frac{(k+1)(k+2)(2k+3)}{6}{=}_9\frac{(k+1)[(k+1)+1][2(k+1)+1]}{6}$
    • onde a igualdade 1 por definição de termo ocultos numa soma finita, a igualdade 2 é devido a hipótese de indução, a igualdade 3 por soma de frações, a igualdade 4 por evidência de um termo, as igualdades 5, 7 e 8 por distributiva, as igualdades 6 e 9 por associatividade da adição.
  • Portanto pelo princípio da indução é válido para todo n natural.

Exemplo 3

Mostrar que, para todo $n\in \mathbb{N},1^3+2^3+3^3+\mathrm{...}+n^3=\frac{n^2\cdot (n+1{)}^2}{4}$ por indução sobre n.

Prova:

• Mostrar que é válido para n = 1, $1^3=\frac{1^2\cdot (1+1{)}^2}{4}\Rightarrow 1=\frac{4}{4}$ (verdade).
• Supor válido para n = k, ou seja, $1^3+2^3+3^3+\mathrm{...}+k^3=\frac{k^2\cdot (k+1{)}^2}{4}$.
• Mostrar válido para n = k+1, ou seja, $1^3+2^3+3^3+\mathrm{...}+(k+1{)}^3=\frac{(k+1{)}^2\cdot (k+2{)}^2}{4}$.
  • $1^3+2^3+3^3+\mathrm{...}+k^3+(k+1{)}^3{=}_1\frac{k^2\cdot (k+1{)}^2}{4}+(k+1{)}^3{=}_2\frac{k^2\cdot (k+1{)}^2+4\cdot (k+1)\cdot (k+1{)}^2}{4}{=}_3\frac{[k^2+4(k+1)](k+1{)}^2}{4}{=}_4$
  • ${=}_4\frac{(k^2+2k+2k+4)(k+1{)}^2}{4}{=}_5\frac{[k(k+2)+2(k+2)](k+1{)}^2}{4}{=}_6\frac{(k+2)(k+2)(k+1{)}^2}{4}{=}_7\frac{(k+1{)}^2\cdot (k+2{)}^2}{4}$
  • onde a igualdade 1 é pela hipótese de indução, a igualdade 2 é pela propriedade de potência e soma de frações, as igualdades 3, 4, 5 e 6 são pela propriedade distributiva, a igualdade 7 é pela comutativa e potência.

Exemplo 4

Mostre que $1\cdot 2+2\cdot 3+\mathrm{...}+n\cdot (n+1)=\frac{n\cdot (n+1)\cdot (n+2)}{3}$

• Prova por indução sobre n:
  • Mostrar que é válido para n = 1: $1\cdot 2=\frac{1\cdot (1+1)\cdot (1+2)}{3}\Rightarrow 2=\frac{1\cdot 2\cdot 3}{3}\Rightarrow 2=2$.
  • Supor válido para n = k: $1\cdot 2+2\cdot 3+\mathrm{...}+k\cdot (k+1)=\frac{k\cdot (k+1)\cdot (k+2)}{3}$
  • Mostrar válido para n = k+1, ou seja, Mostrar que $1\cdot 2+2\cdot 3+\mathrm{...}+(k+1)\cdot (k+2)=\frac{(k+1)\cdot (k+2)\cdot (k+3)}{3}$.
    • Temos que $1\cdot 2+2\cdot 3+\mathrm{...}+k\cdot (k+1)+(k+1)\cdot (k+2){=}_1\frac{k\cdot (k+1)\cdot (k+2)}{3}+\frac{(k+1)\cdot (k+2)}{1}{=}_2\frac{k\cdot (k+1)\cdot (k+2)+3\cdot (k+1)\cdot (k+2)}{3}{=}_3$.
    • ${=}_3\frac{(k+1)\cdot (k+2)\cdot (k+3)}{3}$.
    • a igualdade 1 é devida à hipótese de indução, a igualdade 2 pela soma de frações e a igualdade 3 é pela propriedade distributiva.

Exemplo 5

Mostre que $\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\mathrm{...}+\frac{1}{n\cdot (n+1)}=\frac{n}{n+1}$

• Prova por indução sobre n:
  • Mostrar que é válido para n = 1: $\frac{1}{1\cdot 2}=\frac{1}{1+1}\Rightarrow \frac{1}{2}=\frac{1}{2}$.
  • Supor válido para n = k: $\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\mathrm{...}+\frac{1}{k\cdot (k+1)}=\frac{k}{k+1}$
  • Mostrar válido para n = k+1, ou seja, Mostrar que $\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\mathrm{...}+\frac{1}{(k+1)\cdot (k+2)}=\frac{k+1}{k+2}$.
    • Temos que $\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\mathrm{...}+\frac{1}{k\cdot (k+1)}+\frac{1}{(k+1)\cdot (k+2)}{=}_1\frac{k}{k+1}+\frac{1}{(k+1)\cdot (k+2)}{=}_2\frac{k\cdot (k+2)+1}{(k+1)\cdot (k+2)}{=}_3$.
    • ${=}_3\frac{k\cdot (k+1)+k+1}{(k+1)\cdot (k+2)}{=}_4\frac{(k+1)\cdot (k+1)}{(k+1)\cdot (k+2)}{=}_5\frac{k+1}{k+2}$
    • a igualdade 1 é devida à hipótese de indução, a igualdade 2 pela soma de frações, a igualdade 3 é pela propriedade redistributiva, a igualdade 4 é pela propriedade distributiva e a igualdade 5 pela lei do cancelamento.

Exemplo 6

Teorema: Torre de Hanói (Para mover n discos para outra posição são necessário no mínimo $q(d)=2^d-1$ movimentos.

Prova (por indução):

• Mostrar válido para n = 1: $q(1)=2^1-1=2-1=1$
• Supor válido para n = k: $q(k)=2^k-1$
• Mostrar válido para n = k+1 ou seja, mostrar que $q(k+1)=2^{k+1}-1$.
  • Para isso devemos ter uma equação que relaciona a quantidade de movimentos com um disco a menos:
    • Para passarmos os discos de uma haste para outra, ocorre uma sequência bem simples:
      • Se temos n discos, devemos passar n-1 discos para outro haste;
      • depois passamos o disco maior para uma terceira haste;
      • depois passamos os n-1 discos para a terceira haste.
      • Por recorrência, $q(d)=q(d-1)+1+q(d-1)\Rightarrow q(d)=2q(d-1)+1\Rightarrow q(d+1)=2q(d)+1$
  • Assim, $q(k+1){=}_{1}2q(k)+1{=}_{2}2\cdot (2^k-1)+1{=}_3{2}^{1+k}-2+1\Rightarrow q(k+1)=2^{k+1}-1$
    • onde a igualdade 1 é por recorrência, a igualdade 2 é pela hipótese de indução, a igualdade 3 é pela propriedade