Olimpíadas ⇒ (Turquia) Teoria dos Números Tópico resolvido

[theblackmamba]

Seja [tex3]k[/tex3] um número inteiro positivo . Mostre que existe uma sequência [tex3]a_0,a_1....[/tex3] de inteiros satisfazendo [tex3]a_n=\frac{a_{n-1}+n^k}{n}[/tex3] para todo [tex3]n\geq 1[/tex3], e [tex3]k-2[/tex3] é divisível por [tex3]3[/tex3].

[Auto Excluído (ID:12031)]

[tex3]a_n = \frac {b_n}{n!}[/tex3]

[tex3]\frac{b_n}{(n-1)!} = \frac{b_{n-1}}{(n-1)!} + n^k[/tex3]

[tex3]b_n - b_{n-1} = (n-1)! n^k[/tex3]

seja [tex3]b_1 = b \in \mathbb{Z} \rightarrow a_1 = b[/tex3]

[tex3]b_m =b + \sum_{n=2}^{m}(n-1)!n^k[/tex3]

então [tex3]a_m = \frac{b + \sum_{n=2}^m (n-1)!n^k}{m!}[/tex3]

só provar que esses caras são inteiros se k = 2 mod 3, acho que dá pra fazer por indução em m

[Auto Excluído (ID:12031)]

falha minha eu escrevi que [tex3]b_m =b + \sum_{n=2}^{m}(n-1)!n^k[/tex3]
na realidade [tex3]b_{m} =b + \sum_{n=1}^{m}(n-1)!n^k[/tex3]
[tex3]b=1[/tex3]

[tex3]b_m \equiv 0 \mod (m+1)![/tex3]
[tex3]1 + \sum_{n=1}^{m}(n-1)!n^{6k+2} = c*(m+1)![/tex3]
[tex3]1 + \sum_{n=1}^{m+1}(n-1)!n^{6k+2} = c*(m+1)! +m!(m+1)^{6k+2}[/tex3]
[tex3]= (m+1)!(c +\sum_{p=0}^{6k+1}C_{p}^{6k+1}(m+2)^p(-1)^{6k+1-p})[/tex3]
[tex3]= (m+1)!(c +\sum_{p=1}^{6k+1}C_{p}^{6k+1}(m+2)^p(-1)^{p}-1)[/tex3]
[tex3]c[/tex3] deve ser [tex3]1 \mod m+2[/tex3]

...

seja [tex3]b_m= p_1^{a_1}p_2^{a_2}..._{p_x}^{a_x}[/tex3]
onde [tex3]p1 < p2 <p3 <... < p_x[/tex3]
[tex3]b_m \mod p_1 \equiv 1 + \sum_{n=1}^{p_1-1}(n-1)!n^{6k+2} \equiv 0 \mod p_1[/tex3]

[Auto Excluído (ID:12031)]

ok vamos provar que [tex3]b_m[/tex3] seja da forma [tex3](m+1)!(c_m*(m+2)+1)[/tex3] para todo [tex3]m[/tex3], [tex3]c_m \in \mathbb{Z}[/tex3]

verificamos que para [tex3]m = 0[/tex3] a afirmação é verdadeira

supondo ela válida para [tex3]m[/tex3]

temos que [tex3]b_{m+1} = b_m + m!(m+1)^{6k+2}[/tex3]
[tex3]b_{m+1} = (m+1)!(c_m*(m+2)+1) + m!(m+1)^{6k+2}[/tex3]
[tex3]b_{m+1} = (m+1)!(c_m*(m+2)+1 +(m+1)^{6k+1})[/tex3]
[tex3]b_{m+1} = (m+1)!(c_m*(m+2)+1 +\sum_{i=0}^{6k+1}C_{i}^{6k+1}(m+2)^i*(-1)^{i-1})[/tex3]
[tex3]b_{m+1} = (m+1)!(c_m*(m+2) +\sum_{i=1}^{6k+1}C_{i}^{6k+1}(m+2)^i*(-1)^{i-1})[/tex3]
[tex3]b_{m+1} = (m+2)!(c_m+\sum_{i=1}^{6k+1}C_{i}^{6k+1}(m+2)^{i-1}*(-1)^{i-1})[/tex3]
[tex3]b_{m+1} = (m+2)!(c_m +\sum_{i=0}^{6k}C_{i+1}^{6k+1}(m+2)^{i}*(-1)^{i})[/tex3]
[tex3]b_{m+1} = (m+2)!(c_m +6k+1 +\sum_{i=1}^{6k}C_{i+1}^{6k+1}(m+2)^{i}*(-1)^{i})[/tex3]
[tex3]b_{m+1} = (m+2)!(c_m +6k+1 +\sum_{i=1}^{6k}C_{i+1}^{6k+1}*(-1)^{i}*\sum_{p=0}^{i}C_{p}^{i}(m+3)^{p}(-1)^{p-i})[/tex3]
[tex3]b_{m+1} = (m+2)!(c_m +6k+1 +\sum_{i=1}^{6k}C_{i+1}^{6k+1}*\sum_{p=0}^{i}C_{p}^{i}(m+3)^{p}(-1)^{p})[/tex3]
[tex3]b_{m+1} = (m+2)!(c_m +\sum_{i=0}^{6k}C_{i+1}^{6k+1} + (m+3)*c_{n+1})[/tex3]
[tex3]b_{m+1} = (m+2)!(c_m +\sum_{i=0}^{6k+1}C_{i}^{6k+1} - 1 + (m+3)*c_{n+1})[/tex3]
[tex3]b_{m+1} = (m+2)!(c_m+2^{6k+1} - 1 + (m+3)*C)[/tex3]
[tex3]c_m + 2^{6k+1} - 1 + (m+3)*C = 1 + (m+3)*c_{m+1}[/tex3]
[tex3]2^{6k+1}-2 + (m+3)*C = (m+3)*c_{m+1} - c_m[/tex3]
[tex3]c_m = \frac{d_m}{(m+2)!}[/tex3]
[tex3](m+2)!(2^{6k+1} - 2 + (m+3)*C)= d_{m+1} - d_m[/tex3]
onde [tex3]C = \sum_{i=1}^{6k}C_{i+1}^{6k+1}*\sum_{p=1}^{i}C_{p}^{i}(m+3)^{p}(-1)^{p}[/tex3]
com essa expressão da pra tirar uma fórmula para [tex3]c_m[/tex3] e assim obter uma fórmula geral para [tex3]b_m[/tex3] que dá pra usar PIF, mas vou ter que sair

