Teorema 2 da indução: Considere um conjunto
A
⊂
N
{\displaystyle A\subset \mathbb {N} }
1
)
a
∈
A
;
2
)
n
∈
A
⇒
s
(
n
)
∈
A
{\displaystyle 1)\;a\in A;2)\;n\in A\Rightarrow s(n)\in A}
A
⊃
{
x
∈
N
;
x
=
a
∨
x
>
a
}
{\displaystyle A\supset \{x\in \mathbb {N} ;x=a\lor x>a\}}
Prova Tome p um natural maior que a, assim a < p, pelo axioma da ordem de dois naturais, existe um q natural, tal que a + q = p, onde p = q-sucessor de a.
Queremos mostrar que dado p=a+q natural, p pertence a A. Vamos fazer indução sobre q.
Devemos mostrar que é válido quando q = 1, ou seja, que
p
=
a
+
1
∈
A
{\displaystyle p=a+1\in A}
a
∈
A
⇒
a
+
1
∈
A
{\displaystyle a\in A\Rightarrow a+1\in A}
Suponha que é válido quando q=k, isto é,
p
=
a
+
k
∈
A
{\displaystyle p=a+k\in A}
Mostrar que é válido quando q=k+1, isto é,
p
=
a
+
k
+
1
∈
A
{\displaystyle p=a+k+1\in A}
a
+
k
∈
A
⇒
a
+
k
+
1
∈
A
{\displaystyle a+k\in A\Rightarrow a+k+1\in A}
Portanto,
∀
q
∈
N
,
a
+
q
∈
A
⇒
A
⊃
{
x
∈
N
;
x
=
a
∨
x
>
a
}
{\displaystyle \forall q\in \mathbb {N} ,a+q\in A\Rightarrow A\supset \{x\in \mathbb {N} ;x=a\lor x>a\}}
Prova 2 Seja
Y
=
{
x
∈
N
:
x
=
a
∨
x
=
s
(
y
)
:
y
∈
Y
}
e
X
=
{
n
∈
N
;
a
+
n
∈
Y
}
.
C
o
m
o
a
∈
Y
,
{\displaystyle Y=\{x\in \mathbb {N} :x=a\lor x=s(y):y\in Y\}\;e\;X=\{n\in \mathbb {N} ;a+n\in Y\}.Como\;a\in Y,}
a
+
1
∈
Y
,
p
o
r
t
a
n
t
o
1
∈
X
.
{\displaystyle a+1\in Y,portanto\;1\in X.}
n
∈
X
⇒
a
+
n
∈
Y
⇒
(
a
+
n
)
+
1
∈
Y
⇒
n
+
1
∈
X
.
L
o
g
o
X
∈
N
{\displaystyle n\in X\Rightarrow a+n\in Y\Rightarrow (a+n)+1\in Y\Rightarrow n+1\in X.Logo\;X\in \mathbb {N} }
Use o teorema da indução com 1 deslocado para provar que
2
n
+
1
<
2
n
,
∀
n
≥
3
{\displaystyle 2n+1<2^{n},\forall \;n\geq 3}
Prova Considere
A
=
{
n
∈
N
−
{
1
}
,
t
a
l
q
u
e
2
n
+
1
<
2
n
}
.
{\displaystyle A=\{n\in \mathbb {N} -\{1\},tal\;que\;2n+1<2^{n}\}.}
Vamos mostrar que é verdade para n = 3: assim,
2
⋅
3
+
1
<
2
3
⇒
7
≤
8
{\displaystyle 2\cdot 3+1<2^{3}\Rightarrow 7\leq 8}
Suponha verdade para
n
=
k
≥
3
:
o
u
s
e
j
a
,
2
k
+
1
<
2
k
{\displaystyle n=k\geq 3:ou\;seja,2k+1<2^{k}}
Vamos mostrar que é válido para
n
=
k
+
1
:
o
u
s
e
j
a
,
2
(
k
+
1
)
+
1
<
2
k
+
1
{\displaystyle n=k+1:ou\;seja,2(k+1)+1<2^{k+1}}
Assim,
2
(
k
+
1
)
+
1
=
1
2
k
+
2
+
1
=
2
2
k
+
1
+
2
<
3
2
k
+
2
<
4
2
k
+
2
k
=
5
2
k
⋅
2
1
=
6
2
k
+
1
{\displaystyle 2(k+1)+1=_{1}2k+2+1=_{2}2k+1+2<_{3}2^{k}+2<_{4}2^{k}+2^{k}=_{5}2^{k}\cdot 2^{1}=_{6}2^{k+1}}
As igualdades 1,5 é por distributiva, a igualdade 2 é por comutatividade, a desigualdade 3 é pela hipótese de indução, a desigualdade 4 é pela potência de 2 ter expoente maior que 2, a igualdade 6 é pela propriedade de potencia.
Portanto
{
1
}
∪
A
=
N
{\displaystyle \{1\}\cup A=\mathbb {N} }
Use o teorema da indução com 1 deslocado para provar que
n
2
<
2
n
,
∀
n
≥
5
{\displaystyle n^{2}<2^{n},\forall \;n\geq 5}
Prova: Tome
A
=
{
n
∈
N
,
t
a
l
q
u
e
n
2
<
2
n
}
.
{\displaystyle A=\{n\in \mathbb {N} ,tal\;que\;n^{2}<2^{n}\}.}
Vamos fazer por indução sobre n, que será válido para
n
≤
5
{\displaystyle n\leq 5}
Temos que mostrar que vale para quando
n
=
5
:
5
2
=
25
<
32
=
2
5
{\displaystyle n=5:5^{2}=25<32=2^{5}}
Suponha que seja válido para quando
n
=
k
:
n
2
<
2
k
{\displaystyle n=k:n^{2}<2^{k}}
Vamos mostrar que é válido para quando
n
=
k
+
1
:
(
k
+
1
)
2
<
2
k
+
1
{\displaystyle n=k+1:(k+1)^{2}<2^{k+1}}
(
k
+
1
)
2
=
1
k
2
+
2
k
+
1
<
2
2
k
+
2
k
+
1
<
3
2
k
+
2
k
=
4
2
k
⋅
2
1
=
5
2
k
+
1
{\displaystyle (k+1)^{2}=_{1}k^{2}+2k+1<_{2}2^{k}+2k+1<_{3}2^{k}+2^{k}=_{4}2^{k}\cdot 2^{1}=_{5}2^{k+1}}
a igualdade 1 é pelo quadrado da soma, a desigualdade 2 é pela hipótese de indução, a desigualdade 3 é pelo teorema anterior, a igualdade 4 é pela distributiva e a igualdade 5 é pela propriedade de potencia.
Prove que
(
n
+
1
n
)
n
<
n
,
∀
n
≥
3
e
m
o
s
t
r
e
q
u
e
{
1
,
2
,
3
3
,
4
4
,
.
.
.
}
{\displaystyle \left({\frac {n+1}{n}}\right)^{n}<n,\forall \;n\geq 3\;e\;mostre\;que\;{\bigg \{}1,{\sqrt {2}},{\sqrt[{3}]{3}},{\sqrt[{4}]{4}},...{\bigg \}}}
Vamos provar a desigualdade por indução sobre n, que é válido para
n
≥
3
{\displaystyle n\geq 3}
A
=
{
n
∈
N
,
t
a
l
q
u
e
(
n
+
1
n
)
n
<
n
}
{\displaystyle A={\bigg \{}n\in \mathbb {N} ,tal\;que\;\left({\frac {n+1}{n}}\right)^{n}<n{\bigg \}}}
vamos mostrar que é válido para
n
=
3
:
(
3
+
1
3
)
3
=
64
27
≤
?
3
⇔
64
<
81
{\displaystyle n=3:\left({3+1 \over 3}\right)^{3}={64 \over 27}\leq _{?}3\Leftrightarrow 64<81}
suponhamos que é válido para
n
=
k
:
(
k
+
1
k
)
k
<
k
⇒
(
k
+
1
k
)
k
+
1
<
k
⋅
(
k
+
1
k
)
⇒
(
k
+
1
k
)
k
+
1
<
k
+
1
{\displaystyle n=k:\left({k+1 \over k}\right)^{k}<k\Rightarrow \left({k+1 \over k}\right)^{k+1}<k\cdot \left({k+1 \over k}\right)\Rightarrow \left({k+1 \over k}\right)^{k+1}<k+1}
Observação:
0
<
1
,
k
≥
3
⇒
k
2
+
2
k
<
k
2
+
2
k
+
1
⇒
(
k
+
2
)
⋅
k
<
(
k
+
1
)
(
k
+
1
)
⇒
k
k
+
1
<
k
+
1
k
+
2
⇒
(
k
k
+
1
)
k
+
1
<
(
k
+
1
k
+
2
)
k
+
1
{\displaystyle 0<1,k\geq 3\Rightarrow k^{2}+2k<k^{2}+2k+1\Rightarrow (k+2)\cdot k<(k+1)(k+1)\Rightarrow {k \over k+1}<{k+1 \over k+2}\Rightarrow {\bigg (}{k \over k+1}{\bigg )}^{k+1}<{\bigg (}{k+1 \over k+2}{\bigg )}^{k+1}}
Vamos mostrar que é válido para
n
=
k
+
1
:
(
k
+
1
+
1
k
+
1
)
k
+
1
<
k
+
1
{\displaystyle n=k+1:\left({k+1+1 \over k+1}\right)^{k+1}<k+1}
(
k
+
2
k
+
1
)
k
+
1
=
1
(
k
+
2
k
+
1
)
k
+
1
⋅
(
k
k
+
1
)
k
+
1
⋅
(
k
+
1
k
)
k
+
1
<
2
(
k
+
2
k
+
1
)
k
+
1
⋅
(
k
+
1
k
+
2
)
k
+
1
⋅
(
k
+
1
)
=
3
k
+
1.
{\displaystyle \left({k+2 \over k+1}\right)^{k+1}=_{1}\left({k+2 \over k+1}\right)^{k+1}\cdot \left({k \over k+1}\right)^{k+1}\cdot \left({k+1 \over k}\right)^{k+1}<_{2}\left({k+2 \over k+1}\right)^{k+1}\cdot \left({k+1 \over k+2}\right)^{k+1}\cdot (k+1)=_{3}k+1.}
a igualdade 1 é pelo inverso multiplicativo, a desigualdade 2 é pela observação acima e pela hipótese de indução e a igualdade 3 é pelo inverso multiplicativo.
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}}
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}}
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}}
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}}
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. 
![{\displaystyle \left({\frac {n+1}{n}}\right)^{n}<n,\forall \;n\geq 3\;e\;mostre\;que\;{\bigg \{}1,{\sqrt {2}},{\sqrt[{3}]{3}},{\sqrt[{4}]{4}},...{\bigg \}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5e179a5362738aa2e0878e5095fefe50834844dc)
![{\displaystyle 1+2^{2}+3^{2}+...+(k+1)^{2}={(k+1)[(k+1)+1][2(k+1)+1] \over 6}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aba9a9dcdfb36054ff6ff0cb2733c4363fe49c1)
![{\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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d9a68c37614e3765eab6409e0cf705e481a059e3)
![{\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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dafd1cf3b80d82345702b23445db0600c362bc47)
^{2} \over 4}=_{4}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3fe467624d7ef5b69efa039b66d9009d6cc10dba)
^{2} \over 4}=_{6}{(k+2)(k+2)(k+1)^{2} \over 4}=_{7}{(k+1)^{2}\cdot (k+2)^{2} \over 4}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f22bac7fbe76bca47c0c9c7a3844cafa0c49f7d4)