Maths Olympiad Prep

Library / Silk Road Mathematics Competition competition problems /6 of 25

Silk Road Mathematics Competition competition problems

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

Find the sum
∑k∈A1k−1 \sum_{k \in A} \frac{1}{k-1}
if A={mn:m,n∈Z,m,n≥2}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:
∑k∈A1k−1=∑k∈A(1k⋅11−1/k)=∑k∈A∑i≥11ki \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 x∈Zx \in \mathbb{Z} the sets {(m,n):x=mn;m,n∈Z,m,n≥2}\{(m,n) : x = m^n; m, n \in \mathbb{Z}, m, n \ge 2\} and {(k,i):x=ki;k∈A,i∈N}\{(k,i) : x = k^i; k \in A, i \in \mathbb{N}\} have the same number of elements.
Proof of the proposition: Let x=p1a1…ptatx = 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 0≤j≤t0 \le j \le t and y=p1b1…ptbty = p_1^{b_1} \dots p_t^{b_t}. Then x=mnx = m^n iff n∣an \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:
∑k∈A∑i≥11ki=∑m≥2∑n≥21mn=∑m≥21/m21−1/m=∑m≥21m(m−1) \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(m−1)=∑m=2l(1m−1−1m)=1−1l→1 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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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