Maths Olympiad Prep

Library / /54 of 71

Number theory Difficulty 5.4 AIME, harder Prove it United States

Problem:

F(x)=n=1105md(n)nx F(x) = \sum_{n=1}^{105^{m}} \frac{d(n)}{n^{x}}
Define the numbers a(n)a(n) to be the positive integers for which
F(x)2=n=11052ma(n)nx F(x)^{2} = \sum_{n=1}^{105^{2m}} \frac{a(n)}{n^{x}}
for all real xx. Express a(105m)a\left(105^{m}\right) in terms of mm.

Solution

Solution:

The denominator of a term in the expansion of F(x)2F(x)^{2} is equal to nxn^{x} if and only if it is a product of two terms of FF of the form d(n/k)(n/k)x\frac{d(n / k)}{(n / k)^{x}} and d(k)kx\frac{d(k)}{k^{x}} for some divisor kk of nn. Thus a(105m)=k105md(k)d(105mk)a\left(105^{m}\right) = \sum_{k \mid 105^{m}} d(k) d\left(\frac{105^{m}}{k}\right). We can write k=3a5b7ck = 3^{a} 5^{b} 7^{c} with a,b,cma, b, c \leq m for any divisor kk of 105m105^{m}, and in this case d(k)=(a+1)(b+1)(c+1)d(k) = (a+1)(b+1)(c+1). Thus the sum becomes
0a,b,cm(a+1)(b+1)(c+1)(ma+1)(mb+1)(mc+1) \sum_{0 \leq a, b, c \leq m} (a+1)(b+1)(c+1)(m-a+1)(m-b+1)(m-c+1)
For a fixed bb and cc, we can factor out (b+1)(c+1)(mb+1)(mc+1)(b+1)(c+1)(m-b+1)(m-c+1) from the terms having this bb and cc and find that the sum is equal to
a(105m)=0b,cm(b+1)(c+1)(mb+1)(mc+1)(a=1m+1a(ma+2))=0b,cm(b+1)(c+1)(mb+1)(mc+1)((m+2)(m+1)(m+2)2(m+1)(m+2)(2m+3)6)=0b,cm(b+1)(c+1)(mb+1)(mc+1)((3m+62m3)(m+1)(m+2)6)=0b,cm(b+1)(c+1)(mb+1)(mc+1)(m+33) \begin{aligned} a\left(105^{m}\right) & = \sum_{0 \leq b, c \leq m} (b+1)(c+1)(m-b+1)(m-c+1)\left(\sum_{a=1}^{m+1} a(m-a+2)\right) \\ & = \sum_{0 \leq b, c \leq m} (b+1)(c+1)(m-b+1)(m-c+1)\left((m+2) \frac{(m+1)(m+2)}{2} - \frac{(m+1)(m+2)(2m+3)}{6}\right) \\ & = \sum_{0 \leq b, c \leq m} (b+1)(c+1)(m-b+1)(m-c+1)\left(\frac{(3m+6-2m-3)(m+1)(m+2)}{6}\right) \\ & = \sum_{0 \leq b, c \leq m} (b+1)(c+1)(m-b+1)(m-c+1)\binom{m+3}{3} \end{aligned}
Fixing cc and factoring out terms again, we find by a similar argument that a(105m)=(m+33)3a\left(105^{m}\right) = \binom{m+3}{3}^{3}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.