Olimpíadas ⇒ (OBM) Teoria dos números Tópico resolvido

[Ittalo25]

Prove que a soma [tex3]1^k+2^k+3^k+...+n^k[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]1+2+3+...+n[/tex3]

[undefinied3]

[tex3]1+2+3+..+n=\frac{n(n+1)}{2}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3](x-n+n-x)(...) \equiv 0 (\ mod \ n)[/tex3]

, e irá sobrar um termo sozinho, que é [tex3](\frac{n}{2}-n)^k[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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 >.<