Suponha que
para
. Use a indução matemática para demonstrar que
a)
.
b)
.
a)
b)
Passo 1
O enunciado diz que temos duas sequências de inteiros
e
tais que
para todo
. Precisamos provar, por indução em
, que
a) .
b) .
Usaremos a propriedade de que equivalências modulares se preservam sob soma e produto e o princípio de indução matemática.
a)
b)
Usaremos a propriedade de que equivalências modulares se preservam sob soma e produto e o princípio de indução matemática.
Passo 2
Prova de (a), caso base
.
Para temos
e
.
Como por hipótese, segue
.
Logo a propriedade vale para .
Para
Como
Logo a propriedade vale para
Passo 3
Prova de (a), passo de indução.
Suponha que para algum já valha
Suponha que para algum
Queremos mostrar que
Observe que
onde a primeira equivalência usa a hipótese de indução e o fato de
, e sabemos que soma preserva congruência. Assim, o passo de indução está completo.
Passo 4
Prova de (b), caso base
.
Para temos
e
.
Como , segue
.
Logo a propriedade vale para .
Para
Como
Logo a propriedade vale para
Passo 5
Prova de (b), passo de indução.
Suponha que para algum já valha
Suponha que para algum
Queremos mostrar que
Temos
onde usamos a hipótese de indução e o fato de que produto preserva congruência mod
. Assim, o passo de indução está completo.
Resposta
a) Para todo
vale
.
b) Para todo vale
.
b) Para todo