Fórum de Matemática | DÚVIDAS? Nós respondemos!
https://forumdematematica.org/

Fundamento de Teoria da Computação - Valor inteiro de x
https://forumdematematica.org/viewtopic.php?f=70&t=7076		 Página 1 de 1
Autor:  heltongeek [ 10 Oct 2014, 22:30 ]
Título da Pergunta:  Fundamento de Teoria da Computação - Valor inteiro de x
Boa tarde pessoal! Sou novo aqui no fórum e nem sei se essa é a seção correta, pois a minha pergunta é de uma disciplina chamada Fundamentos de Teoria da Computação, mas ela é bastante relacionada à Matemática. Se estiver no local errado, favor excluirem ou alterarem a seção. Obrigado.

Estou com dificuldades neste exercício, na verdade não sei nem por onde começar. Alguém poderia dar uma luz?

Considere a expressão:
2^(2n)-1=xm

onde n e m são inteiros e n>0.

Qual o valor do inteiro x?
Autor:  Fraol [ 11 Oct 2014, 15:04 ]
Título da Pergunta:  Re: Fundamento de Teoria da Computação - Valor inteiro de x
Oi,

Creio que uma forma de resolver isso é testar alguns valores de n (0, 1, 2, 3, ... ) e verificar o padrão - que no caso é um múltiplo de 3. Para provar que vale sempre você pode usar indução.

A resposta direta seria: x = 3.
Autor:  heltongeek [ 11 Oct 2014, 15:30 ]
Título da Pergunta:  Re: Fundamento de Teoria da Computação - Valor inteiro de x
O x vale isso mesmo, 3. Porém gostaria de poder provar por indução, pois é isso que estou estudando no momento.
Autor:  Fraol [ 11 Oct 2014, 15:45 ]
Título da Pergunta:  Re: Fundamento de Teoria da Computação - Valor inteiro de x  [resolvida]
Então, vamos (tentar) provar por indução que \({2}^{2n}-{1} = {3m}\) para todo \(n \ge 0\).

O caso base é direto, quando n = 0 a expressão vale 0 e \(0 = 3 \cdot 0\)

Assumindo que a expressão vale para n qualquer, vamos provar que vale para n+1:

\({2}^{2(n+1)}-{1} = {2}^{2n +2}-{1} = {2}^{2n}\cdot 2^2 - {1} = 2^{2n}\cdot {4} - {1} = {2}^{2n}\cdot ({3+1}) - {1} = {3}\cdot2^{2n} + {2}^{2n}- {1}\)

Como a nossa hipótese é que \({2}^{2n}-{1} = {3m}\) então podemos substituir esse resulta na expressão que estamos desenvolvendo:

\({2}^{2(n+1)}-{1} = {3}\cdot2^{2n} + {3m}\), de onde sai que \({2}^{2(n+1)}-{1} = {3}\cdot p\)

Ou seja, por indução temos que \({2}^{2n}-{1} = {3m}\) para todo \(n \ge 0\).
Autor:  heltongeek [ 12 Oct 2014, 00:39 ]
Título da Pergunta:  Re: Fundamento de Teoria da Computação - Valor inteiro de x
Ok, obrigado. Acho que entendi. Obrigado :)
Página 1 de 1 Os Horários são TMG [ DST ]
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/