[Auto Excluído (ID:12031)]

vou provar, por PIF, que [tex3]1 + \sum_{n=1}^{m}(n-1)!n^2 = (m+1)![/tex3]

para [tex3]m=1[/tex3]
[tex3]1 + 0!*1 = 1 + 1 = 2 = 2![/tex3]

se

[tex3]1 + \sum_{n=1}^{m}(n-1)!n^2= (m+1)![/tex3] então

[tex3]1 + \sum_{n=1}^{m+1}(n-1)!n^2 = (m+1)! + m!(m+1)^2 = (m+1)!(1+m+1) = (m+2)![/tex3]

a sequência: [tex3]a_m = \frac{1 + \sum_{n=1}^{m}(n-1)!n^2}{m!} = m+1[/tex3]

satisfaz a equação para [tex3]k=2[/tex3].

Para um k geral eu tentei mas não consegui mostrar.

[FelipeMartinMOD]

Vou traduzir a resposta do usuário math154 daqui

Suponha que os [tex3]a_n[/tex3] sejam todos inteiros. Deixe [tex3]S_k(n) = \sum_{i=1}^n i^k(i-1)![/tex3], então, [tex3]n!a_n - a_0 = S_k(n)[/tex3] (como foi provado acima neste tópico). Então, note que [tex3]S_1(n) \equiv S_0(n) -1 \mod (n!)[/tex3], e, para [tex3]k \ge 1[/tex3], o teorema binomial diz que:

[tex3]\sum_{j=0}^k (-1)^{k-j} {k \choose j}S_j(n) = \sum_{i=1}^n (i-1)^k(i-1)! = \\ = \sum_{i=2}^n (i-1)^{k+1}(i-2)! = \sum_{i=1}^{n-1} i^{k+1}(i-1)! \equiv
\sum_{i=1}^n i^{k+1} (i-1)! = S_{k+1}(n) \mod (n!)[/tex3]

Agora definam-se [tex3]p_0=1, q_0 = 0,p_1=1, q_1=-1[/tex3] e:

[tex3]\[p_{k+1} = \sum_{j=0}^{k} (-1)^{k-j}\binom{k}{j} p_j,\; q_{k+1} = \sum_{j=0}^{k} (-1)^{k-j}\binom{k}{j} q_j\][/tex3]

para [tex3]k \geq1[/tex3] (estas sequências são independentes de [tex3]n[/tex3]), logo, [tex3]-a_0 \equiv S_k(n) \equiv p_k S_0(n) +q_k \mod (n!)[/tex3] para todo [tex3]n \geq 1[/tex3].

Podemos provar por indução forte que [tex3]p_k[/tex3] é par se, e somente se, [tex3]k \equiv 2 \mod 3[/tex3]. De fato:

[tex3]p_{k+1} \equiv \sum_{j=0}^{k}\binom{k}{j}p_j \pmod{2}[/tex3]

Para todo [tex3]k \geq 1[/tex3], então, pela hipótese de indução:

[tex3]p_{k+1} \equiv 2^k - \sum_{3|j-2}\binom{k}{j} \equiv \omega^{2k+1}+\omega^{k+2} \equiv 1-[3|k-1] \pmod{2}[/tex3]

pelos filtros de raíz cúbica da unidade.

Agora fixe um [tex3]k[/tex3] não congruente a [tex3]2 \mod 3[/tex3] e assuma que todos os [tex3]a_n[/tex3] sejam inteiros. Pela indução acima, temos que [tex3]p_k[/tex3] é ímpar e, portanto, não nulo,então, para [tex3]n[/tex3] suficientemente largo, [tex3]n![/tex3] divide o número:

[tex3]|p_kS_0(n) +a_0+q_k| \in (0,n!)[/tex3], o que é absurdo.

Parece que tem um post provando essa cota acima lá no fórum em inglês, se alguém quiser, depois confira