Sol_L9D131

Prévia do material em texto

MAT 01375 – Matema´tica Discreta B 2013/1
Lista de Exerc´ıcios 9
Soluc¸o˜es de Exerc´ıcios Escolhidos
1 (d). Provaremos esse resultado pelo Princ´ıpio da Induc¸a˜o Matema´tica.
Base (n = 0): Note que 100 + 3 · 42 + 5 = 54 = 6 · 9, de forma que a afirmac¸a˜o
vale para n = 0.
Passo da Induc¸a˜o: Seja n ≥ 0 e suponha que 10n + 3 · 4n+2 + 5 e´ divis´ıvel por
9. Note que
10n+1 + 3 · 4n+3 + 5 = 10 · 10n + 4 · 3 · 4n+2 + 5
= (9 + 1) · 10n + (3 + 1) · 3 · 4n+2
= 9 · 10n + 3 · 3 · 4n+2 + (10n + 3 · 4n+2 + 5)
= 9
(
10n + 4n+2
)
+
(
10n + 3 · 4n+2 + 5) .
O primeiro termo desta u´ltima expressa˜o e´ claramente divis´ıvel por 9, enquanto
que o segundo e´ divis´ıvel por 9 pela Hipo´tese de Induc¸a˜o. Logo, a sua soma e´
divis´ıvel por 9 e o resultado segue pelo Princ´ıpio da Induc¸a˜o Matema´tica.
1 (e). Provaremos esse resultado pelo Princ´ıpio da Induc¸a˜o Matema´tica.
Base (n = 1): Nesse caso, temos
1∑
i=1
i3 = 13 = 1 = 12 =
(
1(1 + 1)
2
)2
, como de-
sejado.
Passo da Induc¸a˜o: Dado n ≥ 1, suponha que
n∑
i=1
i3 = 13 + 23 + · · ·+ n3 = n
2(n+ 1)2
4
.
Note que
n+1∑
i=1
i3 = (n+ 1)3 +
n∑
i=1
i3
= (n+ 1)3 +
n2(n+ 1)2
4
= (n+ 1)2
(
n+ 1 +
n2
4
)
=
(n+ 1)2
4
(n2 + 4n+ 4) =
(n+ 1)2(n+ 2)2
4
,
como desejado. Note o uso da Hipo´tese da Induc¸a˜o na passagem para a segunda
linha da equac¸a˜o acima.
1 (f). Provaremos esse resultado pelo Princ´ıpio da Induc¸a˜o Matema´tica. Para
tanto, utilizaremos as seguintes relac¸o˜es:
(I)
(
n+ 1
k
)
=
(
n
k
)
+
(
n
k − 1
)
para 0 ≤ k ≤ n+1 e supondo ( nn+1) = ( n−1) = 0, ∀n
(II)
n∑
j=0
(
n
j
)
= 2n.
Base (n = 0): Como
0∑
i=0
i
(
0
i
)
= 0 = 0 · 2−1, o resultado vale neste caso.
Passo da Induc¸a˜o: Dado n ≥ 0, suponha que
n∑
i=0
i
(
n
i
)
= n2n−1.
Note que, pela igualdade mencionada acima, temos
n+1∑
i=0
i
(
n+ 1
i
)
=
n+1∑
i=0
i
((
n
i
)
+
(
n
i− 1
))
=
n+1∑
i=0
i
(
n
i
)
+
n+1∑
i=0
i
(
n
i− 1
)
=
(
n∑
i=0
i
(
n
i
))
+ (n+ 1)
(
n
n+ 1
)
+
(
n+1∑
i=1
i
(
n
i− 1
))
+ 0
(
n
−1
)
=
n∑
i=0
i
(
n
i
)
+
n∑
j=0
(j + 1)
(
n
j
)
=
n∑
i=0
i
(
n
i
)
+
n∑
j=0
j
(
n
j
)
+
n∑
j=0
(
n
j
)
.
Pela hipo´tese de induc¸a˜o, as duas primeiras somas sa˜o iguais a n2n−1 e, por (II),
a terceira soma resulta em 2n. Conclu´ımos que
n+1∑
i=0
i
(
n+ 1
i
)
= n2n−1 + n2n−1 + 2n = n2n + 2n = (n+ 1)2n,
como quer´ıamos demonstrar.
Outra demonstrac¸a˜o: Dado n ≥ 0, considere a func¸a˜o real f(x) = (x + 1)n, que,
pelo Teorema Binomial, pode ser escrita como
f(x) = (x+ 1)n =
n∑
i=0
(
n
i
)
xi.
A sua derivada e´ dada por f ′(x) = n(x + 1)n−1 =
∑n
i=0
(
n
i
)
ixi−1. Assim, f ′(1) =
n2n−1 =
∑n
i=0 i
(
n
i
)
, como quer´ıamos demonstrar.
3. Provaremos esse resultado pelo Princ´ıpio da Induc¸a˜o Forte (tambe´m chamado
de 2a forma do Princ´ıpio da Induc¸a˜o).
Base (n = 1): Note que 1 = 20, de forma que a afirmac¸a˜o vale para n = 1.
Passo da Induc¸a˜o: Seja n ≥ 1. Suponha que todo inteiro m tal que 1 ≤ m ≤ n
e´ soma de poteˆncias de dois distintas.
Considere o inteiro n + 1. Inicialmente, suponha que n + 1 e´ ı´mpar enta˜o
n+ 1 = n+ 20, e, pela Hipo´tese de Induc¸a˜o,
n+ 1 = 2α1 + 2α2 + 2α3 + · · ·+ 2αr + 20,
com αi 6= αj se i 6= j. Como n e´ par, αi 6= 0 para todo i ∈ {1, 2, . . . , r}, logo a
expressa˜o acima e´ a representac¸a˜o de n+ 1 soma de poteˆncias de dois distintas.
Por outro lado, se n+1 e´ par, temos que n+1 = 2m para certo inteiro positivo
m ≤ n. Pela hipo´tese de induc¸a˜o, temos
n+ 1 = 2 · (2β1 + 2β2 + 2β3 + · · ·+ 2βt) = 2β1+1 + 2β2+1 + · · · 2βt+1.
Segue que n+ 1 e´ a soma de poteˆncias de 2 distintas.
4. Provaremos que 3n > n2, para todo inteiro n ≥ 0.
Base (n ∈ {0, 1, 2}): Claramente, 30 = 1 > 0 = 02, 31 = 3 > 1 = 12 e 32 = 9 >
4 = 22.
Passo da Induc¸a˜o: Seja n ≥ 2. Suponha que 3n > n2.
Note que
3n+1 − (n+ 1)2 = 3 · 3n − (n2 + 2n+ 1) > 3n2 − (n2 + 2n+ 1) = 2(n2 − n)− 1,
onde a desigualdade segue da Hipo´tese de Induc¸a˜o. Como n ≥ 2, temos n2−n > 0
e, portanto, 2(n2 − n)− 1 > 0. Conclu´ımos que 3n+1 > (n+ 1)2, como quer´ıamos
demonstrar.
Observac¸a˜o: Note que demosntramos treˆs casos na Base da Induc¸a˜o, pois o ar-
gumento utilizado no Passo da Induc¸a˜o falha se n < 2. De fato, na˜o temos
2(n2 − n)− 1 para n ∈ {0, 1}.
5. Seja θ ∈ R. A prova sera´ por induc¸a˜o em n.
Base (n = 0): Observe que (cos θ + i sen θ)0 = 1 = cos 0 + sen 0, como desejado.
Passo da Induc¸a˜o: Seja n ≥ 0. Suponha que (cos θ + i sen θ)n = cos(nθ) +
i sen(nθ).
Temos que
(cos θ + i sen θ)n+1 = (cos θ + i sen θ)(cos θ + i sen θ)n
= (cos θ + i sen θ)(cos(nθ) + i sen(nθ))
= cos θ cos(nθ)− sen θ sen(nθ) + i (cos θ sen(nθ) + sen θ sen(nθ))
= cos (θ + nθ) + i sen (θ + nθ) = cos((n+ 1)θ) + i sen((n+ 1)θ),
como quer´ıamos demonstrar. Note o uso da Hipo´tese da Induc¸a˜o para chegar-
mos a` terceira linha da equac¸a˜o acima, e das equac¸o˜es de soma de aˆngulos para
deduzirmos a quarta linha.