Maths Olympiad Prep

Library / /6 of 29

Algebra Difficulty 5.2 AIME, harder Prove it Silk Road Mathematics Competition

Find the sum
kA1k1 \sum_{k \in A} \frac{1}{k-1}
if A={mn:m,nZ,m,n2}A = \{m^n : m, n \in \mathbb{Z}, m, n \ge 2\}.

Solution

Answer: the sum is equal 11.
This can be seen as follows:
kA1k1=kA(1k111/k)=kAi11ki \sum_{k \in A} \frac{1}{k-1} = \sum_{k \in A} \left( \frac{1}{k} \cdot \frac{1}{1-1/k} \right) = \sum_{k \in A} \sum_{i \ge 1} \frac{1}{k^i}
Proposition: For xZx \in \mathbb{Z} the sets {(m,n):x=mn;m,nZ,m,n2}\{(m,n) : x = m^n; m, n \in \mathbb{Z}, m, n \ge 2\} and {(k,i):x=ki;kA,iN}\{(k,i) : x = k^i; k \in A, i \in \mathbb{N}\} have the same number of elements.
Proof of the proposition: Let x=p1a1ptatx = p_1^{a_1} \dots p_t^{a_t} be the prime factorization of xx. a=GCD(a1,,at)a = \text{GCD}(a_1, \dots, a_t), aj=abja_j = ab_j for 0jt0 \le j \le t and y=p1b1ptbty = p_1^{b_1} \dots p_t^{b_t}. Then x=mnx = m^n iff nan \mid a and m=ya/nm = y^{a/n}. So both of the sets above have τ(a)1\tau(a) - 1 elements, where τ(a)\tau(a) stands for the number of positive divisors of aa. \square

Therefore:
kAi11ki=m2n21mn=m21/m211/m=m21m(m1) \begin{aligned} \sum_{k \in A} \sum_{i \ge 1} \frac{1}{k^i} &= \sum_{m \ge 2} \sum_{n \ge 2} \frac{1}{m^n} \\ &= \sum_{m \ge 2} \frac{1/m^2}{1 - 1/m} = \sum_{m \ge 2} \frac{1}{m(m-1)} \end{aligned}
And finally,
m=2l1m(m1)=m=2l(1m11m)=11l1 for l. \sum_{m=2}^{l} \frac{1}{m(m-1)} = \sum_{m=2}^{l} \left( \frac{1}{m-1} - \frac{1}{m} \right) = 1 - \frac{1}{l} \to 1 \text{ for } l \to \infty.

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 and solution reproduced as published; topic and difficulty added by this site.