Demonstrar:
d(n) <= 2 raizn

Passo 1

O enunciado nos pede para provar que o número de divisores de um inteiro positivo n, denotado por d(n), satisfaz
d(n)<= 2raizn
O conteúdo necessário é o pareamento de divisores e contagem de cardinalidade de conjuntos finitos.

Passo 2

Definimos
A = ,dinNmid dmid n e d<= raizn, B = ,dinNmid dmid n e d> raizn
Note que todo divisor din B associa-se de forma injetiva a um divisor n/din A, pois se d>raizn então n/d<raizn e (n/d)mid n. Logo
|B|<= |A|

Passo 3

Como todo elemento de A é um inteiro entre 1 e lfloorraiznrfloor, temos
|A|<= lfloorraiznrfloor <= raizn

Passo 4

O total de divisores de n é
d(n)=|A|+|B|<= |A|+|A|=2,|A|<= 2raizn

Resposta

d(n)<= 2raizn

Exercícios de Livros Relacionados