Fundamento de Teoria da Computação - Valor inteiro de x
10 Oct 2014, 22:30
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?
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?
Re: Fundamento de Teoria da Computação - Valor inteiro de x
11 Oct 2014, 15:04
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.
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.
Re: Fundamento de Teoria da Computação - Valor inteiro de x
11 Oct 2014, 15:30
O x vale isso mesmo, 3. Porém gostaria de poder provar por indução, pois é isso que estou estudando no momento.
Re: Fundamento de Teoria da Computação - Valor inteiro de x [resolvida]
11 Oct 2014, 15:45
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\).
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\).
Re: Fundamento de Teoria da Computação - Valor inteiro de x
12 Oct 2014, 00:39
Ok, obrigado. Acho que entendi. Obrigado 