Análise real/Indução

Naturais

O conjunto $\mathbb {N} =\{1,2,3,...\}$ é 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} =\{...,-2,-1,0,1,2,...\}$ (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;\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\not \in \mathbb {N} \Rightarrow \not \exists \;m\in \mathbb {N}$ tal que $s(m)=1$.
3. (unicidade) $\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 A\;e\;n\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+...+n={n\cdot (n+1) \over 2}$.

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

Exemplo1

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

Prova

• Vamos provar por indução sobre n:
  • Para quando n = 1, temos que $2n-1\;vale\;2\cdot 1-1=2-1=1$, então nossa soma é $1=1=1^{2}$.
  • Para quando n = 2, temos que $2n-1\;vale\;2\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-1\;vale\;2\cdot k-1$, então nossa soma é $1+3+...+2k-1=k^{2}$.
  • Vamos provar ser válido para quando n=k+1, ou seja, $2n-1\;vale\;2\cdot (k+1)-1$, então nossa soma é $1+3+...+2(k+1)-1=(k+1)^{2}$.
    • $1+3+...+2(k+1)-1=_{1}1+3+...+2k+2-1=_{2}1+3+...+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: $\forall \;n\in \mathbb {N} ,1+2^{2}+3^{2}+...+n^{2}={n(n+1)(2n+1) \over 6}$

Prova

• Vamos provar por indução sobre n:
  • Para quando n = 1, temos que $1^{2}={1\cdot (1+1)\cdot (2\cdot 1+1) \over 6}={1\cdot 2\cdot 3 \over 6}$ (verdade).
  • Para quando n = 2, temos que $1^{2}+2^{2}={2\cdot (2+1)\cdot (2\cdot 2+1) \over 6}\Rightarrow 1+4={2\cdot 3\cdot 5 \over 6}$ (verdade).
  • Suponha ser válido para quando n=k, ou seja, $1+2^{2}+3^{2}+...+k^{2}={k(k+1)(2k+1) \over 6}$.
  • Vamos provar ser válido para quando n=k+1, ou seja, $1+2^{2}+3^{2}+...+(k+1)^{2}={(k+1)[(k+1)+1][2(k+1)+1] \over 6}$.
    • $1+2^{2}+3^{2}+...+(k+1)^{2}=_{1}1+2^{2}+3^{2}+...+k^{2}+(k+1)^{2}=_{2}{k(k+1)(2k+1) \over 6}+(k+1)^{2}=_{3}{k(k+1)(2k+1)+6(k+1)^{2} \over 6}=_{4}$ $=_{4}{(k+1)[k(2k+1)+6(k+1)] \over 6}=_{5}{(k+1)[2k^{2}+k+6k+6)] \over 6}=_{6}{(k+1)(2k^{2}+4k+3k+6) \over 6}=_{7}$ $=_{7}{(k+1)[2k(k+2)+3(k+2) \over 6}=_{8}{(k+1)(k+2)(2k+3) \over 6}=_{9}{(k+1)[(k+1)+1][2(k+1)+1] \over 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}+...+n^{3}={n^{2}\cdot (n+1)^{2} \over 4}$ por indução sobre n.

Prova:

• Mostrar que é válido para n = 1, $1^{3}={1^{2}\cdot (1+1)^{2} \over 4}\Rightarrow 1={4 \over 4}$ (verdade).
• Supor válido para n = k, ou seja, $1^{3}+2^{3}+3^{3}+...+k^{3}={k^{2}\cdot (k+1)^{2} \over 4}$.
• Mostrar válido para n = k+1, ou seja, $1^{3}+2^{3}+3^{3}+...+(k+1)^{3}={(k+1)^{2}\cdot (k+2)^{2} \over 4}$.
  • $1^{3}+2^{3}+3^{3}+...+k^{3}+(k+1)^{3}=_{1}{k^{2}\cdot (k+1)^{2} \over 4}+(k+1)^{3}=_{2}{k^{2}\cdot (k+1)^{2}+4\cdot (k+1)\cdot (k+1)^{2} \over 4}=_{3}{[k^{2}+4(k+1)](k+1)^{2} \over 4}=_{4}$
  • $=_{4}{(k^{2}+2k+2k+4)(k+1)^{2} \over 4}=_{5}{[k(k+2)+2(k+2)](k+1)^{2} \over 4}=_{6}{(k+2)(k+2)(k+1)^{2} \over 4}=_{7}{(k+1)^{2}\cdot (k+2)^{2} \over 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+...+n\cdot (n+1)={n\cdot (n+1)\cdot (n+2) \over 3}$

• Prova por indução sobre n:
  • Mostrar que é válido para n = 1: $1\cdot 2={1\cdot (1+1)\cdot (1+2) \over 3}\Rightarrow 2={1\cdot 2\cdot 3 \over 3}\Rightarrow 2=2$.
  • Supor válido para n = k: $1\cdot 2+2\cdot 3+...+k\cdot (k+1)={k\cdot (k+1)\cdot (k+2) \over 3}$
  • Mostrar válido para n = k+1, ou seja, Mostrar que $1\cdot 2+2\cdot 3+...+(k+1)\cdot (k+2)={(k+1)\cdot (k+2)\cdot (k+3) \over 3}$.
    • Temos que $1\cdot 2+2\cdot 3+...+k\cdot (k+1)+(k+1)\cdot (k+2)=_{1}{k\cdot (k+1)\cdot (k+2) \over 3}+{(k+1)\cdot (k+2) \over 1}=_{2}{k\cdot (k+1)\cdot (k+2)+3\cdot (k+1)\cdot (k+2) \over 3}=_{3}$.
    • $=_{3}{(k+1)\cdot (k+2)\cdot (k+3) \over 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 ${1 \over 1\cdot 2}+{1 \over 2\cdot 3}+...+{1 \over n\cdot (n+1)}={n \over n+1}$

• Prova por indução sobre n:
  • Mostrar que é válido para n = 1: ${1 \over 1\cdot 2}={1 \over 1+1}\Rightarrow {1 \over 2}={1 \over 2}$.
  • Supor válido para n = k: ${1 \over 1\cdot 2}+{1 \over 2\cdot 3}+...+{1 \over k\cdot (k+1)}={k \over k+1}$
  • Mostrar válido para n = k+1, ou seja, Mostrar que ${1 \over 1\cdot 2}+{1 \over 2\cdot 3}+...+{1 \over (k+1)\cdot (k+2)}={k+1 \over k+2}$.
    • Temos que ${1 \over 1\cdot 2}+{1 \over 2\cdot 3}+...+{1 \over k\cdot (k+1)}+{1 \over (k+1)\cdot (k+2)}=_{1}{k \over k+1}+{1 \over (k+1)\cdot (k+2)}=_{2}{k\cdot (k+2)+1 \over (k+1)\cdot (k+2)}=_{3}$.
    • $=_{3}{k\cdot (k+1)+k+1 \over (k+1)\cdot (k+2)}=_{4}{(k+1)\cdot (k+1) \over (k+1)\cdot (k+2)}=_{5}{k+1 \over 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