O conjunto
N
=
{
1
,
2
,
3
,
.
.
.
}
{\displaystyle \mathbb {N} =\{1,2,3,...\}}
é usado para contagens. De tão natural,
N
{\displaystyle \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
N
e
Z
=
{
.
.
.
,
−
2
,
−
1
,
0
,
1
,
2
,
.
.
.
}
{\displaystyle \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
N
{\displaystyle \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)
editar
A função sucessão é dada por
S
(
n
)
=
n
+
1
;
∀
n
∈
N
{\displaystyle S(n)=n+1;\forall n\in \mathbb {N} }
(Identidade) A função de sucessão
s
:
N
↦
N
{\displaystyle s:\mathbb {N} \mapsto \mathbb {N} }
é injetiva
Prova: Dados
m
,
n
∈
N
,
s
(
m
)
=
s
(
n
)
⇒
m
+
1
=
n
+
1
⇒
m
=
n
{\displaystyle m,n\in \mathbb {N} ,s(m)=s(n)\Rightarrow m+1=n+1\Rightarrow m=n}
.
(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
⇒
t
+
1
=
1
⇒
t
=
0
∉
N
⇒
∄
m
∈
N
{\displaystyle 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
{\displaystyle s(m)=1}
.
(unicidade)
∀
n
∈
N
⇒
s
(
n
)
∈
N
{\displaystyle \forall n\in \mathbb {N} \Rightarrow s(n)\in \mathbb {N} }
Seja
m
,
n
,
p
∈
N
;
s
(
n
)
=
p
;
s
(
m
)
=
p
{\displaystyle 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.
(Princípio da Indução ) Seja
A
⊂
N
{\displaystyle A\subset \mathbb {N} }
um conjunto com as seguintes propriedades: Se
{
1
∈
A
e
n
∈
A
⇒
n
+
1
∈
A
}
{\displaystyle \{1\in A\;e\;n\in A\Rightarrow n+1\in A\}}
. Então
A
=
N
{\displaystyle 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
=
N
{\displaystyle 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.
Vamos demonstrar, por indução, a conhecida fórmula
1
+
.
.
.
+
n
=
n
⋅
(
n
+
1
)
2
{\displaystyle 1+...+n={n\cdot (n+1) \over 2}}
.
Mostraremos ser válida para n = 1 assim,
1
=
1
⋅
(
1
+
1
)
2
{\displaystyle 1={1\cdot (1+1) \over 2}}
.
Suponhamos válido para n = k, ou seja, é verdadeiro que
1
+
.
.
.
+
k
=
k
⋅
(
k
+
1
)
2
{\displaystyle 1+...+k={k\cdot (k+1) \over 2}}
.
Pela recíproca da lei do corte
1
+
.
.
.
+
k
+
k
+
1
=
k
⋅
(
k
+
1
)
2
+
k
+
1
=
k
⋅
(
k
+
1
)
2
+
2
(
k
+
1
)
2
=
(
k
+
1
)
(
k
+
2
)
2
{\displaystyle 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}}
.
Teorema:
∀
n
∈
N
,
1
+
3
+
5
+
.
.
.
+
(
2
n
−
1
)
=
n
2
{\displaystyle \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
2
n
−
1
v
a
l
e
2
⋅
1
−
1
=
2
−
1
=
1
{\displaystyle 2n-1\;vale\;2\cdot 1-1=2-1=1}
, então nossa soma é
1
=
1
=
1
2
{\displaystyle 1=1=1^{2}}
.
Para quando n = 2, temos que
2
n
−
1
v
a
l
e
2
⋅
2
−
1
=
4
−
1
=
3
{\displaystyle 2n-1\;vale\;2\cdot 2-1=4-1=3}
, então nossa soma é
1
+
3
=
4
=
2
2
{\displaystyle 1+3=4=2^{2}}
.
Suponha ser válido para quando n=k, ou seja,
2
n
−
1
v
a
l
e
2
⋅
k
−
1
{\displaystyle 2n-1\;vale\;2\cdot k-1}
, então nossa soma é
1
+
3
+
.
.
.
+
2
k
−
1
=
k
2
{\displaystyle 1+3+...+2k-1=k^{2}}
.
Vamos provar ser válido para quando n=k+1, ou seja,
2
n
−
1
v
a
l
e
2
⋅
(
k
+
1
)
−
1
{\displaystyle 2n-1\;vale\;2\cdot (k+1)-1}
, então nossa soma é
1
+
3
+
.
.
.
+
2
(
k
+
1
)
−
1
=
(
k
+
1
)
2
{\displaystyle 1+3+...+2(k+1)-1=(k+1)^{2}}
.
1
+
3
+
.
.
.
+
2
(
k
+
1
)
−
1
=
1
1
+
3
+
.
.
.
+
2
k
+
2
−
1
=
2
1
+
3
+
.
.
.
+
2
k
−
1
+
2
k
+
1
=
3
k
2
+
2
k
+
1
=
4
k
2
+
k
+
k
+
1
=
5
{\displaystyle 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
{\displaystyle =_{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.
Teorema:
∀
n
∈
N
,
1
+
2
2
+
3
2
+
.
.
.
+
n
2
=
n
(
n
+
1
)
(
2
n
+
1
)
6
{\displaystyle \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
⋅
(
1
+
1
)
⋅
(
2
⋅
1
+
1
)
6
=
1
⋅
2
⋅
3
6
{\displaystyle 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
⋅
(
2
+
1
)
⋅
(
2
⋅
2
+
1
)
6
⇒
1
+
4
=
2
⋅
3
⋅
5
6
{\displaystyle 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
)
(
2
k
+
1
)
6
{\displaystyle 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
]
6
{\displaystyle 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
)
(
2
k
+
1
)
6
+
(
k
+
1
)
2
=
3
k
(
k
+
1
)
(
2
k
+
1
)
+
6
(
k
+
1
)
2
6
=
4
{\displaystyle 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
(
2
k
+
1
)
+
6
(
k
+
1
)
]
6
=
5
(
k
+
1
)
[
2
k
2
+
k
+
6
k
+
6
)
]
6
=
6
(
k
+
1
)
(
2
k
2
+
4
k
+
3
k
+
6
)
6
=
7
{\displaystyle =_{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
)
[
2
k
(
k
+
2
)
+
3
(
k
+
2
)
6
=
8
(
k
+
1
)
(
k
+
2
)
(
2
k
+
3
)
6
=
9
(
k
+
1
)
[
(
k
+
1
)
+
1
]
[
2
(
k
+
1
)
+
1
]
6
{\displaystyle =_{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.
Mostrar que, para todo
n
∈
N
,
1
3
+
2
3
+
3
3
+
.
.
.
+
n
3
=
n
2
⋅
(
n
+
1
)
2
4
{\displaystyle 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
⋅
(
1
+
1
)
2
4
⇒
1
=
4
4
{\displaystyle 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
⋅
(
k
+
1
)
2
4
{\displaystyle 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
⋅
(
k
+
2
)
2
4
{\displaystyle 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
⋅
(
k
+
1
)
2
4
+
(
k
+
1
)
3
=
2
k
2
⋅
(
k
+
1
)
2
+
4
⋅
(
k
+
1
)
⋅
(
k
+
1
)
2
4
=
3
[
k
2
+
4
(
k
+
1
)
]
(
k
+
1
)
2
4
=
4
{\displaystyle 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
+
2
k
+
2
k
+
4
)
(
k
+
1
)
2
4
=
5
[
k
(
k
+
2
)
+
2
(
k
+
2
)
]
(
k
+
1
)
2
4
=
6
(
k
+
2
)
(
k
+
2
)
(
k
+
1
)
2
4
=
7
(
k
+
1
)
2
⋅
(
k
+
2
)
2
4
{\displaystyle =_{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.
Mostre que
1
⋅
2
+
2
⋅
3
+
.
.
.
+
n
⋅
(
n
+
1
)
=
n
⋅
(
n
+
1
)
⋅
(
n
+
2
)
3
{\displaystyle 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
⋅
2
=
1
⋅
(
1
+
1
)
⋅
(
1
+
2
)
3
⇒
2
=
1
⋅
2
⋅
3
3
⇒
2
=
2
{\displaystyle 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
⋅
2
+
2
⋅
3
+
.
.
.
+
k
⋅
(
k
+
1
)
=
k
⋅
(
k
+
1
)
⋅
(
k
+
2
)
3
{\displaystyle 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
⋅
2
+
2
⋅
3
+
.
.
.
+
(
k
+
1
)
⋅
(
k
+
2
)
=
(
k
+
1
)
⋅
(
k
+
2
)
⋅
(
k
+
3
)
3
{\displaystyle 1\cdot 2+2\cdot 3+...+(k+1)\cdot (k+2)={(k+1)\cdot (k+2)\cdot (k+3) \over 3}}
.
Temos que
1
⋅
2
+
2
⋅
3
+
.
.
.
+
k
⋅
(
k
+
1
)
+
(
k
+
1
)
⋅
(
k
+
2
)
=
1
k
⋅
(
k
+
1
)
⋅
(
k
+
2
)
3
+
(
k
+
1
)
⋅
(
k
+
2
)
1
=
2
k
⋅
(
k
+
1
)
⋅
(
k
+
2
)
+
3
⋅
(
k
+
1
)
⋅
(
k
+
2
)
3
=
3
{\displaystyle 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
)
⋅
(
k
+
2
)
⋅
(
k
+
3
)
3
{\displaystyle =_{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.
Mostre que
1
1
⋅
2
+
1
2
⋅
3
+
.
.
.
+
1
n
⋅
(
n
+
1
)
=
n
n
+
1
{\displaystyle {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
1
⋅
2
=
1
1
+
1
⇒
1
2
=
1
2
{\displaystyle {1 \over 1\cdot 2}={1 \over 1+1}\Rightarrow {1 \over 2}={1 \over 2}}
.
Supor válido para n = k:
1
1
⋅
2
+
1
2
⋅
3
+
.
.
.
+
1
k
⋅
(
k
+
1
)
=
k
k
+
1
{\displaystyle {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
1
⋅
2
+
1
2
⋅
3
+
.
.
.
+
1
(
k
+
1
)
⋅
(
k
+
2
)
=
k
+
1
k
+
2
{\displaystyle {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
1
⋅
2
+
1
2
⋅
3
+
.
.
.
+
1
k
⋅
(
k
+
1
)
+
1
(
k
+
1
)
⋅
(
k
+
2
)
=
1
k
k
+
1
+
1
(
k
+
1
)
⋅
(
k
+
2
)
=
2
k
⋅
(
k
+
2
)
+
1
(
k
+
1
)
⋅
(
k
+
2
)
=
3
{\displaystyle {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
⋅
(
k
+
1
)
+
k
+
1
(
k
+
1
)
⋅
(
k
+
2
)
=
4
(
k
+
1
)
⋅
(
k
+
1
)
(
k
+
1
)
⋅
(
k
+
2
)
=
5
k
+
1
k
+
2
{\displaystyle =_{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.