Olimpíadas ⇒ (Torneio das Cidades) Teoria dos números

[Deleted User 23699]

Para todo inteiro de (n+1) a 2n, inclusive (n natural), calculamos o maior divisor ímpar e somamos todos esses divisores. Prove que a soma obtida é n².

[leozitz]

vamos usar indução.
f(x) = maior divisor ímpar de x.

por hipótese [tex3]\sum_{k = n+1}^{2n}f(k) = n^2[/tex3]

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

[tex3]\sum_{k = n+1}^{2n}f(k) = n^2[/tex3]

e queremos descobrir [tex3]\sum_{k = n+2}^{2n+2}f(k)[/tex3]

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

[tex3]\sum_{k = n+2}^{2n+2}f(k)[/tex3]

.

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

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

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

como por definição a função f(x) ignora os fatores 2, a gente tem que [tex3]f(2a) = f(a)[/tex3]

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

[tex3]f(2a) = f(a)[/tex3]

então aquilo é igual a [tex3]2n + 1 + n^2 = (n+1)^2[/tex3]

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

[tex3]2n + 1 + n^2 = (n+1)^2[/tex3]

agora a base é tranquilo verificar(verifique! kkkkkk) fica provado por indução