Página 1 de 1
(Rufino) Função máximo inteiro
Enviado: Seg 07 Set, 2020 16:50
por Deleted User 23699
Prove que
[tex3]d(1)+d(2)+d(3)+...+d(n)=\lfloor{\frac{n}{1}}\rfloor+\lfloor{\frac{n}{2}}\rfloor+\lfloor{\frac{n}{3}}\rfloor+...+\lfloor{\frac{n}{n}}\rfloor[/tex3]
onde d(i) é o número de divisores positivos do número natural i.
Re: (Rufino) Função máximo inteiro
Enviado: Sex 20 Out, 2023 16:48
por παθμ
Note que o número [tex3]\left \lfloor \frac{n}{k} \right \rfloor[/tex3]
é a quantidade de múltiplos de [tex3]k[/tex3]
que existem no intervalo [tex3][1, \;n].[/tex3]
Imagine cada parcela da soma [tex3]\sum_{i=1}^{n}d(i)[/tex3]
como uma caixa inicialmente vazia, as quais vamos preenchendo com bolas que representam unidades. Para preenchê-las, vamos passar por cada um dos inteiros de 1 a n. Para cada [tex3]1 \leq k \leq n,[/tex3]
vemos quais são os [tex3]1 \leq i \leq n[/tex3]
que têm [tex3]k[/tex3]
como um de seus divisores, e adicionamos uma bola a cada uma dessas caixas [tex3]i.[/tex3]
Fazemos isso até passearmos por todos os [tex3]1 \leq k \leq n.[/tex3]
Para cada inteiro [tex3]k,[/tex3]
nós adicionamos então [tex3]\left \lfloor \frac{n}{k} \right \rfloor[/tex3]
bolas no total, porque essa é a quantidade de múltiplos de [tex3]k[/tex3]
no intervalo de 1 a n. Por isso, ao final, teremos adicionado [tex3]\sum_{k=1}^{n} \left \lfloor \frac{n}{k} \right \rfloor[/tex3]
bolas nas caixas, e portanto:
[tex3]\boxed{\sum_{k=1}^{n}d(k)=\sum_{k=1}^{n} \left \lfloor \frac{n}{k} \right \rfloor}[/tex3]