Número de soluciones$x_1x_2\dots x_k = n, x_i, n \in \mathbb{N}$

Question

He aquí una pregunta que me han hecho:

Deje $n\in \mathbb{N}$ y deje $d_k(n)$ el número de soluciones de $$x_1\dots x_k = n, \hspace{5mm}x_i\in \mathbb{N}$$

Necesito mostrar

$$d_k(n) = \sum_{d|n}d_{k-1}(d), \hspace{5mm} k \ge 2$$ y que para cualquier $\epsilon > 0$, $d_k(n) = O(n^\epsilon)$ donde el implícita constante que sólo depende de $k$. I. e $d_k(n) \ll f(k)n^\epsilon$ para algunos la función $f$.

Tengo que admitir, me falta una idea de lo $d_k(n)$ parece. Configuración de la base de caso por un argumento inductivo no es difícil, pero estoy teniendo un tiempo difícil imaginarse cómo este ser verdadero para una arbitraria $k$ implica la declaración de $k+1$. La declaración de $\epsilon > 0$, $d_k(n) = O(n^\epsilon)$ también es muy extraño para mí, tener un CS de fondo. Puedo ver cómo la elección de $\epsilon$ es arbitrario, ya que sólo varía el implícita constante en $O(n^\epsilon$). Me parece que no puede conciliar esto en mi cabeza. Asesoramiento? Gracias por su tiempo.

Answer 1

Para la suma, tenga en cuenta que $d_k(n)$ es el número de ordenadas $k$-tuplas $(x_1,x_2, \dots, x_k)$$x_2x_2\cdots x_k=n$.

Si $d$ es cualquier divisor de $n$, considere la posibilidad de la $k$-tuplas cuyo último plazo $x_k$ es igual a $n/d$. ¿Cuántos de estos hay? El $(k-1)$-tupla $(x_1,x_2,\dots, x_{k-1})$ entonces debe tener producto $d$, y por definición no se $d_{k-1}(d)$ tales $(k-1)$-uples. Finalmente, la suma de todos los $d$ que dividen $n$.

Para la estimación, probablemente usted se espera utilizar el sólo resultó de la suma de resultados, y el uso de un límite superior en el número de divisores de a $n$ a obligado a $d_k(n)$.

Nota: Si usted está familiarizado con el término, tenga en cuenta que la relación demostró muestra que $d_k(n)$ es multiplicativo, es decir, que $d_k(ab)=d_k(a)d_k(b)$ siempre $a$ $b$ son relativamente primos.

Esto implica que se puede escribir $d_k(n)$ una vez que se conoce la estructura de la potencia principal de la factorización de $n$.