Olimpíadas ⇒ (OBM) Teoria dos números Tópico resolvido
Moderador: [ Moderadores TTB ]
Mar 2017
26
13:19
(OBM) Teoria dos números
Prove que a soma [tex3]1^k+2^k+3^k+...+n^k[/tex3]
, onde n é um inteiro e k é ímpar, é divisível por [tex3]1+2+3+...+n[/tex3]
Última edição: Ittalo25 (Dom 26 Mar, 2017 13:19). Total de 1 vez.
Ninguém pode ser perfeito, mas todos podem ser melhores. [\Bob Esponja]
-
undefinied3 
- Mensagens: 1483
- Registrado em: Dom 02 Ago, 2015 13:51
- Última visita: 30-09-22
Mar 2017
26
14:40
Re: (OBM) Teoria dos números
[tex3]1+2+3+..+n=\frac{n(n+1)}{2}[/tex3]
Então precisamos provar que duas vezes a expressão é divisível por n e n+1, ou a rigor, é divisível por n/2 e n+1 (ou n e (n+1)/2)
Sendo k ímpar, temos:
[tex3]1^k+n^k=(1+n)(1^{k-1}-1^{k-2}n+...\pm n^{k-1})[/tex3]
[tex3]2^k+(n-1)^k=(1+n)(2^{k-1}-2^{k-2}(n-1)+...\pm(n-1)^{k-1})[/tex3]
E vai repetindo o processo com os opostos.
Se n for ímpar, sobra um termo médio, se não, dá pra fazer isso com todos os termos, e (n+1) poderá ser posto em evidência. Caso sobre o termo médio, note que ele é [tex3]\frac{n+1}{2}[/tex3] , e ainda podemos colocar (n+1) em evidência. A divisão por dois não causa problemas, visto que precisamos provar que duas vezes a expressão é divisível por n+1
Isso já prova a divisibilidade por (n+1).
Agora pra provar a divisibilidade por n, apliquemos módulo n na expressão:
Se o número de termos for impar, subtraimos n de todos os termos anteriores ao termo médio, inclusive, menos o primeiro. Os que estão depois mantemos inalterados
[tex3]1^k+(2-n)^k+(3-n)^k+...+(n-2)^k +(n-1)^k+n \equiv x \ (mod \ n )[/tex3]
Aplicamos a mesma fatoração com o primeiro termo e o (n-1) termo, com o segundo e o (n-2) e assim por diante. Quando atingirmos o termo médio, o processo se repete com o termo antecessor dele, ou seja, teríamos:
[tex3](\frac{n+1}{2}-n-1)^k+(\frac{n+1}{2}-n)^k=-n(...)[/tex3]
No final, sobrará o último termo que é o próprio n. Agora dá pra colocar n em evidência.
Se o número de termos for par, é agora que precisamos usar do fato que duas vezes a expressão tem que ser divisível por n, pois só a expressão sozinha não vai ser.
Utilizando da mesma estratégia de subtrair n de todos os termos antecessores ao termo médio, inclusive. Como não existe termo médio, vamos subtrair n dos "primeiro termo médio", que é o que existe quando o número de termos é par. Por exemplo:
[tex3]1^k+2^k+3^k+4^k \rightarrow (1-4)^k+(2-4)^k+3^k+4^k[/tex3]
Deixe o último termo de lado e some os opostos. Da mesma fatoração, veja que irá aparecer [tex3](x-n+n-x)(...) \equiv 0 (\ mod \ n)[/tex3] , e irá sobrar um termo sozinho, que é [tex3](\frac{n}{2}-n)^k[/tex3] . Esse termo que sobra, iremos somar com o último termo n.
[tex3](\frac{n}{2}-n)^k+n^k \equiv (\frac{n}{2})(...)[/tex3]
Como aparece essa fração, apesar dela ser divisível por n, não sabemos se o que está no parênteses é divisível por 2. Mas não tem problema porque devemos ter duas vezes a expressão divisível por n, ou a expressão divisível por n/2. Apenas exemplificando o raciocínio:
[tex3]1^k+2^k+3^k+4^k+5^k+6^k \equiv 1^k+(2-6)^k+(3-6)^k+4^k+5^k+6^k \equiv (1-6+5)(...)+(2-6+4)(...)+(3-6+6)(...) \equiv 3(...) \ (mod \ n)[/tex3]
E aí a gente vê que precisa multiplicar por 2 nesse caso.
Ficou bem confuso, mas acho que serve >.<
Então precisamos provar que duas vezes a expressão é divisível por n e n+1, ou a rigor, é divisível por n/2 e n+1 (ou n e (n+1)/2)
Sendo k ímpar, temos:
[tex3]1^k+n^k=(1+n)(1^{k-1}-1^{k-2}n+...\pm n^{k-1})[/tex3]
[tex3]2^k+(n-1)^k=(1+n)(2^{k-1}-2^{k-2}(n-1)+...\pm(n-1)^{k-1})[/tex3]
E vai repetindo o processo com os opostos.
Se n for ímpar, sobra um termo médio, se não, dá pra fazer isso com todos os termos, e (n+1) poderá ser posto em evidência. Caso sobre o termo médio, note que ele é [tex3]\frac{n+1}{2}[/tex3] , e ainda podemos colocar (n+1) em evidência. A divisão por dois não causa problemas, visto que precisamos provar que duas vezes a expressão é divisível por n+1
Isso já prova a divisibilidade por (n+1).
Agora pra provar a divisibilidade por n, apliquemos módulo n na expressão:
Se o número de termos for impar, subtraimos n de todos os termos anteriores ao termo médio, inclusive, menos o primeiro. Os que estão depois mantemos inalterados
[tex3]1^k+(2-n)^k+(3-n)^k+...+(n-2)^k +(n-1)^k+n \equiv x \ (mod \ n )[/tex3]
Aplicamos a mesma fatoração com o primeiro termo e o (n-1) termo, com o segundo e o (n-2) e assim por diante. Quando atingirmos o termo médio, o processo se repete com o termo antecessor dele, ou seja, teríamos:
[tex3](\frac{n+1}{2}-n-1)^k+(\frac{n+1}{2}-n)^k=-n(...)[/tex3]
No final, sobrará o último termo que é o próprio n. Agora dá pra colocar n em evidência.
Se o número de termos for par, é agora que precisamos usar do fato que duas vezes a expressão tem que ser divisível por n, pois só a expressão sozinha não vai ser.
Utilizando da mesma estratégia de subtrair n de todos os termos antecessores ao termo médio, inclusive. Como não existe termo médio, vamos subtrair n dos "primeiro termo médio", que é o que existe quando o número de termos é par. Por exemplo:
[tex3]1^k+2^k+3^k+4^k \rightarrow (1-4)^k+(2-4)^k+3^k+4^k[/tex3]
Deixe o último termo de lado e some os opostos. Da mesma fatoração, veja que irá aparecer [tex3](x-n+n-x)(...) \equiv 0 (\ mod \ n)[/tex3] , e irá sobrar um termo sozinho, que é [tex3](\frac{n}{2}-n)^k[/tex3] . Esse termo que sobra, iremos somar com o último termo n.
[tex3](\frac{n}{2}-n)^k+n^k \equiv (\frac{n}{2})(...)[/tex3]
Como aparece essa fração, apesar dela ser divisível por n, não sabemos se o que está no parênteses é divisível por 2. Mas não tem problema porque devemos ter duas vezes a expressão divisível por n, ou a expressão divisível por n/2. Apenas exemplificando o raciocínio:
[tex3]1^k+2^k+3^k+4^k+5^k+6^k \equiv 1^k+(2-6)^k+(3-6)^k+4^k+5^k+6^k \equiv (1-6+5)(...)+(2-6+4)(...)+(3-6+6)(...) \equiv 3(...) \ (mod \ n)[/tex3]
E aí a gente vê que precisa multiplicar por 2 nesse caso.
Ficou bem confuso, mas acho que serve >.<
Última edição: undefinied3 (Dom 26 Mar, 2017 14:40). Total de 3 vezes.
Ocupado com início do ano no ITA. Estarei fortemente inativo nesses primeiros meses do ano, então busquem outro moderador para ajudar caso possível.
-
- Tópicos Semelhantes
- Respostas
- Exibições
- Última msg
-
- 2 Respostas
- 543 Exibições
-
Última msg por Ornitologo
-
- 1 Respostas
- 189 Exibições
-
Última msg por Ittalo25
-
- 4 Respostas
- 472 Exibições
-
Última msg por Lliw
-
- 1 Respostas
- 256 Exibições
-
Última msg por FelipeMartin
