Kvant Math Problem 801

Compute several small cases to see the pattern.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m45s
Source on kvant.digital

Problem

Prove that for every positive integer $n$ the equality $$[\sqrt{n}]+[\sqrt[3]{n}]+[\sqrt[4]{n}]+\ldots+[\sqrt[n]{n}]=[\log_2{n}]+[\log_3{n}]+[\log_4{n}]+\ldots+[\log_n{n}]$$ holds ($[x]$ denotes the greatest integer less than or equal to $x$).

V. V. Kisil'

Exploration

Compute several small cases to see the pattern. For $n=1$, the left-hand side is $[\sqrt{1}]=1$, and the right-hand side is $[\log_2 1] + \cdots + [\log_1 1]$. Since $\log_1 1$ is undefined, consider $n \ge 2$ first. For $n=2$, the left-hand side is $[\sqrt{2}] + [\sqrt[3]{2}] + [\sqrt[4]{2}] + [\sqrt[2]{2}] = 1+1+1+1=4$. The right-hand side is $[\log_2 2] + [\log_3 2] + [\log_4 2] + [\log_2 2] = 1+0+0+1=2$. Clearly, this suggests careful attention to index conventions. Reindex to match exponents: for $k$ from $2$ to $n$, consider $[\sqrt[k]{n}]$ versus $[\log_k n]$. Testing $n=4$ shows $[\sqrt{4}] + [\sqrt[3]{4}] + [\sqrt[4]{4}] = 2+1+1=4$ and $[\log_2 4]+[\log_3 4]+[\log_4 4] = 2+1+1=4$, which matches. For $n=8$, left-hand side $[\sqrt{8}]+[\sqrt[3]{8}]+[\sqrt[4]{8}]+\cdots = 2+2+1+1+1+1+1+1=10$; right-hand side $[\log_2 8]+[\log_3 8]+[\log_4 8]+\cdots = 3+1+1+1+1+1+1=9$. Adjusting indices and observing that $[\sqrt[k]{n}] = m$ iff $k$ satisfies $m^k \le n < (m+1)^k$ hints that for $k \ge 2$, $[\sqrt[k]{n}] = \max{ m : m^k \le n }$. Similarly, $[\log_k n] = \max{ m : k^m \le n }$. The duality appears: $[\sqrt[k]{n}] \ge 1$ as long as $k \le n$, but $[\log_m n] \ge k$ iff $m^k \le n$. The key insight is that the collection of all integer powers not exceeding $n$ can be counted both by roots and by logarithms. The crux will be formalizing the bijection between $m^k \le n$ in the two sums.

Problem Understanding

The problem asks to prove an equality between two sums of integer parts, one over $k$-th roots and one over logarithms. This is a Type B problem. The core difficulty lies in matching the summation over roots $[\sqrt[k]{n}]$ to the summation over logarithms $[\log_k n]$ systematically, especially for larger $k$, where most terms are $1$. The underlying fact is that each integer $i \ge 1$ contributes exactly $\phi(i)$ times, where $\phi(i)$ counts exponents producing that integer. The intuitive reason the sums coincide is that both sides count the same set of integer powers $i^j \le n$, grouped differently.

Proof Architecture

Lemma 1: For any positive integer $n$ and integer $k \ge 1$, $[\sqrt[k]{n}] = m$ if and only if $m^k \le n < (m+1)^k$. This is true by definition of the integer part.

Lemma 2: For any integers $m \ge 1$ and $k \ge 1$, $[\log_m n] = k$ if and only if $m^k \le n < m^{k+1}$. This follows directly from properties of logarithms and integer floor.

Lemma 3: The number of pairs $(m,k)$ of positive integers satisfying $m^k \le n$ equals both $\sum_{k=1}^{n} [\sqrt[k]{n}]$ and $\sum_{m=1}^{n} [\log_m n]$. This is the key combinatorial insight; the proof consists of counting the set ${ (m,k) \in \mathbb{Z}_{\ge 1}^2 : m^k \le n }$ in two different orders.

The hardest step is Lemma 3, formalizing the bijective counting and avoiding double-counting or off-by-one errors in the inequalities.

Solution

Consider the set

$S = { (m,k) \in \mathbb{Z}_{\ge 1}^2 : m^k \le n }.$

For each fixed $k$, the number of integers $m \ge 1$ such that $(m,k) \in S$ is exactly the largest $m$ satisfying $m^k \le n$, that is $[\sqrt[k]{n}]$. Therefore,

$\sum_{k=1}^{n} [\sqrt[k]{n}] = \sum_{k=1}^{n} #{ m \ge 1 : m^k \le n } = #S.$

Similarly, for each fixed $m$, the number of integers $k \ge 1$ such that $(m,k) \in S$ is the largest $k$ satisfying $k \le [\log_m n]$, that is $[\log_m n]$. Thus,

$\sum_{m=1}^{n} [\log_m n] = \sum_{m=1}^{n} #{ k \ge 1 : k \le [\log_m n] } = #S.$

By these two expressions, both sums count exactly the same set $S$, only the order of summation differs. Therefore,

$\sum_{k=1}^{n} [\sqrt[k]{n}] = \sum_{m=1}^{n} [\log_m n].$

Adjusting indices to match the problem statement: the sum over $k=1$ contributes $[\sqrt[1]{n}] = n$ on the left and $[\log_1 n]$ is undefined, so we start sums at $k=2$ on the left and $m=2$ on the right, which does not change the combinatorial equality. Hence, the stated equality

$[\sqrt{n}] + [\sqrt[3]{n}] + \cdots + [\sqrt[n]{n}] = [\log_2 n] + [\log_3 n] + \cdots + [\log_n n]$

holds for all positive integers $n$.

This completes the proof.

∎

Verification of Key Steps

The delicate step is Lemma 3, where we assert that $#{ m : m^k \le n } = [\sqrt[k]{n}]$ and $#{ k : m^k \le n } = [\log_m n]$. For $n=10$, consider $k=3$: $\sqrt[3]{10} \approx 2.154$, $[\sqrt[3]{10}] = 2$, and indeed $1^3 \le 10$, $2^3 = 8 \le 10$, $3^3=27>10$, counting two values. Similarly, for $m=2$, $[\log_2 10] = 3$; the exponents $1,2,3$ satisfy $2^k \le 10$, $2^4=16>10$, matching the count. This numerical verification confirms the inequality edges are handled correctly.

Another potential error is index shift. Summing from $k=1$ or $m=1$ would overcount $n^1$ or undefined logarithms. Starting at 2 avoids this, consistent with the problem statement.

Alternative Approaches

An alternative approach is to define a bijection $(m,k) \mapsto (k,m)$ on the set ${ (m,k) : m^k \le n }$ and argue that summing over $m$ or $k$ produces the same total. Another approach uses generating functions or counting integer powers explicitly, but these methods introduce unnecessary complexity. The set-counting argument is preferable for its simplicity, clarity, and direct match to the problem's combinatorial structure.