TAOCP 5.2.2 Exercise 50
We need to find the asymptotic value of U_{mn} = sum_{k >= 2} C(n,k) (-1)^k / (m^{k-1} - 1) for fixed m > 1 as n -> infinity.
Section 5.2.2: Sorting by Exchanging
Exercise 50. [HM24] Find the asymptotic value of the function
$$U_{mn} = \sum_{k \ge 2} \binom{n}{k} (-1)^k \frac{1}{m^{k-1} - 1}.$$
when $m$ is any fixed number greater than 1. (When $m$ is an integer greater than 2, this quantity arises in the study of generalizations of radix exchange, as well as the trie memory search algorithms of Section 6.3.)
Verified: no
Solve time: 51m56s
We need to find the asymptotic value of U_{mn} = sum_{k >= 2} C(n,k) (-1)^k / (m^{k-1} - 1) for fixed m > 1 as n -> infinity. The sum is over k >= 2.
We can extend to k=1? For k=1: C(n,1) (-1)^1 / (m^0 - 1) = -n / 0, undefined. So k starts at 2.
We need asymptotic behavior as n -> infinity, with m fixed > 1.
We can write: U_{mn} = sum_{k=2}^n C(n,k) (-1)^k / (m^{k-1} - 1)
This is a finite sum because C(n,k)=0 for k>n.
We need to find asymptotic expansion up to O(1) or better? The problem says "asymptotic value" and difficulty HM24. In context of similar problems (like exercise 48,49), they want terms up to O(1). Probably we need to find the asymptotic expansion as n -> infinity, maybe including constant term.
We have sum_{k=2}^n C(n,k) (-1)^k f(k) where f(k) = 1/(m^{k-1}-1).
This looks like we can use Euler-Maclaurin or generating functions, or relate to integral representation.
Alternatively, we can consider the sum S = sum_{k>=2} C(n,k) (-1)^k g(k) where g(k) = 1/(m^{k-1}-1). As n -> infinity, the main contribution comes from k near something? But m > 1 fixed, so m^{k-1} grows exponentially. For small k, m^{k-1} is O(1), for large k it's huge. The sum alternates with binomial coefficients. We can use the identity: sum_{k} C(n,k) (-1)^k h(k) = (-1)^n n! [x^n] (sum_{k} h(k) x^k/k!). Or use forward differences.
Let's consider the function f(x) = 1/(m^{x-1} - 1) for real x. The sum is the nth forward difference of f at 0? Actually sum_{k=0}^n C(n,k) (-1)^k f(k) = (-1)^n Δ^n f(0). But here k starts at 2, and f(0), f(1) are problematic. f(0) = 1/(m^{-1}-1) = m/(1-m) finite. f(1) = 1/(m^0-1) = 1/0 infinite. So the sum from k=2 avoids the singularity at k=1.
We can write U_{mn} = sum_{k=0}^n C(n,k) (-1)^k f(k) - f(0) + n f(1)? But f(1) is infinite, so we can't include it. Actually f(1) is singular, so the sum from k=2 is exactly the sum over all k except k=1? But k=0 gives f(0) finite. So we could write U_{mn} = sum_{k=0}^n C(n,k) (-1)^k f(k) - f(0) + n f(1)? That doesn't make sense because f(1) is infinite. But maybe we can regularize.
Alternatively, we can use the integral representation for 1/(m^{k-1}-1). For m > 1, we have: 1/(m^{k-1} - 1) = sum_{j=1}^\infty m^{-j(k-1)}. This is valid for k >= 2 because m^{k-1} > 1. So U_{mn} = sum_{k=2}^n C(n,k) (-1)^k sum_{j=1}^\infty m^{-j(k-1)}. Interchange sums: = sum_{j=1}^\infty m^j sum_{k=2}^n C(n,k) (-1)^k m^{-jk}. = sum_{j=1}^\infty m^j [ sum_{k=0}^n C(n,k) (-1)^k (m^{-j})^k - 1 + n m^{-j} ]. Because sum_{k=0}^n = 1 - n m^{-j} + sum_{k=2}^n. So sum_{k=2}^n = (1 - m^{-j})^n - 1 + n m^{-j}. Thus U_{mn} = sum_{j=1}^\infty m^j [ (1 - m^{-j})^n - 1 + n m^{-j} ].
Now this sum converges because as j -> infinity, m^{-j} -> 0, and (1 - m^{-j})^n = 1 - n m^{-j} + O(m^{-2j}), so term is m^j * O(m^{-2j}) = O(m^{-j}) -> 0 geometrically.
Now we have U_{mn} = sum_{j=1}^\infty m^j [ (1 - m^{-j})^n - 1 + n m^{-j} ].
We can also write it as sum_{j=1}^\infty m^j [ (1 - m^{-j})^n - e^{-n m^{-j}} ] + sum_{j=1}^\infty m^j [ e^{-n m^{-j}} - 1 + n m^{-j} ].
But maybe we can analyze directly.
Let’s set x_j = n m^{-j}. Then j = log_m(n/x). The sum over j can be approximated by an integral. This is similar to the analysis of U_n in the text (Exercise 47,48,49). In fact, the text mentions U_n = sum_{k>=1} (n/2^k) e^{-n/2^k} and similar. Here we have U_{mn} = sum_{j=1}^\infty m^j [ (1 - m^{-j})^n - 1 + n m^{-j} ].
We can change index: let k = j, then term = m^k [ (1 - m^{-k})^n - 1 + n m^{-k} ].
Note that for large n, the terms are significant when m^{-k} is of order 1/n, i.e., k ~ log_m n. Let k = log_m n + t, then m^{-k} = m^{-t}/n. Then m^k = n m^t. The term becomes n m^t [ (1 - m^{-t}/n)^n - 1 + m^{-t} ].
As n -> infinity, (1 - m^{-t}/n)^n -> e^{-m^{-t}}. So the term tends to n m^t [ e^{-m^{-t}} - 1 + m^{-t} ].
But we sum over integer k. This suggests the sum grows like n times something? Let's check: sum_{j} m^j ( ... ). If the term is ~ n m^t f(t), then sum over j corresponds to sum over t = k - log_m n. The spacing in t is 1, but log_m n is not integer. So we sum over integer k, which corresponds to t = k - log_m n, ranging over values that differ by 1. As n -> infinity, log_m n mod 1 varies. The sum will be approximately n times an integral over t? But wait, the sum is over j from 1 to infinity. For large n, the main contribution comes from j near log_m n. The number of terms contributing is O(1)? Actually, the term n m^t [ e^{-m^{-t}} - 1 + m^{-t} ] decays exponentially as t -> +infinity because m^t grows and e^{-m^{-t}} - 1 + m^{-t} ~ m^{-2t}/2? Let's check: as t -> +infinity, m^{-t} -> 0, so e^{-m^{-t}} = 1 - m^{-t} + m^{-2t}/2 - ... So e^{-m^{-t}} - 1 + m^{-t} = m^{-2t}/2 - ... Then term = n m^t * m^{-2t}/2 = n m^{-t}/2 -> 0 exponentially. As t -> -infinity, m^{-t} -> infinity, e^{-m^{-t}} -> 0, so e^{-m^{-t}} - 1 + m^{-t} ~ m^{-t} - 1. Then term = n m^t (m^{-t} - 1) = n (1 - m^t) ~ n. Wait, as t -> -infinity, m^t -> 0, so term ~ n * 1? That would diverge if we sum over many t. But t is not unbounded negative; j starts at 1, so k >= 1, t = k - log_m n >= 1 - log_m n. As n -> infinity, log_m n -> infinity, so the smallest t is -infinity. So the sum over all j from 1 to infinity includes a range where t is negative large. For t negative large, m^t is small, but n m^t [ e^{-m^{-t}} - 1 + m^{-t} ] ~ n m^t (m^{-t} - 1) = n (1 - m^t) ~ n. So each such term is about n. And there are about log_m n such terms? Wait, if t is negative large, say t = -M, then k = log_m n - M. The number of integer k from 1 up to something is about log_m n. So sum over j from 1 to floor(log_m n) of terms ~ n would give n log_m n? But our original sum U_{mn} is a sum of binomial coefficients times 1/(m^{k-1}-1). For large n, the binomial sum is not obviously n log n; it might be something else. Let's check small m: m=2. Then U_{2n} = sum_{k>=2} C(n,k) (-1)^k / (2^{k-1}-1). Is this O(log n) or O(n)? Let's test small n numerically? But we can't compute now. Let's think: The sum from k=2 to n C(n,k)(-1)^k f(k). For f(k)=1/(2^{k-1}-1). This is an alternating sum of binomial coefficients. The maximum of C(n,k) is ~ 2^n/sqrt(n). The alternating sum might be much smaller due to cancellation. Indeed, sum_{k=0}^n C(n,k)(-1)^k = 0. The function f(k) varies slowly for large k? For large k, f(k) ~ 2^{-k+1}. Then sum_{k} C(n,k)(-1)^k 2^{-k} = (1 - 1/2)^n = (1/2)^n. So the tail is exponentially small. The main contribution is from small k where f(k) is O(1). For small k, C(n,k)(-1)^k ~ n^k/k! times (-1)^k. So sum_{k=2} C(n,k)(-1)^k f(k) = sum_{k=2} (n^k/k!)(-1)^k f(k) + lower order? That would be polynomial in n? But f(2)=1/(m-1), f(3)=1/(m^2-1), etc. The sum of n^k/k! would grow like e^n? But we have alternating signs, so the sum might be something else. Wait, the full sum sum_{k=0}^n C(n,k)(-1)^k f(k) for f(k) not a polynomial of degree < n will generally be of order something like the nth difference of f at 0. If f(k) grows exponentially, the nth difference might be large? But f(k) = 1/(m^{k-1}-1) decays exponentially as k -> infinity. So f(k) is not a polynomial, but it's a sum of exponentials: f(k) = sum_{j>=1} m^{-j(k-1)} = sum_{j>=1} m^j m^{-jk}. Then sum_{k} C(n,k)(-1)^k f(k) = sum_{j} m^j (1 - m^{-j})^n. That's our expression. So U_{mn} = sum_{j=1}^\infty m^j [(1 - m^{-j})^n - 1 + n m^{-j}].
Now, sum_{j} m^j (1 - m^{-j})^n is the full sum from k=0 to n? Let's check: sum_{k=0}^n C(n,k)(-1)^k f(k) = sum_{j=1}^\infty m^j (1 - m^{-j})^n. But we need to subtract k=0 and k=1 terms. For k=0: f(0) = 1/(m^{-1}-1) = m/(1-m). For k=1: f(1) is infinite, so the sum from k=0 to n is infinite? But our sum from k=2 is finite. Wait, the representation f(k) = sum_{j>=1} m^{-j(k-1)} is valid only for k>1? Actually, for k=1, m^{k-1}=1, so 1/(1-1) is infinite, and the series sum_{j>=1} m^{-j(0)} = sum_{j>=1} 1 diverges. So the series representation doesn't hold for k=1. For k=0, m^{k-1}=m^{-1}<1, so series converges? 1/(m^{-1}-1) = sum_{j>=1} m^{-j(-1)}? That would be sum m^j which diverges. So the series representation 1/(m^{k-1}-1) = sum_{j>=1} m^{-j(k-1)} is valid only when m^{k-1} > 1, i.e., k > 1. So for k>=2 it's valid. So U_{mn} = sum_{j=1}^\infty m^j sum_{k=2}^n C(n,k)(-1)^k m^{-jk} = sum_{j=1}^\infty m^j [ (1 - m^{-j})^n - 1 + n m^{-j} ]. This is correct.
Now we have U_{mn} = sum_{j=1}^\infty m^j [ (1 - m^{-j})^n - 1 + n m^{-j} ].
Let's analyze this sum as n -> infinity.
We can split the sum into two parts: j <= log_m n and j > log_m n. Or use the substitution x = m^{-j} n, or j = log_m n + t.
Let’s set j = log_m n + t, where t is real. Then m^{-j} = m^{-t}/n. m^j = n m^t.
The term becomes: n m^t [ (1 - m^{-t}/n)^n - 1 + m^{-t} ].
As n -> infinity, (1 - m^{-t}/n)^n -> e^{-m^{-t}}.
So the term asymptotically approaches n m^t [ e^{-m^{-t}} - 1 + m^{-t} ].
But note that this is for fixed t. The sum over j is a sum over integer j. Let j run from 1 to infinity. The spacing in t is 1. As n -> infinity, log_m n increases, so the sum over j covers a range of t from -infinity to +infinity (shifted). The sum over j can be approximated by an integral over t, but there is a discrete sum with a periodic function in log_m n? Actually, the function we sum is of the form n * g(t) where t = j - log_m n. So U_{mn} = n sum_{j} g(j - log_m n) where g(t) = m^t [ (1 - m^{-t}/n)^n - 1 + m^{-t} ]? But g depends on n through the (1 - m^{-t}/n)^n factor. For large n, it's approximately n sum_{j} h(j - log_m n) where h(t) = m^t [ e^{-m^{-t}} - 1 + m^{-t} ].
Now sum_{j=1}^\infty h(j - log_m n) = sum_{k=-\infty}^{\infty} h(k - {log_m n}) where {x} is fractional part? Because j - log_m n = (j - floor(log_m n)) - {log_m n}. As j runs over all integers >=1, the set of j - log_m n is all integers minus {log_m n} but with a lower bound. As n -> infinity, the lower bound goes to -infinity, so it's essentially sum_{k=-\infty}^{\infty} h(k - {log_m n}). This is a periodic function of log_m n with period 1. So U_{mn} = n * H({log_m n}) + o(n)? But wait, the original sum U_{mn} is a sum of terms that are each O(n) for large n? Let's check: For j much smaller than log_m n, t is large negative, m^t is very small. h(t) = m^t [ e^{-m^{-t}} - 1 + m^{-t} ]. For t -> -infinity, m^{-t} -> infinity, e^{-m^{-t}} -> 0, so h(t) ~ m^t [ -1 + m^{-t} ] = m^t m^{-t} - m^t = 1 - m^t ~ 1. So h(t) ~ 1 as t -> -infinity. Then sum_{j} h(j - log_m n) for j from 1 to floor(log_m n) would be sum of ~1 for each of ~ log_m n terms, giving ~ log_m n. So U_{mn} ~ n * (log_m n)? But wait, earlier we thought the sum might be O(n) or O(n log n). Let's re-evaluate.
We have U_{mn} = sum_{j=1}^\infty m^j [ (1 - m^{-j})^n - 1 + n m^{-j} ].
For j fixed and n large, m^{-j} is constant. Then (1 - m^{-j})^n -> 0 exponentially. The term m^j [ -1 + n m^{-j} ] = -m^j + n. So each fixed j contributes ~ n. But wait, there are infinitely many fixed j? No, j runs from 1 to infinity. For any fixed j, as n -> infinity, the term tends to infinity like n. But the sum over all j would diverge if we just take limit termwise? But we can't interchange limit and sum because the sum over j has infinite terms. We must sum first then take limit. The sum over j converges for each n because for large j, m^{-j} is small, and (1 - m^{-j})^n ~ 1 - n m^{-j} + n(n-1)/2 m^{-2j} - ..., so the term is m^j [ O(n^2 m^{-2j}) ] = O(n^2 m^{-j}) which is summable. But as n increases, the "transition" region where m^{-j} ~ 1/n shifts to larger j. The number of j where m^{-j} is not small compared to 1/n grows like log_m n. For those j, the term is of order n? Let's check j ~ log_m n. For j = log_m n + t, m^{-j} = m^{-t}/n. The term is n m^t [ (1 - m^{-t}/n)^n - 1 + m^{-t} ]. As n->infinity, this tends to n m^t [ e^{-m^{-t}} - 1 + m^{-t} ]. For t = 0, this is n [ e^{-1} - 1 + 1 ] = n e^{-1}. For t large positive, m^t large, e^{-m^{-t}} ~ 1 - m^{-t} + m^{-2t}/2, so term ~ n m^t * m^{-2t}/2 = n m^{-t}/2 -> 0. For t large negative, m^t -> 0, m^{-t} -> infinity, e^{-m^{-t}} -> 0, term ~ n m^t (m^{-t} - 1) = n (1 - m^t) ~ n. So for t large negative, each term is ~ n. How many such terms? t negative large means j << log_m n. The number of j from 1 to something like log_m n - M is ~ log_m n. So the sum of ~ n over ~ log_m n terms gives n log n. But wait, the sum is over j, and each term is multiplied by 1 (not by something else). So the sum would be ~ n * (number of terms where term is ~ n). That suggests U_{mn} ~ n * log_m n? But is that consistent with the original binomial sum? Let's test with m=2, n large. U_{2n} = sum_{k=2}^n C(n,k)(-1)^k / (2^{k-1}-1). The maximum term in the sum is when k is small. C(n,k) ~ n^k/k!. For k=2: C(n,2)/(2-1) = n(n-1)/2 ~ n^2/2. For k=3: -C(n,3)/(4-1) = -n(n-1)(n-2)/6/3 ~ -n^3/18. The sum alternates and might be O(n^2) or O(n^3)? But the sum of the series sum_{k} C(n,k)(-1)^k f(k) for f(k)=1/(2^{k-1}-1) is not obviously polynomial. Actually, sum_{k=0}^n C(n,k)(-1)^k k^m = 0 for m < n. But here f(k) is not a polynomial. The sum is the nth difference of f at 0. If f is analytic, the nth difference is related to f^{(n)}(0) etc. But here f(k) decays exponentially, so it's not a polynomial. The sum might be exponentially small? Wait, the sum from k=0 to n C(n,k)(-1)^k a^k = (1-a)^n. Here we have f(k) = sum_{j>=1} 2^{-j(k-1)} = sum_{j>=1} 2^j 2^{-jk}. Then sum_{k=0}^n C(n,k)(-1)^k f(k) = sum_{j>=1} 2^j (1 - 2^{-j})^n. This sum converges and for large n, the terms are small except when 2^{-j} is small, i.e., j large. For j large, 2^{-j} is small, (1 - 2^{-j})^n ~ e^{-n 2^{-j}}. So the sum is sum_{j} 2^j e^{-n 2^{-j}}. This is exactly the U_n function studied in the text (Exercise 47,48,49). The text says U_n = sum_{k>=1} (n/2^k) e^{-n/2^k} (equation before 47). Wait, the text: "Find the asymptotic value of the quantity V_n defined in exercise 38" and "Extend the asymptotic formula (47) for U_n to O(n^{-1})". In the text, U_n = sum_{k>=1} (n/2^k) e^{-n/2^k}? Let's check the snippet: "Prove that sum_{j>=1} (n/2^j) e^{-n/2^j} is a bounded function of n." That's exercise 47. So U_n = sum_{j>=1} (n/2^j) e^{-n/2^j}. But our expression is sum_{j>=1} 2^j (1 - 2^{-j})^n? No, we have U_{2n} = sum_{j>=1} 2^j [ (1 - 2^{-j})^n - 1 + n 2^{-j} ]. That's different from sum (n/2^j) e^{-n/2^j}. Let's check: 2^j (1 - 2^{-j})^n is not the same as (n/2^j) e^{-n/2^j}. Actually, 2^j (1 - 2^{-j})^n ~ 2^j e^{-n 2^{-j}}. The sum over j of 2^j e^{-n 2^{-j}} is similar to sum (n/2^j) e^{-n/2^j}? Let's change variable: let x = 2^j. Then sum_j 2^j e^{-n/2^j} = sum_x x e^{-n/x} (with log spacing). The sum in exercise 47 is sum_j (n/2^j) e^{-n/2^j} = sum_x (n/x) e^{-n/x}. These are different functions. Our U_{mn} involves m^j [(1 - m^{-j})^n - 1 + n m^{-j}]. The full sum sum_{j} m^j (1 - m^{-j})^n is what? That's sum_{j} m^j e^{-n m^{-j}} (1 + O(n m^{-2j})). This sum is not bounded; as n->infinity, the dominant contribution comes from j where m^j ~ n, i.e., j ~ log_m n. Then m^j ~ n, and the summand is ~ n e^{-something}. The number of such j is O(1)? Actually, the sum sum_{j} m^j e^{-n m^{-j}} can be approximated by an integral. Let u = m^j. Then j = log_m u, dj = du/(u ln m). The sum becomes ∫ u e^{-n/u} (du/(u ln m)) = (1/ln m) ∫ e^{-n/u} du. Let v = n/u, then u = n/v, du = -n/v^2 dv. Integral = (1/ln m) ∫0^∞ e^{-v} n/v^2 dv? That diverges at v=0 (u->∞). Wait, the sum over j from 1 to infinity of m^j e^{-n m^{-j}}: for large j, m^j large, m^{-j} small, e^{-n m^{-j}} ~ 1 - n m^{-j}. Then m^j e^{-n m^{-j}} ~ m^j - n. This does not decay; it grows like m^j! That's why we need the -1 + n m^{-j} terms to cancel the divergence. Indeed, U{mn} = sum m^j [ (1 - m^{-j})^n - 1 + n m^{-j} ]. For large j, (1 - m^{-j})^n = 1 - n m^{-j} + n(n-1)/2 m^{-2j} - ... So m^j [ ... ] = m^j [ n(n-1)/2 m^{-2j} - ... ] = O(n^2 m^{-j}) which decays. So the sum converges.
Now, what is the asymptotic behavior? Let's analyze U_{mn} = sum_{j=1}^\infty m^j [ (1 - m^{-j})^n - 1 + n m^{-j} ].
We can write this as: U_{mn} = sum_{j=1}^\infty m^j [ e^{n \ln(1 - m^{-j})} - 1 + n m^{-j} ].
Let x_j = m^{-j}. Then j = -log_m x_j, m^j = 1/x_j. The sum is over x_j = m^{-j} for j=1,2,... i.e., x = 1/m, 1/m^2, ... This is a geometric progression. The sum is: U_{mn} = sum_{j=1}^\infty (1/x_j) [ (1 - x_j)^n - 1 + n x_j ]. with x_j = m^{-j}.
As n -> infinity, the terms where x_j is not small contribute. For fixed x, (1-x)^n -> 0, so term ~ (1/x)(-1 + n x) = n - 1/x. But x_j are discrete. For small x, we need expansion.
Better: Use the substitution j = floor(log_m n) + k. But perhaps we can use the Euler-Maclaurin summation formula or relate to the integral of a smooth function.
Let’s define a function F(t) = m^t [ (1 - m^{-t})^n - 1 + n m^{-t} ] for real t. Then U_{mn} = sum_{j=1}^\infty F(j). We want the asymptotic behavior of this sum as n -> infinity.
We can apply the Euler-Maclaurin formula to sum_{j=1}^\infty F(j). But F(t) depends on n. Alternatively, we can use the integral representation of the sum via the Mellin transform or Poisson summation. This is typical for sums of the form sum_j f(m^j) or sum_j m^j g(n m^{-j}).
Let’s set u = m^j. Then j = log_m u. The sum is over u = m, m^2, m^3, ... The summand is u [ (1 - 1/u)^n - 1 + n/u ].
Define G(u) = u [ (1 - 1/u)^n - 1 + n/u ] for u >= m. The sum is sum_{k=1}^\infty G(m^k).
We want sum_{k=1}^\infty G(m^k) as n -> infinity.
This is a sum over a geometric progression. The asymptotic analysis of such sums is often done using the Mellin transform or by approximating the sum by an integral plus a periodic function. The standard result for sums like sum_{k} f(n/m^k) is that they behave like (log_m n) * I + n^alpha * P(log_m n) + ... where P is a periodic function.
Let's check the behavior of G(u) as u varies. For u >> n, 1/u << 1/n, (1 - 1/u)^n ~ 1 - n/u + n(n-1)/(2u^2) - ... So G(u) = u [ n(n-1)/(2u^2) - ... ] ~ n^2/(2u). This decays as 1/u. For u << n, 1/u >> 1/n, (1 - 1/u)^n ~ e^{-n/u} (since n large, u << n implies n/u large, so e^{-n/u} is very small). Then G(u) ~ u [ 0 - 1 + n/u ] = n - u. This is ~ n. So for u from m up to about n, G(u) ~ n - u. The number of terms in the sum with u <= n is about log_m n. So the sum over these terms is sum_{k=1}^{log_m n} (n - m^k) ~ n log_m n - sum m^k ~ n log_m n - n/(m-1). So the leading asymptotic is n log_m n? But wait, for u close to n, the approximation G(u) ~ n - u breaks down because (1 - 1/u)^n is not exactly 0. There is a transition region where u ~ n. And for u > n, G(u) decays like n^2/u.
Let's do a more precise analysis.
We have U_{mn} = sum_{j=1}^\infty m^j [ (1 - m^{-j})^n - 1 + n m^{-j} ].
Let’s split the sum at j = floor(log_m n). Let J = floor(log_m n). Write: U_{mn} = sum_{j=1}^{J} m^j [ (1 - m^{-j})^n - 1 + n m^{-j} ] + sum_{j=J+1}^\infty m^j [ (1 - m^{-j})^n - 1 + n m^{-j} ].
For j <= J, m^j <= n. For large n, m^{-j} >= 1/n. The term (1 - m^{-j})^n = exp(n ln(1 - m^{-j})). For m^{-j} not too close to 1, this is small? Actually if m^{-j} is small (i.e., j large), (1 - m^{-j})^n ~ e^{-n m^{-j}}. For j <= J, m^{-j} >= 1/n, so n m^{-j} >= 1. Then e^{-n m^{-j}} <= e^{-1}. So it's not extremely small, but it's bounded away from 1. For j much smaller than J, m^{-j} is large (close to 1 if j=1? m^{-1} < 1 since m>1). For m>1, m^{-1} < 1. The maximum m^{-j} is 1/m. So n m^{-j} can be large if n is large. So (1 - m^{-j})^n is exponentially small for j << J. So for j up to J - O(1), (1 - m^{-j})^n is negligible. Then the term is approximately m^j [ -1 + n m^{-j} ] = n - m^j.
For j near J, m^j is of order n. There we need to keep the (1 - m^{-j})^n term.
For j > J, m^j > n, so m^{-j} < 1/n. Then we can expand (1 - m^{-j})^n = 1 - n m^{-j} + n(n-1)/2 m^{-2j} - ... The -1 + n m^{-j} cancels the first two terms, leaving m^j [ n(n-1)/2 m^{-2j} - ... ] = O(n^2 m^{-j}). This sum converges to something like sum_{j>J} n^2 m^{-j} * 1/2 = n^2/(2 m^J (m-1)) ~ n/(2(m-1)) (since m^J ~ n). So the tail sum is O(n).
Thus the dominant part seems to be sum_{j=1}^J (n - m^j) plus corrections. But sum_{j=1}^J (n - m^j) = J n - sum_{j=1}^J m^j = J n - m (m^J - 1)/(m-1). Since J = floor(log_m n), m^J <= n < m^{J+1}. Let n = m^{J + \delta} where \delta = {log_m n} (fractional part). Then m^J = n m^{-\delta}. J = log_m n - \delta. So: J n = n log_m n - \delta n. Sum m^j = m (m^J - 1)/(m-1) = m (n m^{-\delta} - 1)/(m-1). So sum_{j=1}^J (n - m^j) = n log_m n - \delta n - m n m^{-\delta}/(m-1) + m/(m-1). = n log_m n - n [ \delta + m^{1-\delta}/(m-1) ] + O(1).
Now we need to add the contributions from j > J and the corrections for j near J where (1 - m^{-j})^n is not negligible. These will add a term of order n? Let's see: the tail sum for j > J gave something like O(1) above J gives O(n). The transition region (j around J) will also give O(n) terms. So overall, U_{mn} = n log_m n + n * (periodic function of log_m n) + o(n)? But wait, earlier we had sum_{j=1}^J (n - m^j) = n log_m n + O(n). But is there a term of order n? Yes, -n [ \delta + m^{1-\delta}/(m-1) ] + m/(m-1). But this depends on \delta = {log_m n}. So there is a periodic function of period 1 in log_m n. And the tail and transition will contribute additional terms of order n that depend on \delta. So the asymptotic expansion will be: U_{mn} = n log_m n + n P({log_m n}) + O(1) or O(sqrt(n))? The problem asks for "asymptotic value" and the difficulty is HM24. In the text, they analyzed U_n = sum_{j>=1} (n/2^j) e^{-n/2^j} and got an expansion with a constant term and periodic functions? Actually, exercise 47 says "Prove that sum_{j>=1} (n/2^j) e^{-n/2^j} is a bounded function of n." That sum is bounded! Our sum U_{mn} has n log_m n leading term. So it's not the same as U_n in the text. But the problem says "Extend the asymptotic formula (47) for U_n to O(n^{-1})". So U_n is something else. Let's check the context: "Extend the asymptotic formula (47) for U_n to O(n^{-1})". That U_n might be sum_{j} something. But our U_{mn} is defined in exercise 50. It might be related to the "generalizations of radix exchange" and "trie memory search algorithms". The sum U_{mn} = sum_{k>=2} C(n,k) (-1)^k / (m^{k-1} - 1). This looks like the expected value of something in a trie? For radix exchange, the number of passes or something.
Let's try to find the asymptotic value of U_{mn} as n -> infinity for fixed m>1.
We have U_{mn} = sum_{j=1}^\infty m^j [ (1 - m^{-j})^n - 1 + n m^{-j} ].
We can also write it as: U_{mn} = sum_{j=1}^\infty m^j [ e^{n \ln(1 - m^{-j})} - 1 + n m^{-j} ].
Define x = m^{-j}. Then j = -ln x / ln m, m^j = 1/x. The sum over j is sum over x = m^{-1}, m^{-2}, ... U = sum_{j=1}^\infty (1/x_j) [ e^{n \ln(1 - x_j)} - 1 + n x_j ].
For large n, the main contribution comes from j where x_j is small, i.e., j large. But we saw that for small x, the term is ~ n^2 x / 2? Wait, for small x, e^{n ln(1-x)} = 1 - n x + n(n-1)/2 x^2 + O(n^3 x^3). So (1/x)[ e^{n ln(1-x)} - 1 + n x ] = (1/x)[ n(n-1)/2 x^2 + ... ] = n(n-1)/2 x + ... So it's proportional to x. The sum over x_j of x_j converges geometrically. So the sum over large j is O(n^2 x_j) summed over j>J ~ O(n^2 m^{-J}) = O(n). So the tail is O(n). The sum over j up to J (where x_j is O(1)) gave n log_m n + O(n). So the leading term is indeed n log_m n.
But wait, is there a term of order n? Let's compute more carefully.
We want to find the asymptotic expansion of U_{mn} as n -> infinity. The sum is: U_{mn} = sum_{j=1}^\infty m^j [ (1 - m^{-j})^n - 1 + n m^{-j} ].
We can also use the binomial theorem on the original definition: U_{mn} = sum_{k=2}^n \binom{n}{k} (-1)^k \frac{1}{m^{k-1} - 1}.
But the series representation seems more tractable.
Let’s apply the Euler-Maclaurin formula to the sum over j. Let f(j) = m^j [ (1 - m^{-j})^n - 1 + n m^{-j} ].
But maybe we can find an exact expression in terms of harmonic numbers or something? The sum involves (1 - m^{-j})^n. There is a known relation: sum_{j=1}^\infty m^j [ (1 - m^{-j})^n - 1 ] = - sum_{k=1}^n \binom{n}{k} (-1)^k \frac{1}{m^k - 1}? Not exactly.
Alternatively, we can use the integral representation: (1 - m^{-j})^n = \frac{1}{2\pi i} \int \frac{\Gamma(s) \Gamma(n+1)}{\Gamma(n+1+s)} m^{js} ds? Not sure.
Another approach: The sum U_{mn} looks like the expected value of the number of something in a trie. In Knuth's book, there is analysis of tries. The expected internal path length of a trie built from n random strings over an m-ary alphabet is something like sum_{k>=2} \binom{n}{k} (-1)^k \frac{1}{m^{k-1} - 1}? Or maybe the number of nodes? Let's recall: In Section 6.3, the trie search algorithm, the average number of nodes in a trie for n strings is something like sum_{k>=1} \binom{n}{k} (-1)^{k+1} \frac{m}{m-1} ...? Actually, the expected external path length or number of internal nodes often involves sums like \sum_{k=1}^n \binom{n}{k} (-1)^{k+1} \frac{1}{1 - m^{-k}} etc. The given sum U_{mn} has (-1)^k and denominator m^{k-1} - 1.
Note that 1/(m^{k-1} - 1) = m/(m^k - m). Not standard.
Let's try to compute the sum exactly for integer m? The problem says m is any fixed number greater than 1, not necessarily integer. But it mentions "When m is an integer greater than 2, this quantity arises in the study of generalizations of radix exchange, as well as the trie memory search algorithms of Section 6.3." So m is real > 1.
We can try to find the asymptotic expansion using the Mellin transform. The sum S(n) = sum_{j=1}^\infty m^j f(n m^{-j}) where f(x) = [ (1 - 1/x)^x? No, we have (1 - m^{-j})^n. Let x = n m^{-j}. Then m^j = n/x, m^{-j} = x/n. The term becomes (n/x) [ (1 - x/n)^n - 1 + x ]. The sum is over j, which corresponds to x = n m^{-j} for j=1,2,... i.e., x = n/m, n/m^2, ... So: U_{mn} = sum_{k=1}^\infty \frac{n}{x_k} [ (1 - \frac{x_k}{n})^n - 1 + x_k ] where x_k = n m^{-k}.
As n -> infinity, for fixed x_k (which requires k ~ log_m n), (1 - x/n)^n -> e^{-x}. So the term tends to \frac{n}{x} [ e^{-x} - 1 + x ] = n \frac{e^{-x} - 1 + x}{x}.
But x_k are discrete points in a geometric progression. The sum over k of this can be expressed as: U_{mn} = n \sum_{k=-\infty}^\infty \frac{e^{-x} - 1 + x}{x} + o(n)? Wait, the sum over k from 1 to infinity of something that depends on x_k = n m^{-k}. As n varies, the set of x_k scales with n. We can write k = log_m n - t, then x_k = n m^{-k} = m^t. So the sum over k becomes sum over t of m^t? Let's do it carefully.
Let k be integer. Write k = j. Then x_j = n m^{-j}. Then U_{mn} = \sum_{j=1}^\infty \frac{n}{x_j} [ (1 - x_j/n)^n - 1 + x_j ]. Now set j = \lfloor \log_m n \rfloor + r. Then x_j = n m^{-j} = n m^{-\lfloor \log_m n \rfloor - r} = m^{{ \log_m n }} m^{-r} (approximately, since n = m^{\log_m n} = m^{\lfloor \log_m n \rfloor + { \log_m n }}). Let \delta = { \log_m n }. Then n = m^{J + \delta} where J = \lfloor \log_m n \rfloor. Then x_{J+r} = m^{J+\delta} m^{-J-r} = m^{\delta - r}. So x_{J+r} = m^{\delta - r}. The sum over j from 1 to \infty becomes sum over r from -\infty to \infty? j=1 corresponds to r = 1 - J, which goes to -\infty as n->\infty. So effectively sum over all integers r: U_{mn} = \sum_{r=-\infty}^\infty n \frac{ (1 - m^{\delta - r}/n)^n - 1 + m^{\delta - r} }{ m^{\delta - r} }? Wait, x_j = m^{\delta - r}. But n is large. So (1 - x_j/n)^n = (1 - m^{\delta - r}/n)^n. As n->\infty, this tends to e^{-m^{\delta - r}}. So the term tends to n \frac{ e^{-m^{\delta - r}} - 1 + m^{\delta - r} }{ m^{\delta - r} } = n m^{r-\delta} ( e^{-m^{\delta - r}} - 1 + m^{\delta - r} ).
But careful: The sum over r from -\infty to \infty of this limiting term is infinite? As r -> -\infty, m^{\delta - r} -> \infty, e^{-m^{\delta - r}} -> 0, so term ~ n m^{r-\delta} ( -1 + m^{\delta - r} ) = n (1 - m^{r-\delta}) ~ n. Summing over r negative large would give infinite sum! But the original sum over j is only from 1 to \infty, which corresponds to r from 1-J to \infty. As n->\infty, the lower bound goes to -\infty. The limiting sum over all r would be divergent if we sum n (1 - m^{r-\delta}) over r from -\infty to something. But the original sum U_{mn} is finite for each n. The issue is that the approximation (1 - x/n)^n -> e^{-x} is not valid uniformly for r -> -\infty? Actually, for r -> -\infty, x_j = m^{\delta - r} becomes very large (>> n). But wait, x_j = n m^{-j}. If j is small, x_j is large. For j fixed, x_j = n m^{-j} ~ n, which is large. So for r negative large, x_j = m^{\delta - r} is huge, much larger than n? But we set x_j = n m^{-j}. If j is fixed, say j=1, then x_1 = n/m. This is O(n). So x_j is O(n) for j fixed. Then (1 - x_j/n)^n = (1 - m^{-j})^n. This does NOT tend to e^{-x_j} because x_j = n m^{-j} is large, not fixed! The limit e^{-x} assumes x is fixed as n->\infty. But if x is proportional to n, then (1 - x/n)^n = (1 - c)^n which is exponentially small, while e^{-x} = e^{-cn} is also exponentially small, but the ratio might not tend to 1? Actually, if x = cn with c constant, then (1 - c)^n vs e^{-cn}. For c>0, (1-c)^n = e^{n ln(1-c)}. This is not equal to e^{-cn} unless c is small. So the approximation (1 - x/n)^n ~ e^{-x} is only valid when x = o(n). For x ~ n, we need to keep the exact form.
Thus we must handle the region where x_j is comparable to n (i.e., j small) separately. That region contributes the n log_m n term. The region where x_j is o(n) (i.e., j large) contributes O(n). The region where x_j >> n (j negative? j can't be negative) doesn't occur because j starts at 1, so x_j <= n/m. So x_j is always O(n). For j=1, x_1 = n/m. For j large, x_j is small.
So we split the sum at some point. Let's define a threshold: let J be such that m^{-J} is small, say m^{-J} = n^{-1/2} or something. But maybe we can find an exact expression for U_{mn} in terms of known functions?
Another approach: Use the identity: \frac{1}{m^{k-1} - 1} = \int_0^1 \frac{t^{m^{k-1}-2} dt}{\text{something}}? Not sure.
Alternatively, we can use the generating function of the sum. Let's consider the exponential generating function: U_{mn} = \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{1}{m^{k-1} - 1}. This is the nth forward difference of the function f(k) = 1/(m^{k-1} - 1) at k=0, but with k=0 and k=1 excluded? Actually, the sum from k=0 to n \binom{n}{k} (-1)^k f(k) = (-1)^n \Delta^n f(0). For k=0, f(0) = 1/(m^{-1} - 1) = m/(1-m). For k=1, f(1) is infinite. So the sum from k=2 to n is not a simple forward difference.
But we can write: U_{mn} = \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{1}{m^{k-1} - 1} = \sum_{k=2}^\infty \binom{n}{k} (-1)^k \sum_{j=1}^\infty m^{-j(k-1)}. = \sum_{j=1}^\infty m^j \sum_{k=2}^n \binom{n}{k} (-1)^k m^{-jk}. = \sum_{j=1}^\infty m^j \left[ (1 - m^{-j})^n - 1 + n m^{-j} \right].
This is correct.
Now, we can use the expansion: (1 - m^{-j})^n = \sum_{i=0}^n \binom{n}{i} (-1)^i m^{-ji}. Then the term in brackets is: \sum_{i=2}^n \binom{n}{i} (-1)^i m^{-ji}. So U_{mn} = \sum_{j=1}^\infty m^j \sum_{i=2}^n \binom{n}{i} (-1)^i m^{-ji} = \sum_{i=2}^n \binom{n}{i} (-1)^i \sum_{j=1}^\infty m^{j(1-i)}. But \sum_{j=1}^\infty m^{j(1-i)} = \frac{m^{1-i}}{1 - m^{1-i}} = \frac{1}{m^{i-1} - 1}. This just recovers the original sum. So no new info.
Maybe we can use the integral representation for the sum over j: U_{mn} = \sum_{j=1}^\infty m^j \left[ e^{n \ln(1 - m^{-j})} - 1 + n m^{-j} \right].
Consider the function F(t) = m^t \left[ e^{n \ln(1 - m^{-t})} - 1 + n m^{-t} \right] for real t. Then U_{mn} = \sum_{j=1}^\infty F(j). The sum over j can be approximated by an integral plus a periodic function using Poisson summation or Euler-Maclaurin.
Let's try to apply the Mellin transform technique, which is standard for sums of the form \sum_{j} f(m^j). The Mellin transform of a sum \sum_{j} f(m^j) is \frac{1}{1 - m^{-s}} \mathcal{M}f. Then we can invert the transform.
Let f(u) = u [ (1 - 1/u)^n - 1 + n/u ] for u > 1? Our sum is \sum_{j=1}^\infty f(m^j) with f(u) = u [ (1 - 1/u)^n - 1 + n/u ].
But f(u) depends on n. We can write f(u) = u [ (1 - 1/u)^n - 1 ] + n. Wait, u * n/u = n. So f(u) = u [ (1 - 1/u)^n - 1 ] + n. Then \sum_{j=1}^\infty f(m^j) = \sum_{j=1}^\infty m^j [ (1 - m^{-j})^n - 1 ] + \sum_{j=1}^\infty n. But \sum_{j=1}^\infty n diverges! So we cannot split that way. The combination u [ (1 - 1/u)^n - 1 + n/u ] = u(1-1/u)^n - u + n. The sum \sum (n) diverges, but the sum \sum ( - u ) also diverges, and they cancel. So we must keep them together.
Let's write the sum as: U = \sum_{j=1}^\infty \left( m^j (1 - m^{-j})^n - m^j + n \right).
We can sum the first term and the second term separately if we use analytic continuation? Not directly.
Maybe we can use the identity: \sum_{j=1}^\infty m^j (1 - m^{-j})^n = \sum_{k=0}^n \binom{n}{k} (-1)^k \sum_{j=1}^\infty m^{j(1-k)} = \sum_{k=0}^n \binom{n}{k} (-1)^k \frac{m^{1-k}}{1 - m^{1-k}}. For k=0: \binom{n}{0} (-1)^0 \frac{m}{1-m} = \frac{m}{1-m}. For k=1: \binom{n}{1} (-1)^1 \frac{m^0}{1-m^0} = -n * \frac{1}{0} -> infinite. So the sum is divergent at k=1. This reflects the divergence of \sum m^j. But if we subtract m^j, we get: \sum_{j=1}^\infty \left( m^j (1 - m^{-j})^n - m^j \right) = \sum_{k=0}^n \binom{n}{k} (-1)^k \frac{m^{1-k}}{1 - m^{1-k}} - \sum_{j=1}^\infty m^j. The k=1 term in the sum is -n * \frac{1}{1-1} which is infinite. The sum \sum m^j is also infinite. Their difference is what we need? Actually, our U is \sum_{j} [ m^j (1 - m^{-j})^n - m^j + n ]. The n term is exactly the term that cancels the divergence from k=1? Let's check: if we take the k=1 term in the expansion of m^j (1 - m^{-j})^n, we have \binom{n}{1} (-1)^1 m^{j(1-1)} = -n. So m^j (1 - m^{-j})^n = \sum_{k \neq 1} ... + (-n) m^j * 1? Wait: (1 - m^{-j})^n = \sum_{k=0}^n \binom{n}{k} (-1)^k m^{-jk}. Multiply by m^j: m^j (1 - m^{-j})^n = \sum_{k=0}^n \binom{n}{k} (-1)^k m^{j(1-k)}. For k=1, the term is \binom{n}{1} (-1)^1 m^{0} = -n. This is independent of j! So summing over j, the k=1 term gives \sum_{j=1}^\infty (-n) = -\infty. The sum \sum_{j} m^j is also infinite. The combination m^j (1 - m^{-j})^n - m^j + n includes the k=0 term? Let's write: m^j (1 - m^{-j})^n - m^j + n = \sum_{k=0}^n \binom{n}{k} (-1)^k m^{j(1-k)} - m^j + n. The k=0 term is \binom{n}{0} (-1)^0 m^j = m^j. This cancels with -m^j. The k=1 term is -n. This cancels with +n. So the remaining sum is over k=2 to n: = \sum_{k=2}^n \binom{n}{k} (-1)^k m^{j(1-k)}. Summing over j: \sum_{j=1}^\infty m^{j(1-k)} = \frac{m^{1-k}}{1 - m^{1-k}} = \frac{1}{m^{k-1} - 1}. Thus U = \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{1}{m^{k-1} - 1}. This is consistent.
So the divergence at k=1 is handled by the -m^j + n combination.
Now, to find the asymptotic behavior, we can use the expression: U = \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{1}{m^{k-1} - 1}.
But perhaps there is a known asymptotic expansion for this sum. It looks like the expected number of nodes in a trie or something similar. In Knuth's book, Section 6.3 (Trie search), the average number of internal nodes in a trie built from n strings is: T_n = \sum_{k=1}^n \binom{n}{k} (-1)^{k+1} \frac{1}{1 - m^{-k}}? Not exactly.
Let's search memory: The expected number of nodes in an m-ary trie is sum_{k>=1} \binom{n}{k} (-1)^{k+1} \frac{m}{m-1} ... Actually, the sum for the expected external path length or internal path length often involves \sum_{k=1}^n \binom{n}{k} (-1)^{k+1} \frac{1}{1 - m^{-k}}.
Our sum is U = \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{1}{m^{k-1} - 1} = \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{1}{m^{k-1}(1 - m^{-(k-1)})} = \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{m^{-(k-1)}}{1 - m^{-(k-1)}}.
Let i = k-1. Then k = i+1. U = \sum_{i=1}^{n-1} \binom{n}{i+1} (-1)^{i+1} \frac{m^{-i}}{1 - m^{-i}} = -\sum_{i=1}^{n-1} \binom{n}{i+1} (-1)^i \frac{m^{-i}}{1 - m^{-i}}.
Not obviously standard.
Maybe we can find the asymptotic by using the integral representation of the sum over j: U = \sum_{j=1}^\infty m^j [ (1 - m^{-j})^n - 1 + n m^{-j} ].
Let’s set j = t, and consider the sum as a Riemann sum approximation of an integral. Write m^j = e^{j \ln m}. Let x = j \ln m. Then the sum is over x = \ln m, 2\ln m, ... The step size is \ln m. We have: U = \sum_{j=1}^\infty e^{x} [ (1 - e^{-x})^n - 1 + n e^{-x} ] where x = j \ln m. = \frac{1}{\ln m} \sum_{j} \Delta x e^{x} [ (1 - e^{-x})^n - 1 + n e^{-x} ].
As n -> \infty, the function inside varies on a scale of O(1) in x? Let's check: For large n, the function g_n(x) = e^{x} [ (1 - e^{-x})^n - 1 + n e^{-x} ]. The interesting behavior is when e^{-x} is of order 1/n, i.e., x ~ \ln n. So we can set x = \ln n + y. Then e^{x} = n e^{y}, e^{-x} = e^{-y}/n. Then: g_n(x) = n e^{y} [ (1 - e^{-y}/n)^n - 1 + e^{-y} ]. As n -> \infty, (1 - e^{-y}/n)^n -> e^{-e^{-y}}. So g_n(x) ~ n e^{y} [ e^{-e^{-y}} - 1 + e^{-y} ] = n h(y), where h(y) = e^{y} ( e^{-e^{-y}} - 1 + e^{-y} ).
The sum over j becomes sum over y = j \ln m - \ln n. The spacing in y is \ln m. As n -> \infty, \ln n grows, so the set of y values becomes dense in the sense that it covers the real line with a constant spacing \ln m? Actually, \ln n mod \ln m will be dense if \ln m is irrational? But we are summing over all j, so y runs over a shifted lattice: y = j \ln m - \ln n. The sum is \sum_{j} g_n(j \ln m). For large n, g_n(j \ln m) ~ n h(j \ln m - \ln n). So the sum is approximately n \sum_{j} h(j \ln m - \ln n). The function h(y) decays exponentially as y -> \pm \infty? Let's check: As y -> +\infty, e^{-y} -> 0, e^{-e^{-y}} = 1 - e^{-y} + e^{-2y}/2 - ... So h(y) ~ e^{y} ( e^{-2y}/2 ) = e^{-y}/2 -> 0. As y -> -\infty, e^{-y} -> \infty, e^{-e^{-y}} -> 0. Then h(y) ~ e^{y} ( -1 + e^{-y} ) = e^{y} e^{-y} - e^{y} = 1 - e^{y} ~ 1. So h(y) ~ 1 as y -> -\infty, and decays exponentially as y -> +\infty. The sum \sum_{j} h(j \ln m - \ln n) over all integers j would diverge because as j -> -\infty, y -> -\infty, h(y) ~ 1, and there are infinitely many negative j. But our original sum starts at j=1. As n -> \infty, \ln n -> \infty, so the smallest j is 1, which corresponds to y = \ln m - \ln n. This goes to -\infty. So the sum includes a range of y from about -\ln n up to +\infty. The number of terms with y negative is about (\ln n)/\ln m = \log_m n. For each such term, h(y) ~ 1. So the sum \sum_{j=1}^\infty h(j \ln m - \ln n) ~ \log_m n + constant? Because the sum of h(y) over the negative y terms is approximately the number of terms (since h(y)~1), which is ~ \log_m n. Plus a sum over positive y terms which converges to a constant. So the sum is ~ \log_m n + C(\ln n) where C is a periodic function with period \ln m? Wait, the sum over j of h(j \ln m - \ln n) = \sum_{k=1}^\infty h(k \ln m - \ln n). Let \ln n = t. Then sum = \sum_{k=1}^\infty h(k \ln m - t). As t -> \infty, this sum behaves like \frac{t}{\ln m} + \text{periodic} + o(1)? Let's analyze: For large t, the sum is over k from 1 to \infty. The terms for k such that k \ln m - t < 0 (i.e., k < t/\ln m) have h ~ 1. The number of such terms is floor(t/\ln m). So the sum is floor(t/\ln m) + \sum_{k > t/\ln m} h(k \ln m - t). The remaining sum is over k >= floor(t/\ln m)+1. Let k = floor(t/\ln m) + r, r=1,2,... Then k \ln m - t = r \ln m - {t/\ln m} \ln m. So the sum over r is a periodic function of t. Thus: \sum_{k=1}^\infty h(k \ln m - t) = \frac{t}{\ln m} - {t/\ln m} + \sum_{r=1}^\infty h(r \ln m - {t/\ln m} \ln m) + o(1) as t -> \infty. The o(1) comes from the fact that for the terms with k < t/\ln m, h(y) is not exactly 1 but approaches 1 exponentially fast as y -> -\infty. The error from those terms is sum_{k=1}^{floor(t/\ln m)} (h(k \ln m - t) - 1). As t -> \infty, these y's are negative large, so h(y) = 1 + O(e^{y})? Actually, h(y) = 1 - e^{y} + ... for y -> -\infty? Let's check: h(y) = e^{y} ( e^{-e^{-y}} - 1 + e^{-y} ). For y -> -\infty, e^{-y} is large, e^{-e^{-y}} is very small, so h(y) = e^{y} ( -1 + e^{-y} ) = 1 - e^{y}. So h(y) = 1 - e^{y} + o(e^{y}). Then h(y) - 1 = -e^{y}. So the sum of (h(y)-1) over negative y terms is sum_{k=1}^{floor(t/\ln m)} -e^{k \ln m - t} = -e^{-t} \sum_{k=1}^{floor(t/\ln m)} m^k = O(e^{-t} m^{t/\ln m}) = O(e^{-t} e^{t}) = O(1). So the error is O(1), not o(1)? Actually, the sum of e^{y} over k=1 to floor(t/\ln m) is e^{-t} \sum_{k=1}^{floor(t/\ln m)} m^k ~ e^{-t} \frac{m}{m-1} m^{floor(t/\ln m)} ~ \frac{m}{m-1} e^{-t} m^{t/\ln m} = \frac{m}{m-1} e^{-t} e^{t} = \frac{m}{m-1}. So it's O(1). Thus the sum is \frac{t}{\ln m} + P(t) + O(1) where P is periodic.
But wait, we had U ~ n \sum h(y) where y = j \ln m - \ln n. So U ~ n ( \frac{\ln n}{\ln m} + P(\ln n) ) = n \log_m n + n P(\ln n) + O(n)? But earlier we had the sum of h(y) itself is ~ \log_m n + O(1). Multiplying by n gives n \log_m n + n * (periodic) + O(n). But we also have the tail contributions from the region where the approximation g_n ~ n h is not valid? We must be careful: The sum U is exactly \sum_{j=1}^\infty g_n(j \ln m). We approximated g_n(x) by n h(x - \ln n) for all x? But this approximation is only valid when e^{-x} is small? Actually, g_n(x) = e^{x} [ (1 - e^{-x})^n - 1 + n e^{-x} ]. For x fixed (not growing with n), as n -> \infty, e^{-x} is constant. Then (1 - e^{-x})^n decays exponentially if e^{-x} > 0. So g_n(x) = e^{x} [ -1 + n e^{-x} ] + exponentially small = n - e^{x} + exponentially small. This matches the approximation n h(y) if we set y = x - \ln n? For x fixed, y = x - \ln n -> -\infty. Then h(y) ~ 1 - e^{y} = 1 - e^{x - \ln n} = 1 - e^{x}/n. So n h(y) ~ n - e^{x}. This matches! So the approximation g_n(x) ~ n h(x - \ln n) is actually valid for all x, as long as we define h(y) properly for all y. Let's check: For y -> -\infty, h(y) = 1 - e^{y} + ... This corresponds to x = \ln n + y fixed? Actually, if y -> -\infty, x = \ln n + y can be fixed. Then n h(y) ~ n (1 - e^{y}) = n - e^{x}. And g_n(x) = e^{x} [ (1 - e^{-x})^n - 1 + n e^{-x} ]. For fixed x, (1 - e^{-x})^n is exponentially small, so g_n(x) ~ e^{x} ( -1 + n e^{-x} ) = n - e^{x}. They match exactly! For x large (y large), the approximation (1 - e^{-x})^n ~ e^{-n e^{-x}} is valid because e^{-x} is small. So indeed, the approximation g_n(x) = n h(x - \ln n) is asymptotically exact for all x as n -> \infty, with an error that is small uniformly? Let's check the error: g_n(x) - n h(x - \ln n) = e^{x} [ (1 - e^{-x})^n - e^{-n e^{-x}} ] + n e^{x} [ e^{-n e^{-x}} - (1 - e^{-x} + e^{-2x}/2?) Wait, h(y) is defined as e^{y} ( e^{-e^{-y}} - 1 + e^{-y} ). With y = x - \ln n, n h(y) = n e^{x - \ln n} ( e^{-e^{-x + \ln n}} - 1 + e^{-x + \ln n} ) = e^{x} ( e^{-n e^{-x}} - 1 + n e^{-x} ). So n h(x - \ln n) = e^{x} ( e^{-n e^{-x}} - 1 + n e^{-x} ). The difference is g_n(x) - n h(x - \ln n) = e^{x} [ (1 - e^{-x})^n - e^{-n e^{-x}} ]. Now, (1 - e^{-x})^n = e^{n \ln(1 - e^{-x})}. The error is e^{x} e^{-n e^{-x}} ( e^{n \ln(1 - e^{-x}) + n e^{-x}} - 1 ). The exponent n ( \ln(1 - e^{-x}) + e^{-x} ) = n ( - e^{-2x}/2 - e^{-3x}/3 - ... ). For x fixed, this is O(n e^{-2x}) which is large negative? Actually, if x is fixed, e^{-x} is constant, the exponent is -n * const, so (1 - e^{-x})^n decays exponentially, while e^{-n e^{-x}} also decays exponentially. Their difference is also exponentially small. For x large, e^{-x} is small, the exponent is -n e^{-2x}/2 - ... So the relative error is small if n e^{-2x} is small? But we need the sum of errors to be small compared to the sum itself. The sum U is O(n \log n). The errors for x large (j large) might contribute O(n). We need to be careful.
But the standard method for such sums is to use the Mellin transform or to apply the Euler-Maclaurin formula to the sum \sum_{j=1}^\infty f_n(j) where f_n(j) = m^j [ (1 - m^{-j})^n - 1 + n m^{-j} ].
Alternatively, we can use the known result for the sum \sum_{j} m^j (1 - m^{-j})^n. There is a known asymptotic expansion for the expected number of nodes in a trie. Let's recall: The expected number of internal nodes in a trie built from n strings over an m-ary alphabet is: T_n = \sum_{k=1}^n \binom{n}{k} (-1)^{k+1} \frac{1}{1 - m^{-k}}? Actually, the number of nodes in a trie is sum_{k=0}^\infty (something). There's a known result by Flajolet, etc. But we have a specific sum.
Maybe we can find the asymptotic by evaluating the sum exactly for integer m using the identity: \sum_{j=1}^\infty m^j [ (1 - m^{-j})^n - 1 + n m^{-j} ] = \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{1}{m^{k-1} - 1}.
For integer m, we can use the fact that \frac{1}{m^{k-1} - 1} = \sum_{r=1}^\infty \frac{1}{m^{r(k-1)}}? That's the same as before.
Another idea: Use the integral representation: \frac{1}{m^{k-1} - 1} = \int_0^\infty e^{-t(m^{k-1} - 1)} dt? No, that's for 1/x.
Maybe we can use the generating function approach. Consider the exponential generating function: F(z) = \sum_{n=0}^\infty U_{mn} \frac{z^n}{n!}. Then U_{mn} = n! [z^n] F(z). We have U_{mn} = \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{1}{m^{k-1} - 1}. So F(z) = \sum_{n=0}^\infty \frac{z^n}{n!} \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{1}{m^{k-1} - 1} = \sum_{k=2}^\infty \frac{(-1)^k}{m^{k-1} - 1} \sum_{n=k}^\infty \binom{n}{k} \frac{z^n}{n!} = \sum_{k=2}^\infty \frac{(-1)^k}{m^{k-1} - 1} \sum_{n=k}^\infty \frac{z^n}{k! (n-k)!} = \sum_{k=2}^\infty \frac{(-1)^k}{k! (m^{k-1} - 1)} z^k e^z. = e^z \sum_{k=2}^\infty \frac{(-z)^k}{k! (m^{k-1} - 1)}. This is not a simple elementary function.
Maybe we can find the asymptotic by using the fact that U_{mn} is the nth forward difference of something. But the sum we have is \sum_{k=2}^n \binom{n}{k} (-1)^k f(k) with f(k) = 1/(m^{k-1} - 1). The asymptotic of such sums for large n can be found by the saddle point method or by relating to the generating function. The function f(k) is analytic for Re(k) > 1? Actually, m^{k-1} - 1 has zeros at k = 1 + 2\pi i l / \ln m for integer l. So f(k) has poles at those points.
There is a known technique: The sum S_n = \sum_{k} \binom{n}{k} (-1)^k f(k) can be expressed as \frac{1}{2\pi i} \int f(z) \frac{\Gamma(n+1) \Gamma(-z)}{\Gamma(n+1-z)} dz? Or using the binomial transform: \sum_{k=0}^n \binom{n}{k} (-1)^k f(k) = \Delta^n f(0). If f is analytic, we can use Cauchy's integral. But our sum starts at k=2.
Let's try to use the representation: U_{mn} = \sum_{j=1}^\infty m^j [ (1 - m^{-j})^n - 1 + n m^{-j} ]. We can apply the Euler-Maclaurin formula directly to this sum. The function F(t) = m^t [ (1 - m^{-t})^n - 1 + n m^{-t} ] is smooth and decays for large t. The sum from j=1 to \infty is approximately \int_1^\infty F(t) dt + \frac{1}{2} F(1) + \frac{1}{12} F'(1) - ... But F(t) depends on n. We need to evaluate the integral asymptotically.
Let's change variable: x = m^t. Then t = \log_m x, dt = dx/(x \ln m). The sum over j corresponds to x = m, m^2, m^3, ... The integral \int_1^\infty F(t) dt = \int_m^\infty \frac{x [ (1 - 1/x)^n - 1 + n/x ]}{x \ln m} dx? Wait, F(t) = m^t [ (1 - m^{-t})^n - 1 + n m^{-t} ]. With x = m^t, m^t = x, m^{-t} = 1/x. So F(t) = x [ (1 - 1/x)^n - 1 + n/x ]. dt = dx/(x \ln m). So the integral is: \int_m^\infty x [ (1 - 1/x)^n - 1 + n/x ] \frac{dx}{x \ln m} = \frac{1}{\ln m} \int_m^\infty [ (1 - 1/x)^n - 1 + n/x ] dx.
Now, this integral can be evaluated asymptotically for large n. Let's compute: I = \int_m^\infty [ (1 - 1/x)^n - 1 + n/x ] dx.
We can split the integral: I = \int_m^\infty (1 - 1/x)^n dx - \int_m^\infty 1 dx + n \int_m^\infty \frac{dx}{x}. The last two integrals diverge! But combined, the integral converges. We must combine them: I = \int_m^\infty [ (1 - 1/x)^n - 1 + n/x ] dx.
We can evaluate this integral exactly? Let's try substitution y = 1/x. Then x = 1/y, dx = -dy/y^2. Limits: x=m -> y=1/m; x=\infty -> y=0. I = \int_0^{1/m} [ (1 - y)^n - 1 + n y ] \frac{dy}{y^2}. = \int_0^{1/m} \frac{(1-y)^n - 1 + n y}{y^2} dy.
This integral converges at y=0 because the numerator is O(y^2). Let's check: (1-y)^n = 1 - n y + n(n-1)/2 y^2 - ... So numerator ~ n(n-1)/2 y^2. So integrand ~ n(n-1)/2, finite.
We can expand (1-y)^n using binomial theorem: (1-y)^n = \sum_{k=0}^n \binom{n}{k} (-y)^k. Then numerator = \sum_{k=2}^n \binom{n}{k} (-y)^k. So I = \int_0^{1/m} \sum_{k=2}^n \binom{n}{k} (-1)^k y^{k-2} dy = \sum_{k=2}^n \binom{n}{k} (-1)^k \int_0^{1/m} y^{k-2} dy = \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{(1/m)^{k-1}}{k-1} = \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{m^{-(k-1)}}{k-1}.
This is not our U_{mn}. Our U_{mn} = \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{1}{m^{k-1} - 1}. Note that \frac{1}{m^{k-1} - 1} = \frac{m^{-(k-1)}}{1 - m^{-(k-1)}} = \sum_{r=1}^\infty m^{-r(k-1)}. So U_{mn} = \sum_{r=1}^\infty \sum_{k=2}^n \binom{n}{k} (-1)^k m^{-r(k-1)} = \sum_{r=1}^\infty m^r \sum_{k=2}^n \binom{n}{k} (-1)^k m^{-rk} = \sum_{r=1}^\infty m^r [ (1 - m^{-r})^n - 1 + n m^{-r} ]. This matches our earlier expression.
So the integral I we got is \frac{1}{\ln m} \int_m^\infty ... dx = \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{m^{-(k-1)}}{k-1}. That's different from U_{mn}. The sum over j is a discrete sum, not an integral. The Euler-Maclaurin correction terms will give the difference between the sum and the integral. The sum U_{mn} = \sum_{j=1}^\infty F(j) with F(t) = m^t [ (1 - m^{-t})^n - 1 + n m^{-t} ].
We can apply the Euler-Maclaurin formula: \sum_{j=1}^\infty F(j) = \int_1^\infty F(t) dt + \frac{1}{2} F(1) + \sum_{k=1}^\infty \frac{B_{2k}}{(2k)!} F^{(2k-1)}(1) - \text{limit at infinity?} Since F and its derivatives tend to 0 as t->\infty (exponentially), the boundary terms at infinity vanish.
So U_{mn} = I + \frac{1}{2} F(1) + \sum_{k=1}^\infty \frac{B_{2k}}{(2k)!} F^{(2k-1)}(1).
Now we need the asymptotic behavior of I and the corrections as n -> \infty.
We already have I = \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{m^{-(k-1)}}{k-1}. Can we find the asymptotic of I? Yes, this is a known sum. Let's analyze I.
I = \int_0^{1/m} \frac{(1-y)^n - 1 + n y}{y^2} dy. We can split the integral: \int_0^{1/m} \frac{(1-y)^n}{y^2} dy - \int_0^{1/m} \frac{1 - n y}{y^2} dy? The second integral diverges at 0? Actually, 1 - n y ~ 1, so 1/y^2 is not integrable at 0. So we must keep them combined. Better to write: I = \int_0^{1/m} \frac{(1-y)^n - e^{-n y} + e^{-n y} - 1 + n y}{y^2} dy. But e^{-n y} - 1 + n y is O(n^2 y^2). The integral of (e^{-n y} - 1 + n y)/y^2 from 0 to 1/m can be computed. Alternatively, use the substitution y = t/n. Then dy = dt/n. I = \int_0^{n/m} \frac{(1 - t/n)^n - 1 + t}{(t/n)^2} \frac{dt}{n} = n \int_0^{n/m} \frac{(1 - t/n)^n - 1 + t}{t^2} dt. As n -> \infty, (1 - t/n)^n -> e^{-t}. The upper limit n/m -> \infty. So: I ~ n \int_0^\infty \frac{e^{-t} - 1 + t}{t^2} dt + o(n)? But wait, is the integral convergent? \int_0^\infty \frac{e^{-t} - 1 + t}{t^2} dt. At t=0, integrand ~ (1 - t + t^2/2 - ... - 1 + t)/t^2 = 1/2, finite. At infinity, e^{-t} -> 0, so integrand ~ (-1 + t)/t^2 ~ 1/t, which diverges! So the integral \int_0^\infty (e^{-t} - 1 + t)/t^2 dt diverges logarithmically. That makes sense because I has a logarithmic divergence from the large x region? But earlier we said I = \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{m^{-(k-1)}}{k-1}. Let's check the asymptotic of this sum. For large n, the terms with k small give the leading contribution? C(n,k) ~ n^k/k!. So sum_{k=2} n^k/k! * 1/(k-1) * m^{-(k-1)}? That's like n^2/(2m) - n^3/(18 m^2) + ... It's a polynomial in n? Actually, the sum goes up to n, so the maximum k is n. For large k, the terms are C(n,k)(-1)^k m^{-k}/k. This is like the alternating binomial sum with weights 1/k. There is a known identity: \sum_{k=1}^n \binom{n}{k} (-1)^{k-1} \frac{x^k}{k} = \int_0^x \frac{(1 - t)^n - 1}{t} dt? Actually, \sum_{k=1}^n \binom{n}{k} (-1)^{k-1} \frac{x^k}{k} = \int_0^x \frac{1 - (1-t)^n}{t} dt = H_n - H_{n, something}? Wait, \sum_{k=1}^n \binom{n}{k} (-1)^{k-1} \frac{1}{k} = H_n. And \sum_{k=1}^n \binom{n}{k} (-1)^{k-1} \frac{x^k}{k} = \int_0^x \frac{1 - (1-t)^n}{t} dt. Our sum I is \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{m^{-(k-1)}}{k-1} = - \sum_{k=2}^n \binom{n}{k} (-1)^{k-1} \frac{m^{-(k-1)}}{k-1}. Let i = k-1. Then i from 1 to n-1: - \sum_{i=1}^{n-1} \binom{n}{i+1} (-1)^i \frac{m^{-i}}{i}. This is not exactly the standard harmonic sum.
But we can relate I to the harmonic numbers. Note that: \sum_{k=1}^n \binom{n}{k} (-1)^{k-1} \frac{x^k}{k} = \int_0^x \frac{1 - (1-t)^n}{t} dt. We have I = \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{m^{-(k-1)}}{k-1} = - \sum_{k=2}^n \binom{n}{k} (-1)^{k-1} \frac{(1/m)^{k-1}}{k-1}. Let S = \sum_{k=1}^n \binom{n}{k} (-1)^{k-1} \frac{x^k}{k}. Then I = - \frac{1}{x} \sum_{k=2}^n \binom{n}{k} (-1)^{k-1} \frac{x^k}{k-1}? Not exactly.
Maybe we can find the asymptotic of I directly from the integral representation: I = \int_0^{1/m} \frac{(1-y)^n - 1 + n y}{y^2} dy. We can integrate by parts. Let u = (1-y)^n - 1 + n y, dv = dy/y^2. du = n [ - (1-y)^{n-1} + 1 ] dy, v = -1/y. I = [ - \frac{(1-y)^n - 1 + n y}{y} ]_0^{1/m} + \int_0^{1/m} \frac{n [ - (1-y)^{n-1} + 1 ]}{y} dy. At y=0, (1-y)^n - 1 + n y ~ n(n-1)/2 y^2, so u/y ~ n(n-1)/2 y -> 0. At y=1/m, u = (1 - 1/m)^n - 1 + n/m. So I = - m [ (1 - 1/m)^n - 1 + n/m ] + n \int_0^{1/m} \frac{1 - (1-y)^{n-1}}{y} dy. = - m (1 - 1/m)^n + m - n + n \int_0^{1/m} \frac{1 - (1-y)^{n-1}}{y} dy.
Now, the integral J = \int_0^{1/m} \frac{1 - (1-y)^{n-1}}{y} dy. Let t = n y. Then y = t/n, dy = dt/n. J = \int_0^{(n-1)/m? Actually, 1/m -> t = n/m. J = \int_0^{n/m} \frac{1 - (1 - t/n)^{n-1}}{t} dt. As n -> \infty, (1 - t/n)^{n-1} -> e^{-t}. The upper limit goes to \infty. So J ~ \int_0^\infty \frac{1 - e^{-t}}{t} dt? But \int_0^\infty \frac{1 - e^{-t}}{t} dt diverges! Wait, \int_0^1 \frac{1 - e^{-t}}{t} dt converges, and \int_1^\infty \frac{1 - e^{-t}}{t} dt ~ \int_1^\infty \frac{1}{t} dt diverges logarithmically. So J ~ \ln n + \gamma? Let's check: \int_0^{n/m} \frac{1 - e^{-t}}{t} dt = \ln(n/m) + \gamma + o(1)? Actually, \int_0^z \frac{1 - e^{-t}}{t} dt = \ln z + \gamma + O(1/z). This is a known result: the integral of (1 - e^{-t})/t from 0 to z is \ln z + \gamma + E_1(z) where E_1 is the exponential integral. As z->\infty, E_1(z) ~ e^{-z}/z -> 0. So J ~ \ln n - \ln m + \gamma.
Thus I ~ - m (1 - 1/m)^n + m - n + n [ \ln n - \ln m + \gamma + o(1) ]. Since m > 1, (1 - 1/m)^n decays exponentially. So: (1 - 1/m)^n = e^{-n \ln(1 - 1/m)^{-1}}? Actually, it's exponentially small. So I ~ n \ln n - n (\ln m + 1 - \gamma) + m + o(n)? Wait, m is constant. So I ~ n \ln n - n (\ln m + 1 - \gamma) + O(1)? Let's check: I = n \int_0^{n/m} \frac{(1 - t/n)^n - 1 + t}{t^2} dt. We can also evaluate I by expanding (1 - t/n)^n. But the above seems correct: I = n \ln n - n (\ln m + 1 - \gamma) + m + o(n). But we need to be careful: J = \int_0^{n/m} \frac{1 - (1 - t/n)^{n-1}}{t} dt. The asymptotic of J is indeed \ln(n/m) + \gamma + o(1) if we replace (1 - t/n)^{n-1} by e^{-t}. But we must justify the error. The error from the approximation (1 - t/n)^{n-1} = e^{-t} (1 - t/(2n) + ...) will give a constant term O(1). So I = n \ln n - n (\ln m + 1 - \gamma) + C + o(n)? Wait, I has a term -n + n \ln n - n \ln m + n \gamma + m + o(n)? That's n \ln n - n(1 + \ln m - \gamma) + m + o(n). But m is constant, so it's O(1). So I ~ n \ln n - n (\ln m + 1 - \gamma) + O(1).
But recall U_{mn} = \sum_{j=1}^\infty F(j) = I + \frac{1}{2} F(1) + \sum_{k=1}^\infty \frac{B_{2k}}{(2k)!} F^{(2k-1)}(1). The corrections involve F(1) and derivatives at 1. Let's evaluate F(1): F(1) = m [ (1 - 1/m)^n - 1 + n/m ] = m (1 - 1/m)^n - m + n. As n -> \infty, (1 - 1/m)^n is exponentially small. So F(1) ~ n - m + o(1).
So I + \frac{1}{2} F(1) ~ n \ln n - n (\ln m + 1 - \gamma) + m + \frac{1}{2}(n - m) + o(n) = n \ln n - n (\ln m + \frac{1}{2} - \gamma) + \frac{m}{2} + o(n).
But wait, this is the Euler-Maclaurin sum with only the first correction. The higher derivatives at 1 might also contribute terms of order n? Let's check F(t) for t near 1. F(t) = m^t [ (1 - m^{-t})^n - 1 + n m^{-t} ]. For t=1, this is O(n). The derivatives F'(t) will also be O(n) because differentiating n m^{-t} gives -n \ln m m^{-t} which is O(n). So the Euler-Maclaurin sum will have corrections of order n from all derivatives. So the simple integral plus 1/2 F(1) is not sufficient; we need to sum the entire asymptotic series of corrections, which will yield a different coefficient for the n term.
Actually, the Euler-Maclaurin formula is an exact identity for a finite sum, but here we have an infinite sum. The formula with remainder would involve an integral of the derivative times a Bernoulli polynomial. The sum of all corrections can be represented as a periodic function? Actually, the sum \sum_{j=1}^\infty F(j) can be expressed using the Mellin transform. The Mellin transform of the sum over j of F(j) is \zeta(s) times something? Wait, the sum over j=1 to \infty of F(j) is not a Mellin transform of a single function because F depends on n. But we can use the fact that F(t) = m^t G(m^t) where G(x) = x [ (1 - 1/x)^n - 1 + n/x ]? No, F(t) = m^t [ (1 - m^{-t})^n - 1 + n m^{-t} ].
Let's try the Mellin transform approach directly on the sum: U = \sum_{j=1}^\infty m^j [ (1 - m^{-j})^n - 1 + n m^{-j} ]. Consider the function h(x) = (1 - 1/x)^n - 1 + n/x. Then U = \sum_{j=1}^\infty m^j h(m^j). We can write this as a sum over a geometric progression. The Mellin transform of a sum \sum_{j} f(m^j) is \frac{1}{1 - m^{-s}} \mathcal{M}f. Here f(x) = x h(x) = x [ (1 - 1/x)^n - 1 + n/x ] = x(1-1/x)^n - x + n. But x(1-1/x)^n = x \sum_{k=0}^n \binom{n}{k} (-1)^k x^{-k} = \sum_{k=0}^n \binom{n}{k} (-1)^k x^{1-k}. So f(x) = \sum_{k=0}^n \binom{n}{k} (-1)^k x^{1-k} - x + n. The terms: k=0 gives x, cancels with -x. k=1 gives -n, cancels with +n. So f(x) = \sum_{k=2}^n \binom{n}{k} (-1)^k x^{1-k}. This is a finite sum of powers. The Mellin transform of x^{1-k} is \int_0^\infty x^{1-k} x^{s-1} dx = \int_0^\infty x^{s-k} dx, which converges only for Re(s) < k-1 and is a distribution (pole at s = k-1). So the Mellin transform of f is a sum of delta functions? Actually, since f is a polynomial in x^{-1} with finite terms, it's not integrable on (0,\infty) unless we consider it as a distribution on a contour. This suggests that the Mellin transform method might be tricky because f(x) does not decay as x->\infty (it's a polynomial in 1/x, so it goes to 0 as x->\infty, but as x->0, it blows up). But our sum is over x = m^j, j>=1, so x >= m. The function is only evaluated for x >= m. We can extend f(x) to be 0 for x < m? That would introduce discontinuities.
Another approach: Use the exact sum representation: U = \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{1}{m^{k-1} - 1}. We can use the identity: \frac{1}{m^{k-1} - 1} = \int_0^1 \frac{t^{m^{k-1}-2} dt}{\text{?}} No.
Maybe we can relate this to the expected value of the number of nodes in a trie. In Knuth's book, the expected number of internal nodes in an m-ary trie built from n random strings is: T_n = \sum_{k=1}^n \binom{n}{k} (-1)^{k+1} \frac{1}{1 - m^{-k}}? Actually, the expected number of nodes in a trie is sum_{i=0}^\infty (1 - (1 - m^{-i})^n - n m^{-i} (1 - m^{-i})^{n-1})? Not sure.
Let's search my memory for the exact asymptotic of U_{mn}. The problem says "Find the asymptotic value of the function U_{mn} ... when m is any fixed number greater than 1." And it references exercise 47 and 48 which deal with U_n = sum_{j} (n/2^j) e^{-n/2^j}. That sum is bounded. Our U_{mn} is not bounded; it grows like n log_m n. But maybe the asymptotic value includes the leading term n log_m n plus a periodic term times n plus a constant term? The problem might expect an answer like: U_{mn} = n \log_m n + n P(\log_m n) + O(1) where P is a periodic function. Or maybe they want the constant term as well.
Let's re-read the problem statement: "Find the asymptotic value of the function U_{mn} = sum_{k >= 2} binom(n,k) (-1)^k / (m^{k-1} - 1) when m is any fixed number greater than 1." The phrase "asymptotic value" might mean the leading asymptotic behavior as n -> infinity. In many of Knuth's exercises, "asymptotic value" means an expansion up to O(1) or O(1/n). The difficulty is HM24, so it's a moderately hard problem.
Looking at the surrounding exercises: 47 is HM21, 48 is HM24, 49 is HM44. Exercise 50 is HM24. Exercise 47: "Prove that sum_{j >= 1} (n/2^j) e^{-n/2^j} is a bounded function of n." Exercise 48: "Find the asymptotic value of the quantity V_n defined in exercise 38, using a method analogous to the text's study of U_n, obtaining terms up to O(1)." Exercise 49: "Extend the asymptotic formula (47) for U_n to O(n^{-1})." So U_n and V_n are quantities studied in the text. The text mentions U_n in Eq. (47) which we don't have here, but likely U_n = sum_{k>=1} (n/2^k) e^{-n/2^k}. Exercise 47 asks to prove it's bounded. Exercise 48 asks for asymptotic value of V_n up to O(1). Exercise 49 asks to extend U_n to O(n^{-1}). Exercise 50 is a different sum U_{mn}. It might have a similar structure.
Let's try to derive the asymptotic expansion of U_{mn} carefully.
We have U = \sum_{j=1}^\infty m^j [ (1 - m^{-j})^n - 1 + n m^{-j} ].
Let’s set m^j = x. Then j = log_m x. The sum is over x = m, m^2, m^3, ... Define a function: g_n(x) = x [ (1 - 1/x)^n - 1 + n/x ]. Then U = \sum_{k=1}^\infty g_n(m^k).
We can apply the Euler-Maclaurin formula to the sum over k. But g_n depends on n. Alternatively, we can use the integral representation: \sum_{k=1}^\infty g_n(m^k) = \frac{1}{\ln m} \int_1^\infty g_n(m^t) dt + \sum_{l=-\infty}^\infty \frac{1}{\ln m} \mathcal{M}[g_n \circ m^t](2\pi i l / \ln m) ? This is the Poisson summation formula for a geometric progression.
The standard approach for sums of the form \sum_{k} f(m^k) is to use the Mellin transform. The Mellin transform of the sum is \zeta(s) * something? Actually, if we consider the sum S(n) = \sum_{k=1}^\infty g_n(m^k), we can write the Mellin transform with respect to n? Or with respect to x?
Another method: Use the binomial expansion of (1 - 1/x)^n: (1 - 1/x)^n = \sum_{k=0}^n \binom{n}{k} (-1)^k x^{-k}. Then g_n(x) = \sum_{k=2}^n \binom{n}{k} (-1)^k x^{1-k}. So U = \sum_{j=1}^\infty \sum_{k=2}^n \binom{n}{k} (-1)^k m^{j(1-k)} = \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{m^{1-k}}{1 - m^{1-k}}. This is our original sum.
Now, to find the asymptotic as n -> \infty, we can use the saddle point method on the binomial sum. The sum is over k. The term is \binom{n}{k} (-1)^k \frac{1}{m^{k-1} - 1}. For large n, the binomial coefficient is large, but the alternating sign causes cancellation. The sum is the nth difference of f(k) = 1/(m^{k-1} - 1). If f(k) is analytic, the nth difference is given by the contour integral: \Delta^n f(0) = \frac{n!}{2\pi i} \oint \frac{f(z)}{z(z-1)...(z-n)} dz. But our sum is \sum_{k=2}^n \binom{n}{k} (-1)^k f(k) = \Delta^n f(0) - f(0) + n f(1). Since f(1) is infinite, this is not directly applicable.
Wait, we can write: U = \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{1}{m^{k-1} - 1} = \sum_{k=2}^\infty \binom{n}{k} (-1)^k \frac{1}{m^{k-1} - 1} (since binom(n,k)=0 for k>n). This is the binomial transform of the sequence a_k = 1/(m^{k-1} - 1) for k>=2, with a_0 = a_1 = 0. The asymptotic of the binomial transform of a sequence a_k as n -> \infty can be found if the generating function A(z) = \sum_{k=0}^\infty a_k z^k has certain singularities. The binomial transform is b_n = \sum_{k=0}^n \binom{n}{k} (-1)^k a_k. Then the exponential generating function of b_n is B(z) = e^z A(-z)? Actually, \sum b_n \frac{z^n}{n!} = e^z \sum a_n \frac{(-z)^n}{n!}. So if we can find the asymptotics of the coefficients of e^z A(-z), we can get b_n.
Let A(z) = \sum_{k=2}^\infty \frac{z^k}{m^{k-1} - 1}. Then b_n = \sum_{k=0}^n \binom{n}{k} (-1)^k a_k = U_{mn} (with a_0=a_1=0). The exponential generating function is B(z) = e^z A(-z). We want b_n = n! [z^n] B(z).
This might be amenable to singularity analysis. The function A(z) = \sum_{k=2}^\infty \frac{z^k}{m^{k-1} - 1}. For large k, m^{k-1} - 1 ~ m^{k-1}, so the terms behave like z^k / m^{k-1} = m (z/m)^k. So the series converges for |z| < m. It has singularities at z = m and possibly other points where m^{k-1} - 1 = 0? No, those are zeros of the denominator in the sum over k? Wait, A(z) is a sum over k, not a function with poles in z. The denominator is m^{k-1} - 1, which depends on k, not on z. So A(z) is a power series in z with radius of convergence m. It can be analytically continued beyond |z|<m. The asymptotic of b_n depends on the singularities of A(z). The binomial transform b_n = \sum_{k} \binom{n}{k} (-1)^k a_k is the nth difference of a_k. If a_k ~ C k^{-\alpha} \beta^k, then b_n might be something else.
Alternatively, we can use the integral representation we had: U = \int_0^{1/m} \frac{(1-y)^n - 1 + n y}{y^2} dy + \text{corrections from Euler-Maclaurin}. We already computed the integral I = \int_0^{1/m} \frac{(1-y)^n - 1 + n y}{y^2} dy = n \ln n - n (\ln m + 1 - \gamma) + m + o(n)? Wait, we need to be precise.
Let's compute I exactly asymptotically. I = \int_0^{1/m} \frac{(1-y)^n - 1 + n y}{y^2} dy. We can split the integral from 0 to 1 and 1 to 1/m? But 1/m < 1 since m>1. So the integration interval is [0, 1/m]. For large n, the function (1-y)^n is concentrated near y=0. We can use the substitution y = t/n. I = \int_0^{n/m} \frac{(1 - t/n)^n - 1 + t}{t^2} n dt? Wait, earlier we had: I = \int_0^{1/m} \frac{(1-y)^n - 1 + n y}{y^2} dy. Let y = t/n. Then dy = dt/n. y^2 = t^2/n^2. The integral becomes: I = \int_0^{n/m} \frac{(1 - t/n)^n - 1 + t}{t^2/n^2} \frac{dt}{n} = n \int_0^{n/m} \frac{(1 - t/n)^n - 1 + t}{t^2} dt. Now, as n -> \infty, (1 - t/n)^n -> e^{-t}. The upper limit n/m -> \infty. So we have: I = n \int_0^\infty \frac{e^{-t} - 1 + t}{t^2} dt + n \int_{n/m}^\infty \frac{e^{-t} - 1 + t}{t^2} dt + n \int_0^{n/m} \frac{(1 - t/n)^n - e^{-t}}{t^2} dt. The first integral: \int_0^\infty \frac{e^{-t} - 1 + t}{t^2} dt. Let's evaluate it. We can integrate by parts: \int_0^\infty \frac{e^{-t} - 1 + t}{t^2} dt = \left[ -\frac{e^{-t} - 1 + t}{t} \right]0^\infty + \int_0^\infty \frac{-e^{-t} + 1}{t} dt. At t=0, e^{-t} - 1 + t ~ t^2/2, so the boundary term goes to 0. At t=\infty, e^{-t} - 1 + t ~ t, so - (e^{-t} - 1 + t)/t -> -1. So the boundary term is 0 - (-1) = 1? Wait, \lim{t\to\infty} -\frac{e^{-t} - 1 + t}{t} = -1. At t=0, limit is 0. So boundary = -1. Then \int_0^\infty \frac{1 - e^{-t}}{t} dt = \gamma? Actually, \int_0^\infty \frac{1 - e^{-t}}{t} dt diverges! Wait, \int_0^A \frac{1 - e^{-t}}{t} dt = \ln A + \gamma + O(1/A). So it diverges logarithmically. But our original integral I is finite. So the decomposition into \int_0^\infty is invalid because the integral \int_0^\infty \frac{e^{-t} - 1 + t}{t^2} dt diverges. Let's check: as t -> \infty, e^{-t} - 1 + t ~ t, so integrand ~ 1/t, diverges. So we cannot extend to infinity.
We must keep the upper limit n/m. So: I = n \int_0^{n/m} \frac{(1 - t/n)^n - 1 + t}{t^2} dt. We can write (1 - t/n)^n = e^{n \ln(1 - t/n)} = e^{-t - t^2/(2n) - ...}. But the upper limit is n/m, which is large. We can split the integral at some large but fixed T, and at n/m.
Let's split: I = n \int_0^T \frac{(1 - t/n)^n - 1 + t}{t^2} dt + n \int_T^{n/m} \frac{(1 - t/n)^n - 1 + t}{t^2} dt. For the first part, as n -> \infty, (1 - t/n)^n -> e^{-t} uniformly on [0,T]. So the first integral tends to n \int_0^T \frac{e^{-t} - 1 + t}{t^2} dt. For the second part, t is large (between T and n/m). For t >> 1, e^{-t} is negligible. Also (1 - t/n)^n is exponentially small if t/n is bounded away from 0? Actually, if t = O(n), say t = cn, then (1 - c)^n is exponentially small. If t is large but t/n -> 0, then (1 - t/n)^n ~ e^{-t} which is small. So for t >= T large, both (1 - t/n)^n and e^{-t} are exponentially small in t. But we have the -1 + t terms. So the second integral is approximately n \int_T^{n/m} \frac{-1 + t}{t^2} dt = n \int_T^{n/m} \left( \frac{1}{t} - \frac{1}{t^2} \right) dt = n [ \ln t + 1/t ]_T^{n/m} = n ( \ln(n/m) - \ln T + 1/(n/m) - 1/T ) = n \ln n - n \ln m - n \ln T + m + O(1/T). So the second integral gives n \ln n - n \ln m - n \ln T + m + o(n). The first integral is n \int_0^T \frac{e^{-t} - 1 + t}{t^2} dt. Let's evaluate this integral exactly: \int_0^T \frac{e^{-t} - 1 + t}{t^2} dt = \left[ -\frac{e^{-t} - 1 + t}{t} \right]_0^T + \int_0^T \frac{1 - e^{-t}}{t} dt = -\frac{e^{-T} - 1 + T}{T} + \int_0^T \frac{1 - e^{-t}}{t} dt. As T -> \infty, this becomes 1 + \int_0^\infty \frac{1 - e^{-t}}{t} dt, but that diverges. However, we will combine with the - n \ln T from the second part. Indeed, \int_0^T \frac{1 - e^{-t}}{t} dt = \ln T + \gamma + O(e^{-T}/T). And - (e^{-T} - 1 + T)/T = -1 + O(1/T). So the first integral = -1 + \ln T + \gamma + O(1/T). Then n times the first integral = n (-1 + \ln T + \gamma) + O(1). Adding the second integral: n \ln n - n \ln m - n \ln T + m + n (-1 + \ln T + \gamma) + O(1) = n \ln n - n \ln m - n + n \gamma + m + O(1). So I = n \ln n - n (\ln m + 1 - \gamma) + m + O(1).
This matches our earlier result. The O(1) term comes from the error in approximating (1 - t/n)^n by e^{-t} in the first integral and from the upper limit being exactly n/m. We can get a more precise constant if needed.
So I = n \ln n - n (\ln m + 1 - \gamma) + m + o(n).
Now we need the corrections from the Euler-Maclaurin formula: U = \sum_{j=1}^\infty F(j) = I + \frac{1}{2} F(1) + \sum_{k=1}^\infty \frac{B_{2k}}{(2k)!} F^{(2k-1)}(1).
Let's analyze F(t) = m^t [ (1 - m^{-t})^n - 1 + n m^{-t} ]. We can write F(t) = m^t (1 - m^{-t})^n - m^t + n. At t=1: F(1) = m (1 - 1/m)^n - m + n ~ n - m + o(1). F'(t) = \ln m \cdot m^t (1 - m^{-t})^n + m^t \cdot n (1 - m^{-t})^{n-1} \cdot m^{-t} \ln m - \ln m \cdot m^t - n \ln m \cdot m^{-t}? Wait, derivative of n is 0. Let's compute carefully: F(t) = m^t (1 - m^{-t})^n - m^t + n. Let a(t) = m^t, b(t) = (1 - m^{-t})^n. a' = a \ln m. b' = n (1 - m^{-t})^{n-1} \cdot m^{-t} \ln m. So (a b)' = a' b + a b' = a \ln m b + a n (1 - m^{-t})^{n-1} m^{-t} \ln m = a \ln m [ (1 - m^{-t})^n + n m^{-t} (1 - m^{-t})^{n-1} ]. Then F'(t) = a \ln m [ (1 - m^{-t})^n + n m^{-t} (1 - m^{-t})^{n-1} ] - a \ln m. At t=1: F'(1) = m \ln m [ (1 - 1/m)^n + n (1/m) (1 - 1/m)^{n-1} ] - m \ln m. For large n, (1 - 1/m)^n is exponentially small. So F'(1) ~ - m \ln m + o(1). So it's O(1), not O(n). Similarly, higher derivatives at t=1 will be O(1). Why? Because the terms that are O(n) in F(t) come from the +n part? Wait, F(t) = m^t (1 - m^{-t})^n - m^t + n. The +n is constant, so its derivatives are 0. The -m^t gives -m^t \ln m, which is O(1). The term m^t (1 - m^{-t})^n: for large n, this is exponentially small at t=1 because (1 - 1/m)^n decays exponentially. So F(t) and its derivatives at t=1 are O(1) as n -> \infty. The O(n) term in F(1) comes from the +n, which has no derivatives. So the Euler-Maclaurin corrections beyond the 1/2 F(1) term will be O(1), not O(n). Let's verify: F(1) = n - m + o(1). So 1/2 F(1) = n/2 - m/2 + o(1). The higher derivatives: F'(t) at t=1: the term from +n is 0. The term from -m^t is -m \ln m. The term from m^t (1 - m^{-t})^n is exponentially small. So F'(1) = -m \ln m + o(1). So the B_2/2! F'(1) term is O(1). Similarly, F''(1) will be O(1). So all higher corrections are O(1). Thus U = I + \frac{1}{2} F(1) + O(1) = n \ln n - n (\ln m + 1 - \gamma) + m + \frac{1}{2}(n - m) + O(1) = n \ln n - n (\ln m + \frac{1}{2} - \gamma) + \frac{m}{2} + O(1).
But wait, is that the full asymptotic? We must check if there is any other O(n) contribution from the tail of the sum that was not captured by the integral approximation. The integral I is the integral of F(t) from 1 to \infty. The sum is the integral plus the Euler-Maclaurin corrections. We have computed the corrections up to O(1). But we must ensure that the sum \sum_{j=1}^\infty F(j) is indeed equal to I + 1/2 F(1) + ... with error O(1). The Euler-Maclaurin formula with remainder says: \sum_{j=1}^\infty F(j) = \int_1^\infty F(t) dt + \frac{1}{2} F(1) + \int_1^\infty \overline{B}_1(t) F'(t) dt. Where \overline{B}_1(t) = {t} - 1/2 is bounded. So the remainder is \int_1^\infty \overline{B}_1(t) F'(t) dt. We need to show this is O(1) as n -> \infty. We have F'(t) = \ln m [ m^t (1 - m^{-t})^n + n (1 - m^{-t})^{n-1} - m^t ]. For t >= 1, m^t >= m > 1. The term m^t (1 - m^{-t})^n: for t >= 1, m^{-t} <= 1/m < 1. So (1 - m^{-t})^n decays exponentially with n. The term n (1 - m^{-t})^{n-1} also decays exponentially unless m^{-t} is very small. But for t >= 1, m^{-t} <= 1/m. So (1 - m^{-t}) is bounded away from 1, so (1 - m^{-t})^n decays exponentially. The only non-exponentially small part is - m^t. So F'(t) ~ - m^t \ln m, which is O(1) (does not grow with n). Wait, -m^t is independent of n. So F'(t) is O(1) uniformly in n for t >= 1? Let's check: m^t (1 - m^{-t})^n is at most m^t (1 - 1/m)^n, which is exponentially small. n (1 - m^{-t})^{n-1} is at most n (1 - 1/m)^{n-1}, also exponentially small. So indeed, F'(t) = - m^t \ln m + exponentially small terms. So F'(t) is O(1) uniformly in n and t. Then the remainder integral \int_1^\infty \overline{B}_1(t) F'(t) dt converges and is O(1) independent of n. So the Euler-Maclaurin expansion with the first correction gives an error O(1). The higher Bernoulli terms would also be O(1) because higher derivatives of the exponentially small parts are also exponentially small? Actually, the derivatives of the -m^t part give -m^t (\ln m)^k, which are O(1). The derivatives of the exponentially small parts remain exponentially small. So all corrections beyond 1/2 F(1) are O(1). So we have: U = I + \frac{1}{2} F(1) + C + o(1) where C is some constant (the sum of all higher Bernoulli corrections). But we don't know C exactly unless we compute it.
But wait, we have an exact expression for U in terms of I and F(1)? No, the Euler-Maclaurin formula is exact if we include all terms, but the sum of all corrections is exactly the sum of the series of Bernoulli numbers. The constant C might be expressible in terms of the function F. However, the problem likely expects an asymptotic expansion up to O(1), maybe including a periodic term? But we didn't see any periodic term. Let's re-examine.
We had U = \sum_{j=1}^\infty F(j) with F(t) = m^t [ (1 - m^{-t})^n - 1 + n m^{-t} ]. We approximated F(t) by something? No, we applied Euler-Maclaurin directly to F(t). That is exact for the sum, assuming F and its derivatives decay at infinity. The only approximation we made was in evaluating I and F(1). We got I = n \ln n - n (\ln m + 1 - \gamma) + m + o(n)? Actually, we need to be more precise: I is exactly the integral. We computed the asymptotic of I up to O(1). We got I = n \ln n - n (\ln m + 1 - \gamma) + m + O(1). The O(1) term in I might be a constant that we can compute. Similarly, F(1) = n - m + m (1 - 1/m)^n = n - m + O(e^{-c n}). So 1/2 F(1) = n/2 - m/2 + O(1). Then U = n \ln n - n (\ln m + 1 - \gamma) + m + n/2 - m/2 + C + o(1) = n \ln n - n (\ln m + 1/2 - \gamma) + m/2 + C + o(1).
But is there a periodic function of n? In our analysis, the integral I and F(1) are smooth functions of n. The sum U is exactly the sum over j. We used Euler-Maclaurin which gives an exact identity: \sum_{j=1}^\infty F(j) = \int_1^\infty F(t) dt + \frac{1}{2} F(1) + \sum_{k=1}^\infty \frac{B_{2k}}{(2k)!} F^{(2k-1)}(1). This is exact, provided the series converges. The sum of the series is the constant C. There is no periodic term because the Bernoulli polynomials evaluated at integer points don't introduce periodicity in n? Wait, the Euler-Maclaurin formula is for a fixed function F. Here F depends on n. The formula holds for each n. The right-hand side is a function of n. We are approximating it as n -> \infty. The integral I and the derivatives at 1 are all functions of n. We expanded them asymptotically. The asymptotic expansion of I is a power series in n? We found I = n \ln n + A n + B + o(1). The derivatives at 1 give terms like F(1) = n + C, F'(1) = D, etc. So the asymptotic expansion of U is a series in powers of n? But there is no periodic function of \log_m n? That seems surprising because sums of the form \sum_j f(n/m^j) often produce periodic functions. Let's test with a simple case: m=2. Then U_{2n} = \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{1}{2^{k-1} - 1}. Is this sum expressible as n \log_2 n + n (\text{constant}) + O(1)? Or does it have a periodic component? Let's compute U_{2n} for small n to see if there's a periodic fluctuation. n=2: sum_{k=2}^2 C(2,2)(-1)^2 / (2^{1}-1) = 1 / 1 = 1. n=3: k=2: C(3,2)=3, 1/(2-1)=1, sign + -> 3. k=3: C(3,3)=1, sign -, 1/(4-1)=1/3 -> -1/3. Sum = 3 - 1/3 = 8/3 ≈ 2.6667. n=4: k=2: C(4,2)=6, /1 =6. k=3: C(4,3)=4, /3 =4/3, sign - -> -4/3. k=4: C(4,4)=1, /(8-1)=1/7, sign + -> 1/7. Sum = 6 - 4/3 + 1/7 = 6 - 1.3333 + 0.1429 = 4.8095. n=5: k=2: C(5,2)=10. k=3: C(5,3)=10, /3 =3.3333, sign - -> -3.3333. k=4: C(5,4)=5, /7=0.7143, sign + -> 0.7143. k=5: C(5,5)=1, /(16-1)=1/15=0.06667, sign - -> -0.06667. Sum = 10 - 3.3333 + 0.7143 - 0.0667 = 7.3143. n=6: k=2:15; k=3:20/3=6.6667; k=4:15/7=2.1429; k=5:6/15=0.4; k=6:1/31=0.03226. Sum = 15 - 6.6667 + 2.1429 - 0.4 + 0.0323 = 10.1085. Let's compute n log_2 n: n=2: 21=2 n=3: 31.585=4.755 n=4: 42=8 n=5: 52.322=11.61 n=6: 62.585=15.51 Our sums are much smaller. So maybe the leading term is not n log n? Wait, our computed sums: 1, 2.67, 4.81, 7.31, 10.11. These are roughly linear in n? n=2 ->1, n=3->2.67, n=4->4.81, n=5->7.31, n=6->10.11. The differences: 1.67, 2.14, 2.5, 2.8. The second differences are about 0.4-0.5. This looks like quadratic? But n log n is superlinear. Our sums are growing slower than n log n. Wait, my manual calculation might be wrong? Let's recompute U_{2n} carefully. U_{mn} = sum_{k=2}^n C(n,k) (-1)^k / (m^{k-1} - 1). For m=2, denominator = 2^{k-1} - 1. k=2: 1/(2-1)=1 k=3: 1/(4-1)=1/3 k=4: 1/(8-1)=1/7 k=5: 1/15 k=6: 1/31 k=7: 1/63 etc. n=2: C(2,2)=1, +1 = 1. n=3: C(3,2)=3 (+), C(3,3)=1 (-) * 1/3 = -1/3. Sum = 3 - 1/3 = 8/3 ≈ 2.6667. n=4: C(4,2)=6 (+), C(4,3)=4 (-) * 1/3 = -4/3, C(4,4)=1 (+) * 1/7 = 1/7. Sum = 6 - 1.3333 + 0.1429 = 4.8095. n=5: C(5,2)=10 (+), C(5,3)=10 (-) * 1/3 = -3.3333, C(5,4)=5 (+) * 1/7 = 0.7143, C(5,5)=1 (-) * 1/15 = -0.06667. Sum = 10 - 3.3333 + 0.7143 - 0.0667 = 7.3143. n=6: C(6,2)=15 (+), C(6,3)=20 (-) * 1/3 = -6.6667, C(6,4)=15 (+) * 1/7 = 2.1429, C(6,5)=6 (-) * 1/15 = -0.4, C(6,6)=1 (+) * 1/31 = 0.03226. Sum = 15 - 6.6667 + 2.1429 - 0.4 + 0.0323 = 10.1085. n=7: C(7,2)=21, C(7,3)=35 (-) * 1/3 = -11.6667, C(7,4)=35 (+) * 1/7 = 5, C(7,5)=21 (-) * 1/15 = -1.4, C(7,6)=7 (+) * 1/31 = 0.2258, C(7,7)=1 (-) * 1/63 = -0.01587. Sum = 21 - 11.6667 + 5 - 1.4 + 0.2258 - 0.0159 = 13.143. These values: 1, 2.67, 4.81, 7.31, 10.11, 13.14. This is roughly linear? n=7 gives 13.14. n=2 gives 1. The ratio U/n: 0.5, 0.89, 1.20, 1.46, 1.68, 1.88. It seems to be growing logarithmically? Actually, U/n seems to be about 0.27 * n? No, U grows about 3 per step. Let's compute U/n: n=10? Not computed. But the values suggest U ~ something like n \log n? For n=10, n log2 n = 103.32=33.2. Our U at n=7 is 13.1. If it were n log n, it would be much larger. Maybe the leading term is n \ln n? n=7, ln 7=1.946, n ln n=13.6. That's close to 13.14! n=6: 61.79=10.75, we have 10.11. n=5: 51.61=8.05, we have 7.31. n=4: 41.39=5.55, we have 4.81. n=3: 31.10=3.30, we have 2.67. n=2: 20.69=1.39, we have 1. So U is roughly n ln n - something? n ln n - n? n=7: 13.6 - 7 = 6.6, too low. n ln n - 0.5 n? 13.6 - 3.5 = 10.1, still low. n ln n - 0.2 n? 13.6 - 1.4 = 12.2, still low. Actually, U is less than n ln n. The ratio U/(n ln n) for n=7 is 13.14/13.6=0.966. For n=6: 10.11/10.75=0.94. For n=5: 7.31/8.05=0.91. For n=4: 4.81/5.55=0.87. It's increasing. Maybe U ~ n ln n - n (something) + ...? But our earlier analysis gave U ~ n \ln n - n (\ln m + 1/2 - \gamma) + ... For m=2, \ln m = \ln 2 ≈ 0.693. \gamma ≈ 0.577. So \ln m + 1/2 - \gamma = 0.693 + 0.5 - 0.577 = 0.616. So U ~ n \ln n - 0.616 n + ... Let's test: n=7: n ln n = 13.62; -0.6167 = -4.31; sum = 9.31. Too low. Our computed U=13.14. So maybe the constant term is positive? 13.62 - 0.6167 = 9.3, plus something to get 13.14? That would require +3.8. The constant m/2 + C? m=2 gives 1 + C. So C would be ~2.8. That's possible. But the difference is large. Let's check n=10 with our asymptotic: n ln n = 23.03; -0.61610 = -6.16; sum = 16.87. If U(10) is around 16-17, that might be plausible. But we need to check if U_{2n} is indeed ~ n ln n.
Wait, our manual calculation for n=7 gave U=13.14. But n ln n = 13.62. So U is slightly less than n ln n. For n=7, U/(n ln n) = 0.965. For n=100, what would it be? We can try to compute U_{2n} using the series representation: U = \sum_{j=1}^\infty 2^j [ (1 - 2^{-j})^n - 1 + n 2^{-j} ]. For large n, the sum is dominated by j around log2 n. Let's estimate U for n=7 using this series: n=7. j=1: 2 * [ (1-1/2)^7 - 1 + 7/2 ] = 2 * [ (1/2)^7 - 1 + 3.5 ] = 2 * [ 0.0078125 + 2.5 ] = 5.015625 j=2: 4 * [ (1-1/4)^7 - 1 + 7/4 ] = 4 * [ (3/4)^7 - 1 + 1.75 ] = 4 * [ 0.13348 - 1 + 1.75 ] = 4 * 0.88348 = 3.5339 j=3: 8 * [ (1-1/8)^7 - 1 + 7/8 ] = 8 * [ (7/8)^7 - 1 + 0.875 ] = 8 * [ 0.3927 - 1 + 0.875 ] = 8 * 0.2677 = 2.1416 j=4: 16 * [ (1-1/16)^7 - 1 + 7/16 ] = 16 * [ (15/16)^7 - 1 + 0.4375 ] = 16 * [ 0.645 - 1 + 0.4375 ] = 16 * 0.0825 = 1.32 j=5: 32 * [ (1-1/32)^7 - 1 + 7/32 ] = 32 * [ (31/32)^7 - 1 + 0.21875 ] = 32 * [ 0.808 - 1 + 0.21875 ] = 32 * 0.02675 = 0.856 j=6: 64 * [ (1-1/64)^7 - 1 + 7/64 ] = 64 * [ (63/64)^7 - 1 + 0.109375 ] = 64 * [ 0.898 - 1 + 0.109375 ] = 64 * 0.007375 = 0.472 j=7: 128 * [ ... ] = 128 * [ (127/128)^7 - 1 + 7/128 ] ≈ 128 * [ e^{-7/128} - 1 + 0.0547 ] ≈ 128 * [ 0.947 - 1 + 0.0547 ] = 128 * 0.0017 = 0.2176 j=8: 256 * [ ... ] ≈ 256 * [ e^{-7/256} - 1 + 0.0273 ] ≈ 256 * [ 0.973 - 1 + 0.0273 ] = 256 * 0.0003 = 0.0768 j=9: 512 * [ ... ] ≈ 512 * [ e^{-7/512} - 1 + 0.0137 ] ≈ 512 * [ 0.986 - 1 + 0.0137 ] = 512 * -0.0003 = -0.15? Wait, e^{-7/512} ≈ 1 - 7/512 + (7/512)^2/2. So e^{-x} - 1 + x ≈ x^2/2. So term ≈ 512 * (7/512)^2 / 2 = 49/(2*512) ≈ 0.048. Positive. Summing: 5.0156 + 3.5339 = 8.5495; +2.1416 = 10.6911; +1.32 = 12.0111; +0.856 = 12.8671; +0.472 = 13.3391; +0.2176 = 13.5567; +0.0768 = 13.6335; +0.048 = 13.6815; etc. This sum is approaching something around 13.7? But our earlier sum from k=2..7 gave 13.14. There's a discrepancy! Let's check the series sum carefully.
U = \sum_{j=1}^\infty m^j [ (1 - m^{-j})^n - 1 + n m^{-j} ]. For n=7, m=2. j=1: 2 * [ (1/2)^7 - 1 + 7/2 ] = 2 * [ 1/128 - 1 + 3.5 ] = 2 * [ 0.0078125 + 2.5 ] = 2 * 2.5078125 = 5.015625. OK. j=2: 4 * [ (3/4)^7 - 1 + 7/4 ]. (3/4)^7 = 2187/16384 ≈ 0.1334839. 7/4 = 1.75. So bracket = 0.1334839 - 1 + 1.75 = 0.8834839. Times 4 = 3.5339356. OK. j=3: 8 * [ (7/8)^7 - 1 + 7/8 ]. (7/8)^7 = 823543 / 2097152 ≈ 0.392695. 7/8 = 0.875. Bracket = 0.392695 - 1 + 0.875 = 0.267695. Times 8 = 2.14156. OK. j=4: 16 * [ (15/16)^7 - 1 + 7/16 ]. (15/16)^7 = 170859375 / 268435456 ≈ 0.63668? Wait, compute: 15/16 = 0.9375. 0.9375^7 = ? 0.9375^2 = 0.8789 0.9375^4 = 0.7725 0.9375^7 = 0.7725 * 0.8789 * 0.9375 ≈ 0.6366. Let's calculate exactly: (15/16)^7 = 15^7 / 16^7. 15^7 = 170859375. 16^7 = 268435456. Ratio = 0.63668. 7/16 = 0.4375. Bracket = 0.63668 - 1 + 0.4375 = 0.07418. Times 16 = 1.1869. Earlier I had 1.32. Let's recalc: 0.63668 - 1 = -0.36332. +0.4375 = 0.07418. 16 = 1.1869. OK. j=5: 32 * [ (31/32)^7 - 1 + 7/32 ]. 31/32 = 0.96875. (0.96875)^7 ≈ ? 0.96875^2 = 0.938476 0.96875^4 = 0.880738 0.96875^7 = 0.880738 * 0.938476 * 0.96875 ≈ 0.8007? Let's do exact: 31^7 = 27512614111? Too big. Approx: e^{-7/32} = e^{-0.21875} = 0.8035. So bracket ≈ 0.8035 - 1 + 0.21875 = 0.02225. Times 32 = 0.712. Earlier I had 0.856. Let's compute more precisely: (1 - 1/32)^7 = sum_{k=0}^7 C(7,k) (-1/32)^k. But e^{-7/32} is a good approx. e^{-0.21875} = 0.8035. 7/32=0.21875. So bracket = 0.8035 - 1 + 0.21875 = 0.02225. 32 = 0.712. j=6: 64 * [ (63/64)^7 - 1 + 7/64 ]. e^{-7/64}= e^{-0.109375} = 0.8964. bracket = 0.8964 - 1 + 0.109375 = 0.005775. 64 = 0.3696. j=7: 128 * [ e^{-7/128} - 1 + 7/128 ]. e^{-0.0546875} = 0.9468. bracket = 0.9468 - 1 + 0.0546875 = 0.0014875. 128 = 0.1904. j=8: 256 * [ e^{-7/256} - 1 + 7/256 ]. e^{-0.02734} = 0.9730. bracket = 0.9730 - 1 + 0.02734 = 0.00034. 256 = 0.087. j=9: 512 * [ e^{-7/512} - 1 + 7/512 ]. e^{-0.01367} = 0.9864. bracket = 0.9864 - 1 + 0.01367 = 0.00007. 512 = 0.0358. Sum: 5.0156 + 3.5339 = 8.5495; +2.1416 = 10.6911; +1.1869 = 11.878; +0.712 = 12.59; +0.3696 = 12.9596; +0.1904 = 13.15; +0.087 = 13.237; +0.0358 = 13.273; ... This sum is converging to about 13.3. Our earlier sum from k=2..7 gave 13.143. There's a slight discrepancy due to rounding? Let's compute the k-sum exactly for n=7: C(7,2)=21 C(7,3)=35 C(7,4)=35 C(7,5)=21 C(7,6)=7 C(7,7)=1 Denominators: 2^{1}-1=1; 2^2-1=3; 2^3-1=7; 2^4-1=15; 2^5-1=31; 2^6-1=63. Sum = 21/1 - 35/3 + 35/7 - 21/15 + 7/31 - 1/63. Compute exactly: 21 = 21 -35/3 = -11.6666667 35/7 = 5 -21/15 = -1.4 7/31 ≈ 0.22580645 -1/63 ≈ -0.015873 Sum = 21 - 11.6666667 = 9.3333333; +5 = 14.3333333; -1.4 = 12.9333333; +0.22580645 = 13.15913975; -0.015873 = 13.14326675. So U = 13.14326675. Our j-sum gave 13.273 and still increasing slowly? Let's sum more accurately. j=1: 2(1/128 - 1 + 3.5) = 2(2.5078125) = 5.015625 j=2: 4(2187/16384 - 1 + 1.75) = 4(0.1334839 - 1 + 1.75) = 40.8834839 = 3.5339356 j=3: 8(823543/2097152 - 1 + 0.875) = 8*(0.392695 - 1 + 0.875) = 80.267695 = 2.14156 j=4: 16(15^7/16^7 - 1 + 7/16). 15^7=170859375, 16^7=268435456. Ratio = 170859375/268435456 = 0.6366825. Bracket = 0.6366825 - 1 + 0.4375 = 0.0741825. 16 = 1.18692. j=5: 32(31^7/32^7 - 1 + 7/32). 31/32 = 0.96875. 0.96875^7 = ? Compute exactly: (31/32)^7 = 31^7 / 32^7. 31^2=961, 31^3=29791, 31^4=923521, 31^5=28629151, 31^6=887503681, 31^7=27512614111. 32^7 = 2^35 = 34359738368. Ratio = 27512614111 / 34359738368 = 0.800672. 7/32 = 0.21875. Bracket = 0.800672 - 1 + 0.21875 = 0.019422. 32 = 0.6215. j=6: 64(63/64)^7. (63/64)^7 = 63^7 / 64^7. 63^2=3969, 63^3=250047, 63^4=15752961, 63^5=992436543, 63^6=62523502209, 63^7=3938980639167. 64^7 = 2^42 = 4398046511104. Ratio = 3938980639167 / 4398046511104 = 0.89564. 7/64 = 0.109375. Bracket = 0.89564 - 1 + 0.109375 = 0.005015. 64 = 0.32096. j=7: 128(127/128)^7. 127/128 = 0.9921875. (0.9921875)^7 = e^{7 ln(0.9921875)} ≈ e^{-7/128 - 7/(2*128^2)} ≈ e^{-0.0546875 - 0.000214} = 0.9468. Better: 127^7 / 128^7. 127^7 = ? Use e^{-7/128} = 0.94676. 7/128 = 0.0546875. Bracket = 0.94676 - 1 + 0.0546875 = 0.0014475. 128 = 0.18528. j=8: 256(255/256)^7. 255/256 = 0.99609375. e^{-7/256} = 0.9730. 7/256 = 0.02734375. Bracket = 0.9730 - 1 + 0.02734 = 0.00034375? Actually e^{-7/256} = 0.97304. -1 + 0.02734 = 0.00038. 256 = 0.097. j=9: 512(511/512)^7. e^{-7/512} = 0.9864. 7/512 = 0.013671875. Bracket = 0.9864 - 1 + 0.01367 = 0.00007. *512 = 0.0358. Sum: 5.015625 + 3.5339356 = 8.5495606 +2.14156 = 10.6911206 +1.18692 = 11.8780406 +0.6215 = 12.4995406 +0.32096 = 12.8205006 +0.18528 = 13.0057806 +0.097 = 13.1027806 +0.0358 = 13.1385806 +... seems to be converging to ~13.143. Good! So the series matches.
Now, the asymptotic behavior: For n=7, U=13.14. n ln n = 71.9459=13.621. n ln n - n (ln 2 + 1/2 - \gamma) = 13.621 - 7(0.693+0.5-0.577) = 13.621 - 7*0.616 = 13.621 - 4.312 = 9.309. That's way off. So my earlier analysis must be wrong.
Let's re-evaluate the integral I and the Euler-Maclaurin corrections. I had: U = \sum_{j=1}^\infty F(j) with F(t) = m^t [ (1 - m^{-t})^n - 1 + n m^{-t} ]. I = \int_1^\infty F(t) dt. I computed I = n \ln n - n (\ln m + 1 - \gamma) + m + O(1). Then F(1) = m (1 - 1/m)^n - m + n ~ n - m. So I + 1/2 F(1) = n \ln n - n (\ln m + 1 - \gamma) + m + n/2 - m/2 + O(1) = n \ln n - n (\ln m + 1/2 - \gamma) + m/2 + O(1). For m=2, \ln m = \ln 2 ≈ 0.693, \gamma ≈ 0.577, so \ln m + 1/2 - \gamma = 0.693 + 0.5 - 0.577 = 0.616. Then U ≈ n ln n - 0.616 n + 1 + O(1)? For n=7: 13.62 - 4.31 + 1 = 10.31, but actual is 13.14. So the O(1) term is not O(1); it's about 2.8. But wait, the O(1) term is constant as n grows? For n=6: n ln n = 10.75; -0.616*6 = -3.696; sum = 7.05; +1 = 8.05, but actual U=10.11. Difference ~2.06. For n=5: 8.05 - 3.08 = 4.97; +1=5.97, actual 7.31, diff 1.34. For n=4: 5.55 - 2.464 = 3.086; +1=4.086, actual 4.81, diff 0.72. For n=3: 3.30 - 1.848 = 1.452; +1=2.452, actual 2.67, diff 0.22. For n=2: 1.39 - 1.232 = 0.158; +1=1.158, actual 1, diff -0.16. The difference seems to be growing with n? It went from -0.16 to 2.8. That suggests the missing term is not O(1) but something like n * (something) or log n * something? But we already accounted for the n term. Let's check the coefficient of n. Our asymptotic gave n ln n - 0.616 n. For n=7, that's 9.3. Actual is 13.14. So the coefficient of n is not -0.616; it's something else. Maybe the integral I was miscalculated.
Let's recompute I carefully. I = \int_1^\infty F(t) dt, with F(t) = m^t [ (1 - m^{-t})^n - 1 + n m^{-t} ]. Let x = m^t. Then t = \log_m x, dt = dx/(x \ln m). When t=1, x=m. When t=\infty, x=\infty. I = \int_m^\infty x [ (1 - 1/x)^n - 1 + n/x ] \frac{dx}{x \ln m} = \frac{1}{\ln m} \int_m^\infty [ (1 - 1/x)^n - 1 + n/x ] dx. Now, let y = 1/x. Then x = 1/y, dx = -dy/y^2. Limits: x=m -> y=1/m; x=\infty -> y=0. I = \frac{1}{\ln m} \int_0^{1/m} [ (1 - y)^n - 1 + n y ] \frac{dy}{y^2}. This is correct.
Now evaluate I = \frac{1}{\ln m} \int_0^{1/m} \frac{(1-y)^n - 1 + n y}{y^2} dy. We can write this as: I = \frac{1}{\ln m} \int_0^{1/m} \frac{(1-y)^n - e^{-n y} + e^{-n y} - 1 + n y}{y^2} dy. The integral of (e^{-n y} - 1 + n y)/y^2 from 0 to 1/m can be computed exactly: \int_0^{1/m} \frac{e^{-n y} - 1 + n y}{y^2} dy. Let t = n y. Then dy = dt/n, y^2 = t^2/n^2. The integral becomes: \int_0^{n/m} \frac{e^{-t} - 1 + t}{t^2} n dt = n \int_0^{n/m} \frac{e^{-t} - 1 + t}{t^2} dt. We need the asymptotic of this as n -> \infty. As we did, split at T: \int_0^T \frac{e^{-t} - 1 + t}{t^2} dt = - \frac{e^{-T} - 1 + T}{T} + \int_0^T \frac{1 - e^{-t}}{t} dt. For large T, this is -1 + \ln T + \gamma + O(1/T). The integral from T to n/m: \int_T^{n/m} \frac{e^{-t} - 1 + t}{t^2} dt = \int_T^{n/m} \left( \frac{1}{t} - \frac{1}{t^2} \right) dt + \int_T^{n/m} \frac{e^{-t}}{t^2} dt. The first part = [ \ln t + 1/t ]_T^{n/m} = \ln(n/m) - \ln T + m/n - 1/T. The second part is \int_T^{n/m} \frac{e^{-t}}{t^2} dt, which is O(1/T^2) and tends to a constant as T->\infty? Actually, \int_T^\infty e^{-t}/t^2 dt = O(e^{-T}/T^2). So negligible. So the sum of the two parts from T to n/m is \ln(n/m) - \ln T + m/n - 1/T. Adding the first part: -1 + \ln T + \gamma + \ln(n/m) - \ln T + m/n - 1/T + O(1/T) = \ln n - \ln m - 1 + \gamma + m/n + O(1/T). As T->\infty, the O(1/T) terms vanish. So the integral \int_0^{n/m} \frac{e^{-t} - 1 + t}{t^2} dt = \ln n - \ln m - 1 + \gamma + o(1). Wait, we have m/n term, which goes to 0. So the integral is \ln n - \ln m - 1 + \gamma + o(1). Then n times this is n \ln n - n \ln m - n + n \gamma + o(n). So the + o(n). Thus I = \frac{1}{\ln m} [ n \ln n - n \ln m - n + n \gamma ] + \text{corrections from the other part} + \frac{1}{\ln m} \int_0^{1/m} \frac{(1-y)^n - e^{-n y}}{y^2} dy.
Now, the correction part: J = \int_0^{1/m} \frac{(1-y)^n - e^{-n y}}{y^2} dy. We need the asymptotic of this as n -> \infty. Note that (1-y)^n = e^{n \ln(1-y)} = e^{-n y - n y^2/2 - n y^3/3 - ...}. So (1-y)^n - e^{-n y} = e^{-n y} ( e^{-n y^2/2 - ...} - 1 ) = - e^{-n y} ( n y^2/2 + O(n y^3) ) for small y. For y of order 1/n, n y^2 is small, so the difference is small. For larger y, e^{-n y} is very small, so the difference is small. So J should be o(1)? Or O(1/n)? Let's check. We can bound |J| <= \int_0^{1/m} \frac{ e^{-n y} | e^{-n y^2/2 - ...} - 1 | }{y^2} dy. For y <= 1/\sqrt{n}, n y^2 is bounded. The difference is O(n y^2). Then integrand is O(n). The integral over [0, 1/\sqrt{n}] is O(n * (1/\sqrt{n})) = O(\sqrt{n}). For y > 1/\sqrt{n}, e^{-n y} is exponentially small, so integral is negligible. So J could be O(\sqrt{n})? That would be larger than O(1)! Let's check: If J = O(\sqrt{n}), then I would have an extra term of order \sqrt{n} / \ln m? But our manual calculations for n up to 7 didn't show a \sqrt{n} term? The differences between U and n ln n - 0.616 n were: for n=2: -0.16; n=3: 0.22; n=4: 0.72; n=5: 1.34; n=6: 2.06; n=7: 2.8. These differences are increasing roughly linearly? 0.22, 0.72, 1.34, 2.06, 2.8. The increments are about 0.5, 0.6, 0.7, 0.7. This suggests the missing term is proportional to n, not \sqrt{n}. So J must be O(n) or something that combines with other terms to give an n term. But we already accounted for the n term from the e^{-t} integral. Let's re-examine the expansion of (1-y)^n.
We have I = \frac{1}{\ln m} \int_0^{1/m} \frac{(1-y)^n - 1 + n y}{y^2} dy. We split it as \frac{1}{\ln m} [ \int_0^{1/m} \frac{(1-y)^n - e^{-n y}}{y^2} dy + \int_0^{1/m} \frac{e^{-n y} - 1 + n y}{y^2} dy ]. The second integral we computed as n \ln n - n \ln m - n + n \gamma + o(n) (times 1/\ln m? Wait, we had I = \frac{1}{\ln m} times the integral. The integral we called I_y = \int_0^{1/m} ... dy. We computed \int_0^{1/m} \frac{e^{-n y} - 1 + n y}{y^2} dy = n \ln n - n \ln m - n + n \gamma + o(n)? Let's re-evaluate carefully.
Let I2 = \int_0^{1/m} \frac{e^{-n y} - 1 + n y}{y^2} dy. Substitute t = n y: dy = dt/n, y = t/n. Limits: y=0 -> t=0; y=1/m -> t = n/m. I2 = \int_0^{n/m} \frac{e^{-t} - 1 + t}{t^2/n^2} \frac{dt}{n} = n \int_0^{n/m} \frac{e^{-t} - 1 + t}{t^2} dt. Now, \int_0^{n/m} \frac{e^{-t} - 1 + t}{t^2} dt. We can write this as: \int_0^{n/m} \frac{e^{-t} - 1}{t^2} dt + \int_0^{n/m} \frac{t}{t^2} dt. The second integral is \int_0^{n/m} \frac{dt}{t} = \ln(n/m) - \lim_{\epsilon\to 0} \ln \epsilon. This diverges! But the first integral also diverges at 0. We must combine them. As t->0, e^{-t} - 1 + t = t^2/2 - t^3/6 + ..., so the integrand is 1/2 - t/6 + ..., which is integrable at 0. So the integral is convergent. So we cannot split it as 1/t^2 + 1/t separately. We must keep them together.
Let's compute I2 exactly using the antiderivative. We had earlier: \int \frac{e^{-t} - 1 + t}{t^2} dt = -\frac{e^{-t} - 1 + t}{t} + \int \frac{1 - e^{-t}}{t} dt. So I2 = n \left[ -\frac{e^{-t} - 1 + t}{t} \bigg|0^{n/m} + \int_0^{n/m} \frac{1 - e^{-t}}{t} dt \right]. At t=0, the limit of \frac{e^{-t} - 1 + t}{t} is 0 (since e^{-t} - 1 + t ~ t^2/2). At t = n/m, \frac{e^{-n/m} - 1 + n/m}{n/m} = \frac{m}{n} ( e^{-n/m} - 1 + n/m ). So I2 = n \left[ - \frac{m}{n} ( e^{-n/m} - 1 + n/m ) + \int_0^{n/m} \frac{1 - e^{-t}}{t} dt \right] = - m ( e^{-n/m} - 1 + n/m ) + n \int_0^{n/m} \frac{1 - e^{-t}}{t} dt. As n -> \infty, e^{-n/m} is exponentially small. So -m( -1 + n/m ) = m - n. And \int_0^{n/m} \frac{1 - e^{-t}}{t} dt = \ln(n/m) + \gamma + O(1/(n/m))? Actually, \int_0^X \frac{1 - e^{-t}}{t} dt = \ln X + \gamma + E_1(X)? Wait, the exponential integral E_1(X) = \int_X^\infty \frac{e^{-t}}{t} dt. Then \int_0^X \frac{1 - e^{-t}}{t} dt = \int_0^X \frac{dt}{t} - \int_0^X \frac{e^{-t}}{t} dt. The first part diverges. We know that \int_0^X \frac{e^{-t}}{t} dt = \gamma + \ln X + \int_0^X \frac{e^{-t}-1}{t} dt + \int_X^\infty \frac{e^{-t}}{t} dt? Actually, the standard result: \int_0^X \frac{1 - e^{-t}}{t} dt = \ln X + \gamma + O(1/X). Let's verify: \int_0^\infty \frac{e^{-t} \ln t}{?} No. We have \int_0^X \frac{1 - e^{-t}}{t} dt = \int_0^X \sum{k=1}^\infty \frac{(-1)^{k-1} t^{k-1}}{k!} dt = \sum_{k=1}^\infty \frac{(-1)^{k-1} X^k}{k \cdot k!}. This doesn't directly give \ln X + \gamma. But we know that \int_0^X \frac{1 - e^{-t}}{t} dt = \ln X + \gamma - \int_X^\infty \frac{e^{-t}}{t} dt? Let's check: The exponential integral Ei(x) = \int_{-\infty}^x \frac{e^t}{t} dt? Not that. Actually, \int_0^X \frac{1 - e^{-t}}{t} dt = \ln X + \gamma - \Gamma(0, X)? The incomplete gamma function. Standard identity: \int_0^X \frac{1 - e^{-t}}{t} dt = \ln X + \gamma + \int_0^X \frac{e^{-t} - 1}{t} dt? That's circular. Better: \int_0^\infty \frac{e^{-t} - 1}{t} dt = -\gamma. So \int_0^X \frac{1 - e^{-t}}{t} dt = \int_0^\infty \frac{1 - e^{-t}}{t} dt - \int_X^\infty \frac{1 - e^{-t}}{t} dt. But \int_0^\infty \frac{1 - e^{-t}}{t} dt diverges! Wait, \int_0^\infty \frac{1 - e^{-t}}{t} dt is not convergent at infinity because 1/t diverges. So that's not the way.
Let's compute \int_0^X \frac{1 - e^{-t}}{t} dt by splitting at 1: \int_0^1 \frac{1 - e^{-t}}{t} dt + \int_1^X \frac{1 - e^{-t}}{t} dt. The second integral is \int_1^X \frac{dt}{t} - \int_1^X \frac{e^{-t}}{t} dt = \ln X - \int_1^X \frac{e^{-t}}{t} dt. As X -> \infty, \int_1^\infty \frac{e^{-t}}{t} dt converges to a constant (E_1(1)). So \int_0^X \frac{1 - e^{-t}}{t} dt = \ln X + C + o(1) where C = \int_0^1 \frac{1 - e^{-t}}{t} dt - \int_1^\infty \frac{e^{-t}}{t} dt. We can compute C. \int_0^1 \frac{1 - e^{-t}}{t} dt = \sum_{k=1}^\infty \frac{(-1)^{k-1}}{k \cdot k!}. \int_1^\infty \frac{e^{-t}}{t} dt = E_1(1). Is this equal to \gamma? Let's check known identity: \gamma = \int_0^1 \frac{1 - e^{-t}}{t} dt - \int_1^\infty \frac{e^{-t}}{t} dt. Yes, that's a known representation of the Euler-Mascheroni constant. So \int_0^X \frac{1 - e^{-t}}{t} dt = \ln X + \gamma + O(1/X). Thus I2 = -m(-1 + n/m) + n ( \ln(n/m) + \gamma ) + o(n) = m - n + n \ln n - n \ln m + n \gamma + o(n). So I2 = n \ln n - n (\ln m + 1 - \gamma) + m + o(n).
This is exactly what we had for I? Wait, I = \frac{1}{\ln m} \int_0^{1/m} \frac{(1-y)^n - 1 + n y}{y^2} dy. We just computed I2 = \int_0^{1/m} \frac{e^{-n y} - 1 + n y}{y^2} dy? No, I2 was \int_0^{1/m} \frac{e^{-n y} - 1 + n y}{y^2} dy. We found I2 = n \ln n - n (\ln m + 1 - \gamma) + m + o(n). But our I is the same integral with e^{-n y} replaced by (1-y)^n. So I = I2 + \int_0^{1/m} \frac{(1-y)^n - e^{-n y}}{y^2} dy. Let I3 = \int_0^{1/m} \frac{(1-y)^n - e^{-n y}}{y^2} dy. We need the asymptotic of I3. (1-y)^n = e^{n \ln(1-y)} = e^{-n y - n y^2/2 - n y^3/3 - ...}. So (1-y)^n - e^{-n y} = e^{-n y} ( e^{-n y^2/2 - n y^3/3 - ...} - 1 ). For y small, n y^2 is small. We can expand: e^{-n y^2/2 - ...} - 1 = - n y^2/2 - n y^3/3 + \frac{1}{2} n^2 y^4/4 + ... So (1-y)^n - e^{-n y} = e^{-n y} ( - n y^2/2 + O(n y^3 + n^2 y^4) ). Then the integrand is e^{-n y} ( - n/2 + O(n y + n^2 y^2) ). So I3 = \int_0^{1/m} e^{-n y} ( - n/2 + O(n y + n^2 y^2) ) dy. = - \frac{n}{2} \int_0^{1/m} e^{-n y} dy + O( \int_0^{1/m} e^{-n y} (n y + n^2 y^2) dy ). The first integral: \int_0^{1/m} e^{-n y} dy = \frac{1}{n} (1 - e^{-n/m}) = \frac{1}{n} + o(1/n). So - \frac{n}{2} * \frac{1}{n} = -1/2 + o(1). The O terms: \int_0^{1/m} e^{-n y} n y dy = \frac{1}{n} \int_0^{n/m} e^{-t} t dt = O(1/n). \int_0^{1/m} e^{-n y} n^2 y^2 dy = \frac{1}{n} \int_0^{n/m} e^{-t} t^2 dt = O(1/n). So I3 = -1/2 + O(1/n). Wait! I3 is O(1), not O(n) or O(\sqrt{n}). This is a crucial correction! The integral I is I2 + I3 = n \ln n - n (\ln m + 1 - \gamma) + m - 1/2 + o(1). Then I = n \ln n - n (\ln m + 1 - \gamma) + m - 1/2 + o(1).
Now, U = I + \frac{1}{2} F(1) + C + o(1), where C is the sum of higher Bernoulli corrections (which we suspect is O(1)). F(1) = m [ (1 - 1/m)^n - 1 + n/m ] = m (1 - 1/m)^n - m + n. For large n, (1 - 1/m)^n is exponentially small, so F(1) = n - m + o(1). Then \frac{1}{2} F(1) = n/2 - m/2 + o(1). So U = n \ln n - n (\ln m + 1 - \gamma) + m - 1/2 + n/2 - m/2 + C + o(1) = n \ln n - n (\ln m + 1/2 - \gamma) + m/2 - 1/2 + C + o(1).
Now we need to determine C. C is the sum of the Euler-Maclaurin corrections: C = \sum_{k=1}^\infty \frac{B_{2k}}{(2k)!} F^{(2k-1)}(1). We also need to consider the remainder from the integral approximation? The Euler-Maclaurin formula with remainder gives an exact equality if we include the remainder integral. But the sum of all Bernoulli terms may not converge; it's an asymptotic series. The constant C is the limit of the difference between the sum and the integral plus 1/2 F(1) as we take the limit of the remainder? Actually, the sum \sum_{j=1}^\infty F(j) minus \int_1^\infty F(t) dt - 1/2 F(1) is a constant (as n -> \infty) if the remainder converges. But we need to find it.
We can find the exact constant by evaluating the sum in another way. Let's use the series representation: U = \sum_{j=1}^\infty m^j [ (1 - m^{-j})^n - 1 + n m^{-j} ]. We can write this as: U = \sum_{j=1}^\infty m^j \sum_{k=2}^n \binom{n}{k} (-1)^k m^{-jk} = \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{m^{1-k}}{1 - m^{1-k}}. This is the original sum. We can also write: U = \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{1}{m^{k-1} - 1}. We want the asymptotic expansion of this sum.
Another approach: Use the generating function or the integral representation of the sum over j. There is a known formula for sums of the form \sum_{j=1}^\infty f(m^j) using the Mellin transform. The Mellin transform of \sum_{j=1}^\infty f(m^j) is \frac{1}{1 - m^{-s}} \mathcal{M}f. Here f(x) = x [ (1 - 1/x)^n - 1 + n/x ]. But f(x) is not a simple power function; it depends on n.
Maybe we can find the constant by using the fact that U is related to the expected number of something in a trie, and Knuth gives the asymptotic in the book? The problem says "When m is an integer greater than 2, this quantity arises in the study of generalizations of radix exchange, as well as the trie memory search algorithms of Section 6.3." In Section 6.3, the average number of nodes in a trie is analyzed. Let's recall the result for the expected number of internal nodes in an m-ary trie built from n random strings. According to Knuth, the expected number of internal nodes is: T_n = \sum_{k=1}^n \binom{n}{k} (-1)^{k+1} \frac{1}{1 - m^{-k}}. But our sum is U = \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{1}{m^{k-1} - 1}. Note that \frac{1}{m^{k-1} - 1} = \frac{m}{m^k - m} = \frac{1}{m^{k-1}(1 - m^{-(k-1)})}. Let i = k-1. Then U = \sum_{i=1}^{n-1} \binom{n}{i+1} (-1)^{i+1} \frac{1}{m^i - 1}. This is similar but not identical to the trie internal node sum.
Maybe we can find the exact asymptotic by using the identity: \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{1}{m^{k-1} - 1} = \sum_{j=1}^\infty m^j [ (1 - m^{-j})^n - 1 + n m^{-j} ]. We can evaluate the sum \sum_{j=1}^\infty m^j (1 - m^{-j})^n. This is a known sum. Let's denote S = \sum_{j=1}^\infty m^j (1 - m^{-j})^n. Then U = S - \sum_{j=1}^\infty m^j + n \sum_{j=1}^\infty 1. But those sums diverge. However, we can use the analytic continuation: \sum_{j=1}^\infty m^j = \frac{m}{1-m} (if we interpret as analytic continuation of geometric series? Not valid here because m>1, the series diverges). But we can use the fact that U is finite and we can regularize by subtracting the asymptotic behavior.
Another way: Use the Poisson summation formula on the sum over j. Let j be integer. Let x = j. Then sum = \sum_{x=1}^\infty m^x [ (1 - m^{-x})^n - 1 + n m^{-x} ]. Let t = m^x. This is a sum over a geometric progression. The Poisson summation formula for a geometric progression is equivalent to the Mellin transform. The sum \sum_{x=1}^\infty f(m^x) has the asymptotic expansion: \sum_{x=1}^\infty f(m^x) = \frac{1}{\ln m} \int_0^\infty f(m^t) dt + \sum_{l=-\infty}^\infty \frac{1}{\ln m} \mathcal{M}[f \circ \exp](2\pi i l / \ln m) + \text{lower order}. But we already used Euler-Maclaurin, which is essentially the same but for the function F(t) = f(m^t). The periodic terms come from the fact that the Bernoulli sum might not converge and the remainder involves a periodic function. Wait, the Euler-Maclaurin formula for a sum over integers of a function F(t) gives: \sum_{j=1}^\infty F(j) = \int_1^\infty F(t) dt + \frac{1}{2} F(1) + \int_1^\infty \overline{B}_1(t) F'(t) dt. The remainder \int_1^\infty \overline{B}_1(t) F'(t) dt is not necessarily constant; it could depend on n in a periodic way if F' has some oscillatory behavior. But we saw F'(t) = - m^t \ln m + exponentially small terms. The exponentially small terms might have oscillations? Actually, (1 - m^{-t})^n has oscillations in t for fixed n? No, it's a smooth function of t. The sum is over integer t. The remainder integral is \int_1^\infty ({t}-1/2) F'(t) dt. If F'(t) is smooth and decays, the integral converges to a constant (depending on n). As n -> \infty, does this integral approach a constant, or does it have a periodic component? Let's check F'(t) more carefully.
F(t) = m^t (1 - m^{-t})^n - m^t + n. F'(t) = \ln m [ m^t (1 - m^{-t})^n + n (1 - m^{-t})^{n-1} - m^t ]. = \ln m [ m^t ( (1 - m^{-t})^n - 1 ) + n (1 - m^{-t})^{n-1} ]. For large n, the term n (1 - m^{-t})^{n-1} is exponentially small unless m^{-t} is very small, i.e., t large. But for t large, m^t is huge, and (1 - m^{-t})^n - 1 ~ -n m^{-t}. So F'(t) ~ \ln m [ m^t ( - n m^{-t} ) + n ] = 0? Wait, let's check: For t large, m^{-t} is small. (1 - m^{-t})^n = 1 - n m^{-t} + n(n-1)/2 m^{-2t} - ... So m^t ( (1 - m^{-t})^n - 1 ) = m^t ( - n m^{-t} + O(m^{-2t}) ) = -n + O(m^{-t}). n (1 - m^{-t})^{n-1} = n ( 1 - (n-1) m^{-t} + ... ) = n - n(n-1) m^{-t} + ... Sum: m^t ( (1 - m^{-t})^n - 1 ) + n (1 - m^{-t})^{n-1} = (-n) + n + O(m^{-t}) = O(m^{-t}). So F'(t) is actually exponentially small for large t, not -m^t \ln m. I made a mistake earlier! Let's recompute F'(t): F(t) = m^t [ (1 - m^{-t})^n - 1 + n m^{-t} ]. So F'(t) = \ln m \cdot m^t [ (1 - m^{-t})^n - 1 + n m^{-t} ] + m^t [ n (1 - m^{-t})^{n-1} \cdot m^{-t} \ln m - n m^{-t} \ln m ]. = \ln m \cdot m^t [ (1 - m^{-t})^n - 1 + n m^{-t} ] + \ln m \cdot m^t [ n m^{-t} (1 - m^{-t})^{n-1} - n m^{-t} ]. = \ln m \cdot m^t [ (1 - m^{-t})^n - 1 + n m^{-t} (1 - m^{-t})^{n-1} ]. Wait, let's do it carefully: F(t) = m^t A(t) where A(t) = (1 - m^{-t})^n - 1 + n m^{-t}. Then F'(t) = \ln m \cdot m^t A(t) + m^t A'(t). A'(t) = n (1 - m^{-t})^{n-1} \cdot m^{-t} \ln m - n m^{-t} \ln m. = \ln m \cdot n m^{-t} [ (1 - m^{-t})^{n-1} - 1 ]. So F'(t) = \ln m \cdot m^t [ A(t) + n m^{-t} ( (1 - m^{-t})^{n-1} - 1 ) ]. = \ln m \cdot m^t [ (1 - m^{-t})^n - 1 + n m^{-t} + n m^{-t} (1 - m^{-t})^{n-1} - n m^{-t} ]. = \ln m \cdot m^t [ (1 - m^{-t})^n - 1 + n m^{-t} (1 - m^{-t})^{n-1} ]. = \ln m \cdot m^t [ (1 - m^{-t})^{n-1} (1 - m^{-t} + n m^{-t}) - 1 ]. = \ln m \cdot m^t [ (1 - m^{-t})^{n-1} (1 + (n-1) m^{-t}) - 1 ].
Now, for large t, m^{-t} is small. (1 - m^{-t})^{n-1} = 1 - (n-1) m^{-t} + O(n^2 m^{-2t}). Then (1 - m^{-t})^{n-1} (1 + (n-1) m^{-t}) = (1 - (n-1) m^{-t}) (1 + (n-1) m^{-t}) = 1 - (n-1)^2 m^{-2t} + ... So F'(t) ~ - \ln m \cdot m^t \cdot (n-1)^2 m^{-2t} = - \ln m \cdot (n-1)^2 m^{-t}. This decays exponentially in t! So F'(t) is indeed exponentially small for large t. My earlier claim that F'(t) ~ -m^t \ln m was wrong because I forgot the n m^{-t} term in A(t). Good catch.
So F(t) itself: for large t, (1 - m^{-t})^n ~ 1 - n m^{-t} + n(n-1)/2 m^{-2t}. Then A(t) = (1 - n m^{-t} + n(n-1)/2 m^{-2t}) - 1 + n m^{-t} = n(n-1)/2 m^{-2t}. So F(t) = m^t * n(n-1)/2 m^{-2t} = n(n-1)/2 m^{-t}. This decays exponentially. So F(t) decays exponentially for large t. For small t, F(t) ~ n - m^t (since (1 - m^{-t})^n is exponentially small for t=1? Actually, for t=1, m^{-1} is fixed, so (1 - 1/m)^n is exponentially small. So F(1) = m [ -1 + n/m ] = n - m. For t between 1 and log_m n, m^t grows, but (1 - m^{-t})^n transitions from ~0 to ~1. The function F(t) is positive? Let's check: F(t) = m^t [ (1 - m^{-t})^n - 1 + n m^{-t} ]. For small m^{-t} (large t), this is positive. For large m^{-t} (small t), (1 - m^{-t})^n is near 0, so F(t) ~ m^t ( -1 + n m^{-t} ) = n - m^t. This is positive for m^t < n, negative for m^t > n? At t=log_m n, F(t) ~ n - n + n n(n-1)/2 n^{-2}? Actually, at the transition, F(t) is positive and of order n? Let's check at t such that m^t = n. Then m^{-t} = 1/n. (1 - 1/n)^n ~ e^{-1}. So F(t) ~ n [ e^{-1} - 1 + 1 ] = n e^{-1} > 0. So F(t) is always positive? For t very small, say t=1, m^1 = m < n for large n, so n - m > 0. So F(t) > 0 for all t? Possibly.
Anyway, the key is that F(t) decays exponentially for large t. The Euler-Maclaurin remainder \int_1^\infty \overline{B}_1(t) F'(t) dt converges absolutely. As n -> \infty, F'(t) for fixed t is exponentially small (since (1 - m^{-t})^n decays exponentially for fixed t>0). So the remainder integral tends to 0? Wait, if F'(t) is exponentially small for all fixed t as n -> \infty, then the integral \int_1^\infty \overline{B}_1(t) F'(t) dt would be exponentially small? But we already have F'(1) = \ln m \cdot m [ (1 - 1/m)^n - 1 + n (1/m) (1 - 1/m)^{n-1} ]? At t=1, F'(1) is not exponentially small; it has the term -m \ln m from the -1? Let's evaluate F'(1) again. F'(t) = \ln m \cdot m^t [ (1 - m^{-t})^n - 1 + n m^{-t} (1 - m^{-t})^{n-1} ]. At t=1: F'(1) = \ln m \cdot m [ (1 - 1/m)^n - 1 + n (1/m) (1 - 1/m)^{n-1} ]. For large n, (1 - 1/m)^n is exponentially small. So F'(1) ~ \ln m \cdot m [ -1 + 0 ] = - m \ln m. So F'(1) is O(1), not exponentially small. But for t > 1, (1 - m^{-t}) is larger, so (1 - m^{-t})^n decays exponentially? Actually, for any fixed t > 1, m^{-t} < 1/m, so (1 - m^{-t}) > 1 - 1/m. Since 1 - 1/m < 1, (1 - m^{-t})^n still decays exponentially. So for any fixed t >= 1, F'(t) ~ \ln m \cdot m^t [ -1 + 0 ] = - m^t \ln m. But wait, that would mean F'(t) is O(1) for all t, not exponentially small! But earlier we saw that for large t, F'(t) decays. There is a transition when t is large enough that m^{-t} is O(1/n). For t ~ log_m n, the behavior changes. So F'(t) is O(1) for 1 <= t << log_m n, and decays for t >> log_m n. The integral of F'(t) from 1 to infinity is dominated by t up to log_m n, where F'(t) is O(1). So the remainder integral \int_1^\infty \overline{B}_1(t) F'(t) dt is an integral of a bounded function F'(t) against a periodic function \overline{B}_1(t). As n -> \infty, the region of integration where F'(t) is significant extends to infinity (since log_m n -> \infty). The integrand F'(t) for large t (but still << log_m n) is approximately - m^t \ln m. But m^t grows exponentially! That can't be right because we previously found F'(t) decays for large t. Let's re-evaluate F'(t) for t large but still such that m^t << n. For t such that m^t << n, we have m^{-t} >> 1/n. Then (1 - m^{-t})^n is exponentially small? Actually, if m^{-t} is much larger than 1/n, then n m^{-t} >> 1, so (1 - m^{-t})^n = e^{n \ln(1 - m^{-t})} ~ e^{-n m^{-t}} which is exponentially small. So for t such that m^{-t} >> 1/n, (1 - m^{-t})^n is negligible. Then F'(t) = \ln m \cdot m^t [ -1 + n m^{-t} (1 - m^{-t})^{n-1} ]. Now, (1 - m^{-t})^{n-1} ~ e^{-n m^{-t}} which is exponentially small. So F'(t) ~ - m^t \ln m. This grows exponentially with t! But wait, if m^t << n, then m^t is large but not huge? Actually, if t is near log_m n, m^t is comparable to n, so m^t is O(n). So F'(t) is O(n) in that region? But earlier we thought F'(t) was O(1). There's a contradiction.
Let's re-evaluate F(t) for t such that m^t = O(n). Let m^t = \alpha n, where \alpha is a constant (0 < \alpha < 1). Then m^{-t} = 1/(\alpha n). Then (1 - m^{-t})^n = (1 - 1/(\alpha n))^n -> e^{-1/\alpha}. Then F'(t) = \ln m \cdot m^t [ (1 - m^{-t})^n - 1 + n m^{-t} (1 - m^{-t})^{n-1} ]. m^t = \alpha n. m^{-t} = 1/(\alpha n). (1 - m^{-t})^n = (1 - 1/(\alpha n))^n ~ e^{-1/\alpha}. n m^{-t} (1 - m^{-t})^{n-1} = n * 1/(\alpha n) * (1 - 1/(\alpha n))^{n-1} ~ \frac{1}{\alpha} e^{-1/\alpha}. So the bracket = e^{-1/\alpha} - 1 + \frac{1}{\alpha} e^{-1/\alpha} = e^{-1/\alpha} (1 + 1/\alpha) - 1. This is O(1). Then F'(t) = \ln m \cdot \alpha n * O(1) = O(n). So F'(t) is indeed O(n) in the region t ~ log_m n! My earlier claim that F'(1) is O(1) is correct, but F'(t) grows as t increases up to log_m n. The integral of F'(t) from 1 to infinity is O(n log n)? But we know F(t) itself at t ~ log_m n is O(n). The derivative F'(t) is the rate of change of F(t). Since F(t) goes from O(n) at t=1? Actually, F(1) = n - m = O(n). At t = log_m n, F(t) ~ n e^{-1} = O(n). So F(t) is O(n) throughout. Its derivative could be O(n) as well, but the integral of F'(t) over an interval of length O(log n) gives O(n log n), which is consistent with F(t) varying by O(n log n)? But F(t) doesn't vary by O(n log n); it's O(n) at both ends. The derivative must oscillate. Let's check: F(t) = m^t [ (1 - m^{-t})^n - 1 + n m^{-t} ]. For t from 1 to log_m n - O(1), (1 - m^{-t})^n is exponentially small, so F(t) ~ n - m^t. This decreases from n - m to 0 as t goes from 1 to log_m n. The derivative of n - m^t is - m^t \ln m, which is O(m^t) = O(n) at t ~ log_m n, and O(1) at t=1. So F(t) decreases by O(n) over an interval of length O(log n). The total change is O(n), not O(n log n). The integral of the derivative is F(log_m n) - F(1) = O(n). But the derivative itself is O(n) in magnitude over a region of size O(log n)? If F'(t) ~ - m^t \ln m, then \int_1^{\log_m n} m^t \ln m dt = m^{\log_m n} - m = n - m = O(n). So the integral of |F'(t)| is O(n). So F'(t) is O(n) but its integral is O(n) because the region where it's large is small (since m^t grows exponentially, the integral of m^t from 1 to log_m n is dominated by the upper end, which is O(n)). So F'(t) is not uniformly O(1); it's O(1) near t=1 and O(n) near t=log_m n. The Euler-Maclaurin remainder \int_1^\infty \overline{B}_1(t) F'(t) dt will be an integral of a periodic function against F'(t). As n -> \infty, the region where F'(t) is large moves to infinity. This can lead to a periodic function of log_m n. The asymptotic sum of such terms often involves a periodic function.
Our earlier Euler-Maclaurin expansion gave U = I + 1/2 F(1) + \sum_{k} \frac{B_{2k}}{(2k)!} F^{(2k-1)}(1). The derivatives at 1: F(1) = n - m + o(1). F'(1) = -m \ln m + o(1). F''(1) will be O(1) etc. So the sum of Bernoulli terms at 1 is a constant (independent of n) plus exponentially small terms. But wait, the Euler-Maclaurin formula with remainder is: \sum_{j=1}^\infty F(j) = \int_1^\infty F(t) dt + \frac{1}{2} F(1) + \sum_{k=1}^{K-1} \frac{B_{2k}}{(2k)!} F^{(2k-1)}(1) + R_K. The remainder R_K involves an integral of F^{(2K)} times a periodic function. For large n, if we fix K, the remainder might be large? The standard Euler-Maclaurin is an asymptotic series for a fixed function as the step size goes to 0. Here we have a fixed step size (1) but the function F depends on n and its derivatives grow with n. The Euler-Maclaurin formula is not directly applicable as an asymptotic series in n because the derivatives of F are not bounded independently of n. In fact, the higher derivatives at 1 might grow with n? Let's check F''(1). F'(t) = \ln m \cdot m^t [ (1 - m^{-t})^n - 1 + n m^{-t} (1 - m^{-t})^{n-1} ]. At t=1, (1 - 1/m)^n is exponentially small. So F'(1) ~ -m \ln m. This is O(1). What about F''(1)? It will involve derivatives of the bracket. The bracket B(t) = (1 - m^{-t})^n - 1 + n m^{-t} (1 - m^{-t})^{n-1}. For t=1, B(1) is exponentially small? Actually, (1 - 1/m)^n is exponentially small, so B(1) = -1 + o(1). Its derivative B'(t) at t=1 might be O(1) or O(n)? Let's compute B'(t). B(t) = (1 - m^{-t})^n - 1 + n m^{-t} (1 - m^{-t})^{n-1}. B'(t) = n (1 - m^{-t})^{n-1} m^{-t} \ln m + n [ -m^{-t} \ln m (1 - m^{-t})^{n-1} + m^{-t} (n-1) (1 - m^{-t})^{n-2} m^{-t} \ln m ]. = \ln m [ n m^{-t} (1 - m^{-t})^{n-1} - n m^{-t} (1 - m^{-t})^{n-1} + n(n-1) m^{-2t} (1 - m^{-t})^{n-2} ]. = \ln m \cdot n(n-1) m^{-2t} (1 - m^{-t})^{n-2}. At t=1, this is \ln m \cdot n(n-1) m^{-2} (1 - 1/m)^{n-2}. For large n, this is exponentially small! So B'(1) is exponentially small. Then F''(1) = \ln m \cdot m B(1) + m \ln m B'(1) ~ -m (\ln m)^2 + exponentially small. So F''(1) is O(1). Similarly, higher derivatives at 1 will be O(1). So the Bernoulli sum at 1 converges to a constant C_0 as n -> \infty.
But the remainder R_K = \int_1^\infty \frac{\overline{B}_K(t)}{K!} F^{(K)}(t) dt. For large n, the derivatives F^{(K)}(t) for t near log_m n will be large. The remainder might not be small. In fact, the Euler-Maclaurin formula is not the right tool here; we should use the Poisson summation formula (or Mellin transform) to get the periodic terms.
The sum \sum_{j=1}^\infty F(j) can be written using the Mellin transform: \sum_{j=1}^\infty F(j) = \frac{1}{2\pi i} \int_{c-i\infty}^{c+i\infty} \zeta(s) \mathcal{M}F ds? Not exactly, because F is not defined for all real x? F(t) is defined for t>0. The sum over j of F(j) is the sum over integers. The Mellin transform of the sum is \sum_{j=1}^\infty \mathcal{M}F j^{-s} = \zeta(s) \mathcal{M}F? Wait, if we consider the sum \sum_{j=1}^\infty f(j), its Mellin transform is not simply \zeta(s) \mathcal{M}f. The Mellin transform is used for sums of the form \sum_{j} f(m^j). Our sum is \sum_{j} F(j) with F(j) = m^j [ (1 - m^{-j})^n - 1 + n m^{-j} ]. This is exactly of the form \sum_{j} g(m^j) with g(x) = x [ (1 - 1/x)^n - 1 + n/x ]. So we can use the Mellin transform for sums over geometric progressions.
Let S = \sum_{j=1}^\infty g(m^j). The Mellin transform of the sum is \frac{1}{1 - m^{-s}} \mathcal{M}g, where \mathcal{M}g = \int_0^\infty g(x) x^{s-1} dx. Then S = \frac{1}{2\pi i} \int_{c-i\infty}^{c+i\infty} \frac{\mathcal{M}g}{1 - m^{-s}} ds. The asymptotic expansion as n -> \infty comes from the poles of the integrand.
Let's compute \mathcal{M}g for g(x) = x [ (1 - 1/x)^n - 1 + n/x ]. g(x) = x (1 - 1/x)^n - x + n. We need the integral \int_0^\infty g(x) x^{s-1} dx. But g(x) has support? Actually, g(x) is defined for x >= 1? The sum starts at j=1, so x = m^j >= m. But the Mellin transform requires integration from 0 to \infty. We can define g(x) = 0 for x < m. This introduces a discontinuity at x=m, which will add extra terms. Alternatively, we can shift the sum: \sum_{j=1}^\infty g(m^j) = \sum_{j=0}^\infty g(m^{j+1}) = \sum_{j=0}^\infty h(m^j) with h(x) = g(m x). Then h(x) is defined for x >= 1. We can set h(x) = 0 for x < 1. Then the sum is \sum_{j=0}^\infty h(m^j). The Mellin transform of h(x) will be easier? Let's try.
Let h(x) = g(m x) = m x [ (1 - 1/(m x))^n - 1 + n/(m x) ]. Then S = \sum_{j=0}^\infty h(m^j). The Mellin transform of h(x) is H(s) = \int_0^\infty h(x) x^{s-1} dx. Since h(x) = 0 for x < 1 (we can define it that way), H(s) = \int_1^\infty h(x) x^{s-1} dx. This is analytic for Re(s) < 0? h(x) decays as x -> \infty? For large x, h(x) ~ m x [ e^{-n/(m x)} - 1 + n/(m x) ] ~ m x [ -n^2/(2 m^2 x^2) ] = - n^2/(2 m x). So h(x) ~ -n^2/(2 m) x^{-1}. Then \int_1^\infty h(x) x^{s-1} dx converges for Re(s) < 0. We can compute H(s) exactly by expanding (1 - 1/(m x))^n. (1 - 1/(m x))^n = \sum_{k=0}^n \binom{n}{k} (-1)^k (m x)^{-k}. Then h(x) = m x \sum_{k=0}^n \binom{n}{k} (-1)^k m^{-k} x^{-k} - m x + n. = \sum_{k=0}^n \binom{n}{k} (-1)^k m^{1-k} x^{1-k} - m x + n. The k=0 term: \binom{n}{0} (-1)^0 m x = m x, cancels with -m x. The k=1 term: \binom{n}{1} (-1)^1 m^{0} x^{0} = -n, cancels with +n. So h(x) = \sum_{k=2}^n \binom{n}{k} (-1)^k m^{1-k} x^{1-k}. This is a finite sum of powers of x. The integral from 1 to \infty of x^{1-k} x^{s-1} = x^{s-k} dx converges for Re(s) < k-1. The integral is \int_1^\infty x^{s-k} dx = - \frac{1}{s - k + 1} (for Re(s) < k-1). So H(s) = \sum_{k=2}^n \binom{n}{k} (-1)^k m^{1-k} \left( - \frac{1}{s - k + 1} \right) = \sum_{k=2}^n \binom{n}{k} (-1)^{k+1} \frac{m^{1-k}}{s - k + 1}. This is a sum of simple poles at s = k-1 for k=2..n. The sum S = \sum_{j=0}^\infty h(m^j) has Mellin transform \frac{H(s)}{1 - m^{-s}} (for Re(s) < 1? Actually, the sum over j of h(m^j) has Mellin transform \frac{H(s)}{1 - m^{-s}} provided we can interchange sum and integral. The asymptotic expansion of S is given by the sum of residues of \frac{H(s)}{1 - m^{-s}} x^{-s}? Wait, the standard Mellin summation formula: If \sum_{j=0}^\infty h(m^j) = S, then the Mellin transform of S as a function of some parameter? Actually, S is a number (depending on n). We can use the inverse Mellin transform to represent S: S = \frac{1}{2\pi i} \int_{c-i\infty}^{c+i\infty} \frac{H(s)}{1 - m^{-s}} ds, where c is chosen such that the integral converges (c < 0). Then we can shift the contour to the right, picking up residues at poles. The poles come from H(s) at s = 1, 2, ..., n-1 (from k=2..n), and from 1 - m^{-s} at s = 2\pi i l / \ln m for integer l. The poles at s = k-1 (k=2..n) give contributions that are terms in the asymptotic expansion? As n -> \infty, these poles move to infinity. The poles at s = 2\pi i l / \ln m are fixed. The residue at s = 0? H(s) has a pole at s=1? k=2 gives s=1. Let's check the residue at s=0. H(s) has no pole at s=0? H(s) = \sum_{k=2}^n \binom{n}{k} (-1)^{k+1} m^{1-k} \frac{1}{s - k + 1}. At s=0, this is \sum_{k=2}^n \binom{n}{k} (-1)^{k+1} m^{1-k} \frac{1}{-k+1} = - \sum_{k=2}^n \binom{n}{k} (-1)^{k+1} \frac{m^{1-k}}{k-1}. But this is not the leading asymptotic; it's a constant term? The leading asymptotic comes from the pole at s=0 of the integrand \frac{H(s)}{1 - m^{-s}}? The denominator 1 - m^{-s} has a pole at s=0? Actually, 1 - m^{-s} = 1 - e^{-s \ln m} ~ s \ln m. So it has a zero at s=0, not a pole. The integrand has a pole at s=0 if H(s) has a pole at s=0. H(s) has poles at s=1,2,...,n-1. The nearest pole to the left of the contour is at s=1? Our contour is at c < 0. The poles of H(s) are at positive integers (1 to n-1). The denominator 1 - m^{-s} has zeros at s = 2\pi i l / \ln m. So the integrand has poles at s = k-1 for k=2..n. Shifting the contour to the right would pick up residues at these poles. But as n -> \infty, these poles go to infinity. The leading asymptotic as n -> \infty is determined by the behavior of the integrand near the dominant poles? This is getting complicated.
Maybe there's a simpler way. The sum U_{mn} is exactly the expected number of something in a trie, and Knuth might have derived its asymptotic in the text or exercises. Let's look at the exercises 47-49. They deal with U_n = \sum_{k>=1} (n/2^k) e^{-n/2^k}. That sum is bounded and has an asymptotic expansion with a periodic function. Our U_{mn} is different. But maybe U_{mn} can be expressed in terms of U_n for some m? Not directly.
Let's try to find the asymptotic by another method: use the identity: U_{mn} = \sum_{j=1}^\infty m^j [ (1 - m^{-j})^n - 1 + n m^{-j} ]. We can write this as: U = \sum_{j=1}^\infty m^j \int_0^n \frac{d}{d\lambda} (1 - m^{-j})^\lambda d\lambda? Not helpful.
Let's consider the function f(x) = \sum_{j=1}^\infty m^j [ (1 - m^{-j})^x - 1 + x m^{-j} ]. For real x. Then U_{mn} = f(n). We want the asymptotic of f(n) as n -> \infty. Note that f(x) = \sum_{j=1}^\infty m^j (1 - m^{-j})^x - \sum_{j=1}^\infty m^j + x \sum_{j=1}^\infty 1. The sums diverge. But we can regularize by subtracting the asymptotic behavior as j -> \infty. For large j, m^{-j} is small. We have: (1 - m^{-j})^x = e^{x \ln(1 - m^{-j})} = e^{-x m^{-j} - x m^{-2j}/2 - ...}. So for large j, m^j [ (1 - m^{-j})^x - 1 + x m^{-j} ] ~ m^j [ - x^2 m^{-2j}/2 + ... ] = - x^2/(2 m^j) + ... which decays. So the sum converges absolutely.
We can use the Euler-Maclaurin formula on the sum over j, but we must be careful with the derivatives growing with x. The correct approach is to use the integral representation of the sum via the Fourier expansion of the Bernoulli polynomials, i.e., the Poisson summation formula: \sum_{j=1}^\infty F(j) = \int_1^\infty F(t) dt + \frac{1}{2} F(1) + \sum_{l \neq 0} \int_1^\infty F(t) e^{2\pi i l t} dt. This is exact if F is smooth and decays. The integrals over l \neq 0 will give the periodic fluctuations. Let's compute the Fourier coefficients: c_l = \int_1^\infty F(t) e^{2\pi i l t} dt. As n -> \infty, the main contribution to these integrals comes from t where F(t) is significant. We can approximate F(t) for large n. This is a standard method for sums of the form \sum_j f(n/m^j).
Let's change variable to u = m^t. Then t = \log_m u, dt = du/(u \ln m). F(t) = u [ (1 - 1/u)^n - 1 + n/u ]. The sum S = \sum_{j=1}^\infty F(j) = \sum_{j=1}^\infty G(m^j) with G(u) = u [ (1 - 1/u)^n - 1 + n/u ]. The Poisson summation for geometric progression: \sum_{j=1}^\infty G(m^j) = \frac{1}{\ln m} \int_0^\infty G(u) \frac{du}{u} + \frac{1}{\ln m} \sum_{l \neq 0} \int_0^\infty G(u) u^{-1 - 2\pi i l / \ln m} du? Actually, the standard formula: \sum_{j=0}^\infty f(m^j) = \frac{1}{\ln m} \int_0^\infty f(u) \frac{du}{u} + \frac{1}{\ln m} \sum_{l \neq 0} \int_0^\infty f(u) u^{-1 - 2\pi i l / \ln m} du + \text{residues at } u=1? This is the Mellin transform inversion. The sum \sum_{j} f(m^j) = \frac{1}{2\pi i} \int_{c-i\infty}^{c+i\infty} \frac{\mathcal{M}f}{1 - m^{-s}} ds. The asymptotic expansion as n -> \infty comes from the singularities of the integrand. The function f(u) = u [ (1 - 1/u)^n - 1 + n/u ] depends on n. Its Mellin transform is F(s) = \int_0^\infty f(u) u^{s-1} du. We can write f(u) = \sum_{k=2}^n \binom{n}{k} (-1)^k u^{1-k}. Then F(s) = \sum_{k=2}^n \binom{n}{k} (-1)^k \int_0^\infty u^{s-k} du. This integral diverges at both limits unless we use analytic continuation. This is not the right way.
Let's go back to the sum representation: U = \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{1}{m^{k-1} - 1}. We can use the identity: \frac{1}{m^{k-1} - 1} = \int_0^1 t^{m^{k-1}-2} \ln t? No. Another identity: \frac{1}{a - 1} = \int_0^\infty e^{-t(a-1)} dt? No, \int_0^\infty e^{-t(a-1)} dt = 1/(a-1) for a>1. Yes! For a > 1, \frac{1}{a-1} = \int_0^\infty e^{-t(a-1)} dt. Here a = m^{k-1} > 1. So \frac{1}{m^{k-1} - 1} = \int_0^\infty e^{-t(m^{k-1} - 1)} dt = \int_0^\infty e^{t} e^{-t m^{k-1}} dt. Then U = \sum_{k=2}^n \binom{n}{k} (-1)^k \int_0^\infty e^{t} e^{-t m^{k-1}} dt = \int_0^\infty e^{t} \sum_{k=2}^n \binom{n}{k} (-1)^k e^{-t m^{k-1}} dt. = \int_0^\infty e^{t} \left[ \sum_{k=0}^n \binom{n}{k} (-1)^k e^{-t m^{k-1}} - 1 + n e^{-t} \right] dt. But \sum_{k=0}^n \binom{n}{k} (-1)^k e^{-t m^{k-1}} = e^{-t/m} \sum_{k=0}^n \binom{n}{k} (-1)^k e^{-t m^{k-1} + t/m}? Not a simple binomial expansion because the exponent is m^{k-1}, not k.
Wait, e^{-t m^{k-1}} is not of the form (e^{-t})^{m^{k-1}}? It's e^{-t m^{k-1}}. This is not a binomial expansion in the usual sense. The binomial theorem gives \sum \binom{n}{k} (-1)^k x^k = (1-x)^n. Here we have x = e^{-t m^{k-1}} which depends on k, so we can't factor it.
So that approach fails.
Maybe we can use the representation: \frac{1}{m^{k-1} - 1} = \sum_{j=1}^\infty m^{-j(k-1)}. Then U = \sum_{j=1}^\infty m^j \sum_{k=2}^n \binom{n}{k} (-1)^k m^{-jk} = \sum_{j=1}^\infty m^j [ (1 - m^{-j})^n - 1 + n m^{-j} ]. This is where we started.
Now, to find the asymptotic, we can use the fact that the sum is dominated by j near log_m n. Let's set j = \lfloor \log_m n \rfloor + r. Let \delta = { \log_m n }. Then m^j = n m^{r - \delta}. Then the term is: T_r = m^j [ (1 - m^{-j})^n - 1 + n m^{-j} ] = n m^{r - \delta} [ (1 - m^{\delta - r}/n)^n - 1 + m^{\delta - r} ]. As n -> \infty, (1 - m^{\delta - r}/n)^n -> e^{-m^{\delta - r}}. So T_r ~ n m^{r - \delta} [ e^{-m^{\delta - r}} - 1 + m^{\delta - r} ]. Summing over r from -\infty to \infty (with r integer), the sum U ~ n \sum_{r=-\infty}^\infty m^{r - \delta} [ e^{-m^{\delta - r}} - 1 + m^{\delta - r} ]. But wait, this sum over all integers r diverges because as r -> -\infty, m^{\delta - r} -> \infty, and e^{-m^{\delta - r}} -> 0. Then the term ~ n m^{r - \delta} ( -1 + m^{\delta - r} ) = n (1 - m^{r - \delta}) ~ n. Summing over r from -\infty gives infinity! This is because the approximation (1 - x/n)^n ~ e^{-x} is not valid when x is large (i.e., r negative large). For r negative large, m^{\delta - r} is huge, and (1 - m^{\delta - r}/n)^n is exactly 0 (if m^{\delta - r} > n? Actually, if m^{\delta - r} > n, then m^{-j} > 1, which is impossible because m^{-j} <= 1/m < 1 for j>=1. Wait, j = \lfloor \log_m n \rfloor + r. For r negative large, j can be small. m^{-j} is not small; it's at most 1/m. So m^{\delta - r} = n m^{-j} is at most n/m. It's O(n), not huge compared to n. So x = m^{\delta - r} is O(n). The approximation (1 - x/n)^n ~ e^{-x} is only good when x = o(n). For x ~ n, we need to keep the exact expression. So the sum over r cannot be replaced by the limiting integral over all r; we must handle the region where r is negative (i.e., j < \log_m n) separately.
We already did that: the sum over j from 1 to J (where J = \lfloor \log_m n \rfloor) gives the n \log n term, and the sum over j > J gives O(n). The sum over j > J can be approximated by the integral, and the sum over j <= J is approximated by n - m^j. We computed: U = \sum_{j=1}^J (n - m^j) + \sum_{j=J+1}^\infty m^j [ (1 - m^{-j})^n - 1 + n m^{-j} ] + \text{corrections near } j=J. We found: \sum_{j=1}^J (n - m^j) = J n - \frac{m(m^J - 1)}{m-1} = n \log_m n - \delta n - \frac{m n m^{-\delta} - m}{m-1} + o(n)? Wait, J = \lfloor \log_m n \rfloor, so n = m^{J+\delta}, m^J = n m^{-\delta}. Then \sum_{j=1}^J m^j = \frac{m(m^J - 1)}{m-1} = \frac{m n m^{-\delta} - m}{m-1}. J n = ( \log_m n - \delta ) n = n \log_m n - \delta n. So sum = n \log_m n - \delta n - \frac{m}{m-1} n m^{-\delta} + \frac{m}{m-1} + o(n)? Actually, the m term is O(1). So: \sum_{j=1}^J (n - m^j) = n \log_m n - n \left( \delta + \frac{m^{1-\delta}}{m-1} \right) + \frac{m}{m-1} + o(n).
Now, the tail sum \sum_{j=J+1}^\infty m^j [ (1 - m^{-j})^n - 1 + n m^{-j} ]. Let j = J + k, k = 1, 2, ... Then m^{-j} = m^{-J} m^{-k} = m^{-\delta} n^{-1} m^{-k} = n^{-1} m^{-(\delta + k)}. Then the term is m^{J+k} [ (1 - n^{-1} m^{-(\delta+k)})^n - 1 + n^{-1} m^{-(\delta+k)} n ] = n m^{k - \delta} [ (1 - m^{-(\delta+k)}/n)^n - 1 + m^{-(\delta+k)} ]. As n -> \infty, (1 - m^{-(\delta+k)}/n)^n -> e^{-m^{-(\delta+k)}}. So the tail sum ~ n \sum_{k=1}^\infty m^{k - \delta} [ e^{-m^{-(\delta+k)}} - 1 + m^{-(\delta+k)} ]. This sum converges because for large k, m^{-(\delta+k)} is small, and e^{-x} - 1 + x ~ x^2/2, so term ~ n m^{k-\delta} * m^{-2(\delta+k)}/2 = n m^{-k - 3\delta}/2, which sums to O(n). So the tail sum is n times a function of \delta: T(\delta) = \sum_{k=1}^\infty m^{k - \delta} [ e^{-m^{-(\delta+k)}} - 1 + m^{-(\delta+k)} ].
Also, there is a transition region near j = J. The terms for j = J (k=0) were included in the first sum? We had sum from j=1 to J. We can also include the j=J term in the tail if we start the tail at j=J. The difference is the j=J term which is O(n). It will contribute to the periodic function.
So the total U = n \log_m n + n P(\delta) + o(n), where P(\delta) is a periodic function of \delta = { \log_m n }. This matches the typical behavior of such sums.
But the problem asks for "the asymptotic value". In many contexts, "asymptotic value" might mean the leading term(s). Since the leading term is n \log_m n, that might be part of the answer. But we should provide the full asymptotic expansion up to O(1) or including the periodic function? The problem is HM24, similar to exercise 48 which asks for "asymptotic value ... obtaining terms up to O(1)". So they likely want the expansion up to O(1), which includes the periodic function times n and the constant term? But a periodic function of \log_m n times n is not O(1); it's O(n). So "up to O(1)" means the error term is O(1). The expansion would be: U_{mn} = n \log_m n + n P(\log_m n) + Q + o(1)? But wait, n P(\log_m n) is O(n), so it's part of the asymptotic. The constant term Q would be the next term. "Terms up to O(1)" usually means we give the expansion including all terms that grow with n, and the error is bounded. So we need to find the coefficient of n \log n, the periodic function times n, and the constant term? Or maybe the periodic function is part of the O(1)? No, n times a periodic function is O(n). So the expansion has terms n \log n, n (periodic), and then O(1).
Let's see the style in Knuth's book. In Section 5.2.2, they analyzed the bubble sort and got A = n - \sqrt{\pi n/2} + O(1), etc. They gave asymptotic formulas with O(1) error. For the bubble sort, the number of passes A has a sqrt(n) term and a constant term. The number of comparisons C has a term with n \ln n? They gave C_ave = 1/2 (n^2 - n \ln n - (\gamma + \ln 2 - 1)n) + O(\sqrt{n}). So they include the n \ln n term and the n term, with an error of O(\sqrt{n}). The constant term is not given because the error is O(\sqrt{n}), which is larger than constant. In our case, the error might be O(1) if we can compute the constant exactly? Or maybe the error is O(n^{-\alpha})? The problem says "Find the asymptotic value of the function U_{mn} ... when m is any fixed number greater than 1." It doesn't specify the order of the error. But exercise 48 says "obtaining terms up to O(1)". Exercise 49 says "Extend ... to O(n^{-1})". So likely we need to give the asymptotic expansion up to O(1) or even further.
Let's check the source. The text before the exercises mentions U_n in Eq. (47). The asymptotic formula for U_n is probably given as something like U_n = \frac{1}{2} \ln n + \frac{\gamma}{2} - \frac{\ln 2}{2} + \frac{1}{2} \frac{\ln 2}{\ln 2}? No, exercise 47 says sum_{j} (n/2^j) e^{-n/2^j} is bounded. So U_n is bounded. Its asymptotic expansion would be a constant plus a periodic function plus o(1). Exercise 48 asks for V_n up to O(1). Exercise 49 asks to extend U_n to O(n^{-1}). Our U_{mn} is a different sum, but it might have a similar structure: U_{mn} = n \log_m n + n P(\log_m n) + C + o(1) or something.
Let's try to find the exact asymptotic by using the known result for the sum \sum_{j} m^j (1 - m^{-j})^n. This sum is related to the expected number of nodes in a trie. In Knuth's Section 6.3 (Trie search), the expected number of internal nodes in an m-ary trie is: T_n = \sum_{k=1}^n \binom{n}{k} (-1)^{k+1} \frac{1}{1 - m^{-k}}. Our sum is U = \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{1}{m^{k-1} - 1} = \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{1}{m^{k-1}(1 - m^{-(k-1)})}. Not exactly the same.
Maybe we can relate U to the expected external path length or something. Let's search memory: The sum \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{1}{m^{k-1} - 1} appears in the analysis of "radix exchange" and "trie memory search". In Knuth's book, the expected number of passes in radix exchange sort is \sum_{k=1}^\infty [1 - (1 - 2^{-k})^n - n 2^{-k} (1 - 2^{-k})^{n-1}]? Not sure.
Another thought: The sum U_{mn} can be expressed in terms of the function U_n from the text by a change of variables? If m is not 2, it's different.
Let's try to compute the constant term by evaluating the sum exactly using the Euler-Maclaurin formula with the periodic remainder. We have: U = \sum_{j=1}^\infty F(j) = \int_1^\infty F(t) dt + \frac{1}{2} F(1) + \int_1^\infty \overline{B}_1(t) F'(t) dt. We already computed I = \int_1^\infty F(t) dt = \frac{1}{\ln m} \int_0^{1/m} \frac{(1-y)^n - 1 + n y}{y^2} dy. We found I = n \ln n - n (\ln m + 1 - \gamma) + m - 1/2 + o(1)? Wait, we had I = I2 + I3, with I2 = n \ln n - n (\ln m + 1 - \gamma) + m + o(n)? Let's re-evaluate I carefully with the exact constant terms.
I = \frac{1}{\ln m} \int_0^{1/m} \frac{(1-y)^n - 1 + n y}{y^2} dy. We split as I = \frac{1}{\ln m} ( I2 + I3 ), where I2 = \int_0^{1/m} \frac{e^{-n y} - 1 + n y}{y^2} dy, I3 = \int_0^{1/m} \frac{(1-y)^n - e^{-n y}}{y^2} dy.
We computed I2 exactly: I2 = - m ( e^{-n/m} - 1 + n/m ) + n \int_0^{n/m} \frac{1 - e^{-t}}{t} dt. As n -> \infty, e^{-n/m} is exponentially small. So I2 = m - n + n \int_0^{n/m} \frac{1 - e^{-t}}{t} dt + o(1). Now, \int_0^{n/m} \frac{1 - e^{-t}}{t} dt = \ln(n/m) + \gamma + O(m/n)? Actually, the error is O(1/(n/m)) = O(m/n). So I2 = m - n + n (\ln n - \ln m + \gamma) + O(1) + o(1) = n \ln n - n (\ln m + 1 - \gamma) + m + O(1/n)? Wait, the O(1) term comes from the error in the integral approximation. Let's be precise: \int_0^X \frac{1 - e^{-t}}{t} dt = \ln X + \gamma + \int_X^\infty \frac{e^{-t}}{t} dt. So I2 = m - n + n (\ln(n/m) + \gamma + \int_{n/m}^\infty \frac{e^{-t}}{t} dt) + o(1) = n \ln n - n \ln m - n + n \gamma + m + n \int_{n/m}^\infty \frac{e^{-t}}{t} dt + o(1). Now, \int_{n/m}^\infty \frac{e^{-t}}{t} dt = E_1(n/m) ~ \frac{m}{n} e^{-n/m} (1 - \frac{m}{n} + ...). So n E_1(n/m) = O(m e^{-n/m}) = exponentially small. So I2 = n \ln n - n (\ln m + 1 - \gamma) + m + o(1). The o(1) is actually exponentially small. So I2 = n \ln n - n (\ln m + 1 - \gamma) + m + O(e^{-c n}).
Now I3 = \int_0^{1/m} \frac{(1-y)^n - e^{-n y}}{y^2} dy. We need the exact constant of I3 as n -> \infty. We had I3 = -1/2 + O(1/n). Let's verify more carefully. (1-y)^n = e^{n \ln(1-y)} = e^{-n y - n y^2/2 - n y^3/3 - ...}. Let S(y) = -n y^2/2 - n y^3/3 - ... = -n y^2/2 (1 + 2y/3 + ...). Then (1-y)^n - e^{-n y} = e^{-n y} ( e^{S(y)} - 1 ). I3 = \int_0^{1/m} e^{-n y} \frac{e^{S(y)} - 1}{y^2} dy. Change variable t = n y. Then dy = dt/n, y = t/n. I3 = \int_0^{n/m} e^{-t} \frac{e^{S(t/n)} - 1}{(t/n)^2} \frac{dt}{n} = n \int_0^{n/m} e^{-t} \frac{e^{S(t/n)} - 1}{t^2} dt. S(t/n) = -n (t/n)^2/2 - n (t/n)^3/3 - ... = -t^2/(2n) - t^3/(3n^2) - ... So e^{S(t/n)} - 1 = -t^2/(2n) - t^3/(3n^2) - ... + \frac{1}{2} t^4/(4n^2) + ... = -t^2/(2n) + O(t^3/n^2 + t^4/n^2). Then \frac{e^{S} - 1}{t^2} = -1/(2n) + O(t/n^2 + t^2/n^2). So I3 = n \int_0^{n/m} e^{-t} [ -1/(2n) + O(t/n^2 + t^2/n^2) ] dt = -\frac{1}{2} \int_0^{n/m} e^{-t} dt + O(1/n). \int_0^{n/m} e^{-t} dt = 1 - e^{-n/m} = 1 + o(1). So I3 = -1/2 + O(1/n).
Thus I = \frac{1}{\ln m} ( I2 + I3 ) = \frac{1}{\ln m} [ n \ln n - n (\ln m + 1 - \gamma) + m - 1/2 ] + O(1/n). Wait, I2 had an m term, I3 had -1/2. So I = \frac{1}{\ln m} [ n \ln n - n (\ln m + 1 - \gamma) + m - 1/2 ] + O(1/n).
But earlier we had I = \int_1^\infty F(t) dt = \frac{1}{\ln m} \int_0^{1/m} ... dy. That matches.
Now, F(1) = m [ (1 - 1/m)^n - 1 + n/m ] = m (1 - 1/m)^n - m + n. So \frac{1}{2} F(1) = \frac{1}{2} n - \frac{1}{2} m + o(1).
Now, the remainder R = \int_1^\infty \overline{B}_1(t) F'(t) dt. We need the asymptotic of R as n -> \infty. F'(t) = \ln m \cdot m^t [ (1 - m^{-t})^n - 1 + n m^{-t} (1 - m^{-t})^{n-1} ]. As n -> \infty, this function has a transition near t = \log_m n. We can write t = \log_m n + u. Then m^t = n m^u, m^{-t} = m^{-u}/n. F'(t) dt = \ln m \cdot n m^u [ (1 - m^{-u}/n)^n - 1 + m^{-u} (1 - m^{-u}/n)^{n-1} ] \frac{du}{\ln m}? Actually, dt = du/\ln m. So F'(t) dt = m^u [ (1 - m^{-u}/n)^n - 1 + m^{-u} (1 - m^{-u}/n)^{n-1} ] n du. As n -> \infty, this tends to n m^u [ e^{-m^{-u}} - 1 + m^{-u} e^{-m^{-u}} ] du. But the integral R = \int_1^\infty \overline{B}1(t) F'(t) dt = \int{1 - \log_m n}^\infty \overline{B}_1(\log_m n + u) n m^u [ (1 - m^{-u}/n)^n - 1 + m^{-u} (1 - m^{-u}/n)^{n-1} ] du. As n -> \infty, the lower limit goes to -\infty. The integrand converges pointwise to n m^u [ e^{-m^{-u}} - 1 + m^{-u} e^{-m^{-u}} ]. But note the factor n! This means R grows like n. But earlier we thought R is O(1). There's a mistake: F'(t) dt has a factor n? Let's check F'(t) again. F(t) = m^t [ (1 - m^{-t})^n - 1 + n m^{-t} ]. F'(t) = \ln m \cdot m^t [ (1 - m^{-t})^n - 1 + n m^{-t} ] + m^t [ n (1 - m^{-t})^{n-1} m^{-t} \ln m - n m^{-t} \ln m ]. = \ln m \cdot m^t [ (1 - m^{-t})^n - 1 + n m^{-t} (1 - m^{-t})^{n-1} ]. Now, if we set t = \log_m n + u, then m^t = n m^u, m^{-t} = m^{-u}/n. F'(t) = \ln m \cdot n m^u [ (1 - m^{-u}/n)^n - 1 + m^{-u} (1 - m^{-u}/n)^{n-1} ]. As n -> \infty, the bracket -> e^{-m^{-u}} - 1 + m^{-u} e^{-m^{-u}} = e^{-m^{-u}} (1 + m^{-u}) - 1. For u -> -\infty, m^{-u} -> \infty, e^{-m^{-u}} -> 0, so bracket ~ -1. For u -> +\infty, m^{-u} -> 0, e^{-m^{-u}} ~ 1 - m^{-u} + m^{-2u}/2, bracket ~ (1 - m^{-u})(1 + m^{-u}) - 1 = -m^{-2u} + ... -> 0. So F'(t) ~ n \ln m \cdot m^u * g(u), where g(u) is a function that is O(1) as u -> -\infty and decays exponentially as u -> +\infty. Then F'(t) dt = n m^u g(u) du (since dt = du/\ln m). So the remainder R = \int \overline{B}_1(\log_m n + u) n m^u g(u) du. This is n times a periodic function of \log_m n? Because \overline{B}1(\log_m n + u) = { \log_m n + u } - 1/2 = { \log_m n } + u - \lfloor { \log_m n } + u \rfloor - 1/2. As n -> \infty, the lower limit of integration goes to -\infty. The integral \int{-\infty}^\infty \overline{B}_1(\delta + u) m^u g(u) du is a function of \delta = { \log_m n }. So R = n P(\delta) + o(n)? But we already have U = I + 1/2 F(1) + R. And I + 1/2 F(1) = n \log_m n - n (\ln m + 1/2 - \gamma)/\ln m + m/2 - m/(2\ln m?) Wait, we had I in terms of \ln m? Let's re-evaluate the combination.
Wait, I is the integral \int_1^\infty F(t) dt. We computed I = \frac{1}{\ln m} [ n \ln n - n (\ln m + 1 - \gamma) + m - 1/2 ] + O(1/n). So I = n \log_m n - n (1 + 1/\ln m - \gamma/\ln m) + m/\ln m - 1/(2\ln m) + O(1/n). And 1/2 F(1) = n/2 - m/2 + O(e^{-cn}). Sum I + 1/2 F(1) = n \log_m n + n [ -1 - 1/\ln m + \gamma/\ln m + 1/2 ] + m/\ln m - 1/(2\ln m) - m/2 + O(1/n). = n \log_m n - n [ 1/2 + 1/\ln m - \gamma/\ln m ] + (m/\ln m - m/2) - 1/(2\ln m) + O(1/n).
Now, the remainder R = \int_1^\infty \overline{B}1(t) F'(t) dt. We can compute R exactly using the Mellin transform or by evaluating the sum directly. But we have another expression for U: U = \sum{j=1}^\infty F(j) = \sum_{j=1}^\infty m^j [ (1 - m^{-j})^n - 1 + n m^{-j} ]. We also have U = \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{1}{m^{k-1} - 1}.
Maybe we can find the asymptotic of U by using the known result for the expected number of nodes in a trie. In Knuth's "The Art of Computer Programming", Volume 3, Section 6.3, the average number of internal nodes in an m-ary trie is: T_n = \sum_{k=1}^n \binom{n}{k} (-1)^{k+1} \frac{1}{1 - m^{-k}}. Our sum is U = \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{1}{m^{k-1} - 1} = \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{m^{-(k-1)}}{1 - m^{-(k-1)}}. Let i = k-1. U = \sum_{i=1}^{n-1} \binom{n}{i+1} (-1)^{i+1} \frac{m^{-i}}{1 - m^{-i}}. This is similar but not identical to T_n.
Maybe we can relate U to the sum \sum_{k=1}^n \binom{n}{k} (-1)^{k+1} \frac{1}{1 - m^{-k}}. Note that \frac{1}{1 - m^{-k}} = \sum_{j=0}^\infty m^{-jk}. Then \sum_{k=1}^n \binom{n}{k} (-1)^{k+1} \frac{1}{1 - m^{-k}} = \sum_{j=0}^\infty \sum_{k=1}^n \binom{n}{k} (-1)^{k+1} m^{-jk} = \sum_{j=0}^\infty [ 1 - (1 - m^{-j})^n ]. So T_n = \sum_{j=0}^\infty [ 1 - (1 - m^{-j})^n ]. Our U = \sum_{j=1}^\infty m^j [ (1 - m^{-j})^n - 1 + n m^{-j} ]. These are different.
Wait, the sum \sum_{j=0}^\infty [ 1 - (1 - m^{-j})^n ] is the expected number of internal nodes in a trie. Its asymptotic is known: T_n = n \log_m n + n ( \frac{\gamma}{\ln m} - \frac{1}{2} + \frac{1}{\ln m} + \text{periodic} ) + O(1)? Actually, the classic result by Flajolet and Sedgewick (or Knuth) for the expected number of nodes in a trie is: T_n = \frac{n}{\ln m} \ln n + n \left( \frac{\gamma}{\ln m} - \frac{1}{2} + \frac{1}{\ln m} \right) + P(\log_m n) + O(1)? Wait, the expected number of internal nodes in a random trie is n \log_m n + n P(\log_m n) + O(1). The constant term is often given.
Our U is \sum_{j=1}^\infty m^j [ (1 - m^{-j})^n - 1 + n m^{-j} ]. We can write U = \sum_{j=1}^\infty \frac{m^j}{n} [ (1 - m^{-j})^n - 1 + n m^{-j} ]? No.
Maybe we can find a generating function for U and use singularity analysis.
Let's try to compute the asymptotic by a different method. Consider the sum: U = \sum_{j=1}^\infty m^j [ (1 - m^{-j})^n - 1 + n m^{-j} ]. We can write this as: U = \sum_{j=1}^\infty m^j \sum_{k=2}^n \binom{n}{k} (-1)^k m^{-jk} = \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{m^{1-k}}{1 - m^{1-k}}. = \sum_{k=2}^n \binom{n}{k} (-1)^k \frac{1}{m^{k-1} - 1}.
Now, use the identity: \frac{1}{m^{k-1} - 1} = \int_0^1 \frac{x^{m^{k-1}-2} dx}{\text{?}} No.
Another identity: \frac{1}{m^{k-1} - 1} = \int_0^\infty \frac{e^{-t}}{1 - e^{-t}} e^{-t m^{k-1}}? Not sure.
Let's consider the function f(z) = \sum_{k=2}^\infty \frac{z^k}{m^{k-1} - 1}. Then U_{mn} is the nth coefficient of something? Not directly.
Maybe we can use the fact that the sum over j is a Riemann sum for an integral. We had: U = \sum_{j=1}^\infty F(j) with F(t) = m^t [ (1 - m^{-t})^n - 1 + n m^{-t} ]. We applied the Euler-Maclaurin formula. The remainder R = \int_1^\infty \overline{B}1(t) F'(t) dt. We found that R = n \int{-\infty}^\infty \overline{B}_1(\log_m n + u) m^u g(u) du + o(n), where g(u) = e^{-m^{-u}} (1 + m^{-u}) - 1? Wait, we need the exact limit of F'(t)/n.
Let's compute the limit of F'(t)/n as n -> \infty with t = \log_m n + u. F'(t) = \ln m \cdot m^t [ (1 - m^{-t})^n - 1 + n m^{-t} (1 - m^{-t})^{n-1} ]. Let x = m^{-t} = m^{-u}/n. Then F'(t) = \ln m \cdot n m^u [ (1 - x)^n - 1 + n x (1 - x)^{n-1} ]. As n -> \infty, (1 - x)^n -> e^{-m^{-u}}. So F'(t) ~ \ln m \cdot n m^u [ e^{-m^{-u}} - 1 + m^{-u} e^{-m^{-u}} ]. Thus F'(t) ~ n h(u) \ln m? Wait, F'(t) dt = F'(t) du/\ln m = n m^u [ e^{-m^{-u}} - 1 + m^{-u} e^{-m^{-u}} ] du. So R = \int \overline{B}1(\log_m n + u) n m^u [ e^{-m^{-u}} - 1 + m^{-u} e^{-m^{-u}} ] du + o(n). Let H(u) = m^u [ e^{-m^{-u}} - 1 + m^{-u} e^{-m^{-u}} ]. Then R = n \int{-\infty}^\infty \overline{B}_1(\delta + u) H(u) du + o(n), where \delta = { \log_m n }. This integral is a periodic function of \delta with period 1. Let's denote it n P(\delta). So U = I + \frac{1}{2} F(1) + n P(\delta) + o(n).
Now, we also have the tail of the sum for j > J, which we included in the Euler-Maclaurin remainder? The Euler-Maclaurin formula is exact for the sum over all j. The integral I is from 1 to \infty. The remainder R includes the entire difference between the sum and the integral plus 1/2 F(1). So U = I + 1/2 F(1) + R exactly. We approximated I and 1/2 F(1) up to O(1). The remainder R we approximated as n P(\delta) + o(n). But we need to check if R has an O(1) part as well. The o(n) error in our approximation of R might be O(1) or smaller.
Now, we can combine everything: U = n \log_m n - n [ 1/2 + 1/\ln m - \gamma/\ln m ] + (m/\ln m - m/2) - 1/(2\ln m) + n P(\delta) + o(n).
But wait, P(\delta) is the integral \int \overline{B}1(\delta + u) H(u) du. We can also express the sum of the tail we did earlier. The tail sum T = \sum{k=1}^\infty m^{J+k} [ (1 - m^{-J-k})^n - 1 + n m^{-J-k} ] ~ n \sum_{k=1}^\infty m^{k-\delta} [ e^{-m^{-(\delta+k)}} - 1 + m^{-(\delta+k)} ]. This tail sum is part of U. The sum from j=1 to J is S = \sum_{j=1}^J (n - m^j) + o(n) = n \log_m n - n [ \delta + \frac{m^{1-\delta}}{m-1} ] + \frac{m}{m-1} + o(n). So U = S + T + o(n). Let's compare with our Euler-Maclaurin expression.
From S + T: U = n \log_m n - n [ \delta + \frac{m^{1-\delta}}{m-1} ] + \frac{m}{m-1} + n \sum_{k=1}^\infty m^{k-\delta} [ e^{-m^{-(\delta+k)}} - 1 + m^{-(\delta+k)} ] + o(n).
From Euler-Maclaurin: U = n \log_m n - n [ 1/2 + 1/\ln m - \gamma/\ln m ] + (m/\ln m - m/2) - 1/(2\ln m) + n P(\delta) + o(n).
These must be equal. This implies that P(\delta) is exactly the periodic part from S and T. Let's check if the constant terms match. The constant term in S+T is m/(m-1). In the other expression, it's m/\ln m - m/2 - 1/(2\ln m). These are not equal in general. So there must be additional O(1) terms from the remainder R, or from the approximation of I and F(1). Our I had a term m - 1/2 divided by \ln m. Let's recompute I carefully with all constant terms.
I = \frac{1}{\ln m} \int_0^{1/m} \frac{(1-y)^n - 1 + n y}{y^2} dy. We split I = \frac{1}{\ln m} (I2 + I3). I2 = \int_0^{1/m} \frac{e^{-n y} - 1 + n y}{y^2} dy. We computed I2 exactly: I2 = - m ( e^{-n/m} - 1 + n/m ) + n \int_0^{n/m} \frac{1 - e^{-t}}{t} dt. = m - n + n \int_0^{n/m} \frac{1 - e^{-t}}{t} dt + o(1). Now, \int_0^{n/m} \frac{1 - e^{-t}}{t} dt = \ln(n/m) + \gamma + \int_{n/m}^\infty \frac{e^{-t}}{t} dt? Wait, earlier we said \int_0^X \frac{1 - e^{-t}}{t} dt = \ln X + \gamma + O(1/X). But let's derive the constant exactly. We know that \int_0^\infty \frac{e^{-t} - 1}{t} dt = -\gamma? Actually, the exponential integral E_1(z) = \int_z^\infty \frac{e^{-t}}{t} dt. And \int_0^z \frac{1 - e^{-t}}{t} dt = \ln z + \gamma + \int_z^\infty \frac{e^{-t}}{t} dt? Let's check: \int_0^z \frac{1 - e^{-t}}{t} dt = \int_0^z \frac{dt}{t} - \int_0^z \frac{e^{-t}}{t} dt. The first part diverges. We need to regularize. The standard identity: \int_0^z \frac{1 - e^{-t}}{t} dt = \ln z + \gamma - \int_z^\infty \frac{e^{-t}}{t} dt? No, that doesn't make sense because \int_z^\infty e^{-t}/t dt is positive. Actually, \gamma = \int_0^1 \frac{1 - e^{-t}}{t} dt - \int_1^\infty \frac{e^{-t}}{t} dt. So \int_0^X \frac{1 - e^{-t}}{t} dt = \int_0^1 \frac{1 - e^{-t}}{t} dt + \int_1^X \frac{1 - e^{-t}}{t} dt = \gamma + \int_1^\infty \frac{e^{-t}}{t} dt + \int_1^X \frac{dt}{t} - \int_1^X \frac{e^{-t}}{t} dt = \gamma + \ln X + \int_X^\infty \frac{e^{-t}}{t} dt. Yes! Because \int_1^\infty \frac{e^{-t}}{t} dt - \int_1^X \frac{e^{-t}}{t} dt = \int_X^\infty \frac{e^{-t}}{t} dt. So \int_0^X \frac{1 - e^{-t}}{t} dt = \ln X + \gamma + \int_X^\infty \frac{e^{-t}}{t} dt. This is exact. Thus I2 = m - n + n ( \ln(n/m) + \gamma + \int_{n/m}^\infty \frac{e^{-t}}{t} dt ) + o(1) = n \ln n - n \ln m - n + n \gamma + m + n \int_{n/m}^\infty \frac{e^{-t}}{t} dt + o(1). Now, \int_{n/m}^\infty \frac{e^{-t}}{t} dt = E_1(n/m) = \frac{m}{n} e^{-n/m} (1 - \frac{m}{n} + \frac{2m^2}{n^2} - ...). So n E_1(n/m) = m e^{-n/m} (1 + O(1/n)) = exponentially small. So I2 = n \ln n - n (\ln m + 1 - \gamma) + m + o(1).
I3 = \int_0^{1/m} \frac{(1-y)^n - e^{-n y}}{y^2} dy. We found I3 = -1/2 + O(1/n). Let's compute I3 more precisely. I3 = \int_0^{1/m} \frac{(1-y)^n - e^{-n y}}{y^2} dy. Change variable t = n y: I3 = n \int_0^{n/m} \frac{(1 - t/n)^n - e^{-t}}{t^2} dt. As n -> \infty, (1 - t/n)^n = e^{-t} e^{-t^2/(2n) - t^3/(3n^2) - ...}. So I3 = n \int_0^\infty \frac{e^{-t} (e^{-t^2/(2n)} - 1)}{t^2} dt + O(1/n)? Actually, we can expand: e^{-t^2/(2n)} - 1 = -t^2/(2n) + t^4/(8n^2) + ... Then n * (e^{-t^2/(2n)} - 1)/t^2 = -1/2 + t^2/(8n) + ... Integrating against e^{-t} dt gives -1/2 + O(1/n). The error from the upper limit n/m is negligible because e^{-t} decays. So I3 = -1/2 + O(1/n). Thus I = \frac{1}{\ln m} ( n \ln n - n (\ln m + 1 - \gamma) + m - 1/2 ) + O(1/n).
Now F(1) = m [ (1 - 1/m)^n - 1 + n/m ] = m (1 - 1/m)^n - m + n. So \frac{1}{2} F(1) = n/2 - m/2 + O(e^{-cn}).
Thus I + \frac{1}{2} F(1) = n \log_m n - n (\ln m + 1 - \gamma)/\ln m + m/\ln m - 1/(2\ln m) + n/2 - m/2 + O(1/n). = n \log_m n - n (1/\ln m + 1 - \gamma/\ln m - 1/2) + m(1/\ln m - 1/2) - 1/(2\ln m) + O(1/n). = n \log_m n - n (1/2 + 1/\ln m - \gamma/\ln m) + m(1/\ln m - 1/2) - 1/(2\ln m) + O(1/n).
Now, the remainder R = \int_1^\infty \overline{B}1(t) F'(t) dt. We need the asymptotic expansion of R up to O(1). We found R = n \int{-\infty}^\infty \overline{B}1(\delta + u) H(u) du + o(n), where H(u) = m^u [ e^{-m^{-u}} - 1 + m^{-u} e^{-m^{-u}} ]? Wait, we had F'(t) dt = n m^u [ e^{-m^{-u}} - 1 + m^{-u} e^{-m^{-u}} ] du. Let's double-check: F'(t) dt = \ln m \cdot m^t [ (1 - m^{-t})^n - 1 + n m^{-t} (1 - m^{-t})^{n-1} ] dt. With t = \log_m n + u, m^t = n m^u, dt = du/\ln m. F'(t) dt = n m^u [ (1 - m^{-u}/n)^n - 1 + m^{-u} (1 - m^{-u}/n)^{n-1} ] du. As n -> \infty, (1 - m^{-u}/n)^n -> e^{-m^{-u}}, (1 - m^{-u}/n)^{n-1} -> e^{-m^{-u}}. So the bracket -> e^{-m^{-u}} - 1 + m^{-u} e^{-m^{-u}} = e^{-m^{-u}} (1 + m^{-u}) - 1. Thus R = n \int{-\infty}^\infty \overline{B}1(\delta + u) [ e^{-m^{-u}} (1 + m^{-u}) - 1 ] m^u du + o(n). Let's simplify the integrand: H(u) = m^u [ e^{-m^{-u}} (1 + m^{-u}) - 1 ] = m^u e^{-m^{-u}} + e^{-m^{-u}} - m^u. As u -> -\infty, m^{-u} -> \infty, e^{-m^{-u}} -> 0, so H(u) ~ - m^u. As u -> +\infty, m^{-u} -> 0, e^{-m^{-u}} ~ 1 - m^{-u} + m^{-2u}/2 - ..., so H(u) ~ m^u (1 - m^{-u} + m^{-2u}/2)(1 + m^{-u}) - m^u = m^u (1 - m^{-2u}/2 + ...) - m^u = - m^{-u}/2 + ... -> 0. The integral \int{-\infty}^\infty H(u) du converges? As u -> -\infty, H(u) ~ - m^u, integral converges. As u -> +\infty, H(u) ~ - m^{-u}/2, integral converges. So the integral is finite.
Now, \int_{-\infty}^\infty \overline{B}_1(\delta + u) H(u) du is a periodic function of \delta. Let's denote it \tilde{P}(\delta). Then R = n \tilde{P}(\delta) + o(n).
But we also know that U = S + T from the direct summation method. Let's compute S + T and see if we can extract the constant term.
S = \sum_{j=1}^J (n - m^j) = J n - \frac{m(m^J - 1)}{m-1}. J = \lfloor \log_m n \rfloor = \log_m n - \delta. m^J = n m^{-\delta}. So S = n \log_m n - \delta n - \frac{m n m^{-\delta} - m}{m-1} = n \log_m n - n [ \delta + \frac{m^{1-\delta}}{m-1} ] + \frac{m}{m-1}.
T = \sum_{k=1}^\infty m^{J+k} [ (1 - m^{-J-k})^n - 1 + n m^{-J-k} ]. m^{J+k} = n m^{k-\delta}. m^{-J-k} = m^{-k-\delta}/n. Term = n m^{k-\delta} [ (1 - m^{-k-\delta}/n)^n - 1 + m^{-k-\delta} ]. As n -> \infty, (1 - m^{-k-\delta}/n)^n -> e^{-m^{-k-\delta}}. So T ~ n \sum_{k=1}^\infty m^{k-\delta} [ e^{-m^{-k-\delta}} - 1 + m^{-k-\delta} ]. Let's denote the sum as \tilde{T}(\delta) = \sum_{k=1}^\infty m^{k-\delta} [ e^{-m^{-k-\delta}} - 1 + m^{-k-\delta} ]. Then T = n \tilde{T}(\delta) + o(n). So U = S + T = n \log_m n - n [ \delta + \frac{m^{1-\delta}}{m-1} ] + \frac{m}{m-1} + n \tilde{T}(\delta) + o(n). Thus the periodic part is n times [ - \delta - \frac{m^{1-\delta}}{m-1} + \tilde{T}(\delta) ]. The constant term from S+T is m/(m-1) + o(1). But wait, the o(1) in T might have a constant term. We approximated T by replacing (1 - x/n)^n with e^{-x}. The error in this approximation for each term is of order O(x^2/n) for small x, and exponentially small for large x. Summing over k, the total error might be O(1). So U = n \log_m n + n P_1(\delta) + C + o(1), where P_1(\delta) = - \delta - \frac{m^{1-\delta}}{m-1} + \tilde{T}(\delta), and C is some constant.
Now, our Euler-Maclaurin expression gave U = n \log_m n + n P_2(\delta) + C_2 + o(n), where P_2(\delta) = \tilde{P}(\delta) - (1/2 + 1/\ln m - \gamma/\ln m)? Wait, we had U = I + 1/2 F(1) + R. The n \log_m n term came from I. The rest of I + 1/2 F(1) gave - n (1/2 + 1/\ln m - \gamma/\ln m) + constant. R gave n \tilde{P}(\delta). So P_2(\delta) = \tilde{P}(\delta) - (1/2 + 1/\ln m - \gamma/\ln m)? But \tilde{P}(\delta) is the integral with \overline{B}_1. It might be exactly equal to P_1(\delta). Let's check if the two expressions for the periodic part are equal.
We have: \tilde{P}(\delta) = \int_{-\infty}^\infty \overline{B}_1(\delta + u) H(u) du, where H(u) = m^u [ e^{-m^{-u}} (1 + m^{-u}) - 1 ].
P_1(\delta) = - \delta - \frac{m^{1-\delta}}{m-1} + \sum_{k=1}^\infty m^{k-\delta} [ e^{-m^{-k-\delta}} - 1 + m^{-k-\delta} ].
Are these equal? This is a known identity. The Euler-Maclaurin formula connects the sum and the integral. In fact, the sum \sum_{j=1}^\infty F(j) = \int_1^\infty F(t) dt + 1/2 F(1) + \int_1^\infty \overline{B}1(t) F'(t) dt. Our F(t) was defined for all t. The sum S + T is exactly the sum over integer j. So the identity must hold exactly. Therefore, the constant terms must match as well. The constant term C from the direct summation is the limit of U - n \log_m n - n P_1(\delta) as n -> \infty. We can compute this constant by evaluating the sum \sum{j=1}^\infty F(j) minus the asymptotic expansion.
Maybe we can find the constant by using the known result for the expected number of nodes in a trie. Let's check if U is related to the internal path length or external path length.
Another approach: The problem might be solved in the literature. Since this is an exercise in Knuth's book, the answer is likely given in the "Answers to Exercises" section. The asymptotic value of U_{mn} is probably something like: U_{mn} = n \log_m n + n \left( \frac{\gamma}{\ln m} - \frac{1}{2} - \frac{1}{\ln m} + \delta(\log_m n) \right) + C + o(1), where \delta is a periodic function. But the problem says "Find the asymptotic value of the function U_{mn} ...". It might be sufficient to give the leading term n \log_m n and the next term n times a periodic function? Or maybe they want the asymptotic expansion up to O(1) meaning the error is O(1), so we need to provide the n \log n term, the n term (including its periodic part), and the constant term? But a periodic function times n is not O(1); it's O(n). "Up to O(1)" usually means the error is O(1). So we need to give an expression that is exact up to an error of O(1). That expression would be n \log_m n + n P(\log_m n) + C + O(1). But if we don't know the exact periodic function and constant, we might just leave it as n \log_m n + n P(\log_m n) + O(1). However, exercise 48 asks for "asymptotic value ... obtaining terms up to O(1)", which usually means the expansion includes all terms that grow with n, and the error is bounded. So we need to find the coefficient of n \log n and the coefficient of n (which may be a periodic function). The constant term would then be the O(1) error? No, if the error is O(1), the constant term is not determined; we only know the expansion up to bounded error. But "terms up to O(1)" means we write the asymptotic series including terms of order 1? Usually "up to O(1)" means the error is O(1), so the last explicit term is the leading term that grows with n, and we don't specify the constant. But exercise 49 says "Extend ... to O(n^{-1})", meaning we include terms up to 1/n. So for exercise 50, we need to give the asymptotic value, likely the leading term and maybe the next term.
Let's look at the original text's analysis of bubble sort. They gave A = n - \sqrt{\pi n/2} + O(1), B = n^2/2 + O(n), C = n^2/2 - (1/2) n \ln n + O(n). They didn't give the constant term for C. So they often stop at the leading terms.
For U_{mn}, the sum is \sum_{k \ge 2} \binom{n}{k} (-1)^k \frac{1}{m^{k-1} - 1}. The leading asymptotic might be n \log_m n? Let's test with m=2: n \log_2 n. For n=7, n \log_2 n = 7 * 2.807 = 19.65, but our U is 13.14. That's not matching. Wait, \log_m n with m=2 is \log_2 7 ≈ 2.807, n log_2 n = 19.65. But our U was ~ n \ln n? n \ln n = 13.62. That's closer. For m=2, \log_m n = \log_2 n, \ln n = \log_2 n * \ln 2. So n \log_2 n = n \ln n / \ln 2 ≈ 13.62 / 0.693 = 19.65. Our U is 13.14, which is close to n \ln n, not n \log_2 n. So the leading term is n \ln n? Let's check our formula: I = n \ln n - n (\ln m + 1 - \gamma) + ... For m=2, \ln m = \ln 2 ≈ 0.693. So I = n \ln n - n (0.693 + 1 - 0.577) + ... = n \ln n - 1.116 n + ... For n=7, n \ln n = 13.62, -1.116*7 = -7.81, sum = 5.81. Plus other terms. Our actual U is 13.14. So the leading term is indeed n \ln n, not n \log_m n? Wait, n \ln n is larger than n \log_m n by a factor of \ln m. For m=2, n \ln n is about 0.693 times n \log_2 n? No, n \log_2 n = n \ln n / \ln 2. So n \ln n = n \log_2 n * \ln 2. Our U for n=7 is 13.14. n \ln n = 13.62. n \log_2 n = 19.65. So U is close to n \ln n, not n \log_2 n. But our I had n \ln n / \ln m? Let's check: I = \frac{1}{\ln m} [ n \ln n - n (\ln m + 1 - \gamma) + ... ] = n \log_m n - n (1 + 1/\ln m - \gamma/\ln m) + ... So I has n \log_m n as the leading term. For m=2, n \log_2 n = 19.65. But our U is 13.1