Sums using the floor function |_ x _|: -- Linear sums -- Problem A0: [GKP88 (3.24) and (3.25)] Let m, n be positive integers then n = |_n/m_| + |_(n+1)/m_| + |_(n+2)/m_| + ... + |_(n+m-1)/m_|, n = |¯n/m¯| + |¯(n-1)/m¯| + |¯(n-2)/m¯| + ... + |¯(n-m+1)/m¯|. Problem A1: [GKP88 (3.26) and Exc 3.17][Knu68 1.2.4 Exc 38][Eng98 Chp 14.6 Problem 60] Let n be a positive integer and x a real number, show |_nx_| = |_x_| + |_x + 1/n_| + |_x + 2/n_| + ... + |_x + (n-1]/n_|. Problem A2: [GKP88 (3.32) 5 pages], [Knu68, 1.2.4 Exc 37], (special case: [Bro75] for x=0, [SCY62] and [Bog96][Eng98 Chp 14.6 Problem 63] for x=0 and n, m coprime) Let m, n be integers, n > 0 and x any real number. Show that |_x/n_| + |_(m+x)/n_| + |_(2m+x)/n_| + ... + |_((n-1)m+x)/n_| = (m-1)(n-1)/2 + (d-1)/2 + d*|_x/d_| with d = gcd(n,m). Note: if m > 0 the formular is symmetric in n and m. Problem A3: [13CMO81 problem 1] Show that the equation |_x_| + |_2x_| + |_4x_| + |_8x_| + |_16x_| + |_32x_| = 12345 has no real solution. Problem A4: [10USA81 problem 5], [KOMAL82] If x is a real number and n is a positive integer, prove that |_nx_| >= |_x_|/1 + |_2x_|/2 + |_3x_|/3 + ... + |_nx_|/n. Problem A5: [Moi92] Let a, b, m, n, are positives integers Sum_{k = 0, m - 1}{[(a + b + k)/n] - [(a + k)/n] - [(b + k)/n] + [k/n]}>=0 Problem A6: [GKP88 Exc 3.38] Let x1, x2, ... xn be real numbers such that the identity |_m x1_| + |_m x1_| + ... + |_m xn_| = |_m (x1 + x2 + ... + xn)_| holds for all positive integers m. Proof at most one xk can be noninteger. Problem A7: [28CMO96 problem 5] Let r1, r2, ..., rm be a given set of m positive rational numbers such that r1 + r2 + ... + rm = 1. Define the function f by f(n) = n - ( |_r1 n_| + |_r2 n_| + ... + |_rm n_| ) for each positive integer n. Determine the minimum and maximum values of f. Problem A8: [PoS24 Vol 2 Part VIII No 79, 80] [Eng98 Chp 14.6 Problem 61][HoR89] If tau(n) is the number of divisors of an integer n, then a(n) = tau(1) + tau(2) + tau(3) + ... + tau(n) = |_n/1_| + |_n/2_| + |_n/3_| + ... + |_n/n_| = 2|_n/1_| + 2|_n/2_| + 2|_n/3_| + ... + 2|_n/v_| - v^2 with v = |_sqrt(n)_|. The number a(n) is the number of positive integer pair (x,y) with xy <= n. Problem A9: [Knu87], [GKP88 Exc 3.37] Prove that |_m*m/n_| + Sum_{k = 0, k = m - 1} ( |_k/n_| - |_(m+k)/n_| ) = |_ min( m mod n, (-m) mod n )^2 / n _| for all positive integers m and n. (Here m mod n = m - |_m/n_|*n.) -- Product sums -- Problem B1: [Moi92, p152] Let p, q be integers and n be a positive integer, prove that _ _ | pq/n | <= |_p/n_||_q/n_| + |_(p+1)/n_||_(q+1)/n_| + ... + |_(p+n-1)/n_||_(q+n-1)/n_| <= |_pq/n + n/4_| -- Sqrt sums -- Problem E1: (a) [Eng98 Chp 14.6 Problem 64] (b) [19CMO87 problem 5] Prove that for all positive integer n |_sqrt(n) + sqrt(n+1)_| = |_sqrt(4n+2)_| (a) |_sqrt(n) + sqrt(n+1)_| = |_sqrt(4n+1)_| = |_sqrt(4n+2)_| = |_sqrt(4n+3)_| (b) Problem E2: [Ham83][Oua00, P2-14] Prove that for all positive integer n |_sqrt(n) + sqrt(n+1) + sqrt(n+2)_| = |_sqrt(9n+8)_| Problem E3: [Eng98 Chp 14.6 Problem 70] Prove that for all positive integer n |_(sqrt(n) + sqrt(n+1) + sqrt(n+2))^2_| = 9n+8 Problem E4: [Ben83] Show that for positive integer p there is a number k0 such that |_(sqrt(k) + sqrt(k+1) + ... + sqrt(k+p))^2_| = (p+1)^2 (2k+p) / 2 - 1 holds for all integers k >= k0. Problem E5: [GKP88 Sect 3.5 (3.27)], [Knu68, 1.2.4 Exc 43] |_sqrt(1)_| + |_sqrt(2)_| + ... + |_sqrt(n-1)_| = n*w - w^3/3 - w^2/2 - w/6 = n*w - w(w + 1/2)(w + 1)/3 with w = |_sqrt(n)_|. Problem E6: [Kor52 problem 2][Parab Q524] Prove that for all positive integer n>1 |_1/sqrt(1) + 1/sqrt(2) + 1/sqrt(3) + ... + 1/sqrt(n*n)_| = 2n-2 Problem E7: |_ 2 sqrt(n+1) / (sqrt(n+1) - sqrt(n)) _| = 4n+2 Problem E8: [Fer96] For any positive integer n and any positive real number a put S_n(a) = Sum_{0<=j=3 |_((n-1)^(1/3) + (n+1)^(1/3))^3_| = 8n - 1 Problem F3: [Ben85] Prove that for all positive integer n |_n^(1/3) + (n+1)^(1/3) + (n+2)^(1/3)_| = |_(27n+26)^(1/3)_| -- Floor sums -- Problem G1: [Kis83] Prove that for any positive integer n |_n^(1/2)_| + |_n^(1/3)_| + |_n^(1/4)_| + .. + |_n^(1/n)_| = |_log_2(n)_| + |_log_3(n)_| + |_log_4(n)_| + ... + |_log_n(n)_|. Problem G2: [Bru78] For all real numbers a>=1 and b>=1, prove that |_b*sqrt(1 - (1/a)^2)_| + |_b*sqrt(1 - (2/a)^2)_| + ... + |_b*sqrt(1 - (|_a_|/a)^2)_| = |_a*sqrt(1 - (1/b)^2)_| + |_a*sqrt(1 - (2/b)^2)_| + ... + |_a*sqrt(1 - (|_b_|/b)^2)_|. Problem G3: [Alf65] Let t = (1 + sqrt(5))/2. Determine a closed expression for |_t_| + |_t^2_| + ... + |_t^n_|. Problem G4: (Sillke) Let t the largest root of x^3 - 2x^2 - x + 1 = 0. It is t = 2.2469796. Determine a closed expression for |_t_| + |_t^2_| + ... + |_t^n_|. -- Log sums -- Problem H: [Knu68, 1.2.4 Exc 42 b] [GKP88 Exc. 3.34 (log2 only with ceiling)], Let the base b be a an integer >= 2 then |_log_b(1)_| + |_log_b(2)_| + ... + |_log_b(n-1)_| = n*w - b*(b^w - 1)/(b-1) with w = |_log_b(n)_|. -- Limits -- Problem L: [Pol17] [PoS24, II.42] "In 1898 de la Vallee Poussin proved that if a large number n is divided by all the primes up to n, then the average fraction by which the quotient falls short of the next whole number is gamma [the Euler-Mascheroni constant], and not 1/2 as you might expect!" lim_{n->oo} 1/n Sum_{k=1..n} ( n/k - |_n/k_| ) = Integral_{0 to 1} (1/x - |_1/x_|) dx = lim_{n->oo} Integral_{1/n to 1} (1/x - |_1/x_|) dx = 1 - lim_{n->oo} (1 + 1/2 + 1/3 + ... + 1/n - log(n)) = 1 - C. Problem L2: Let f(n) = n - [n/2] + [n/3] - [n/4] + ... (this is a finite sum of course). How it can be proved that that f(n)/n -> ln(2) as n goes to infinity ? Problem L3: [NiZ60, 4.1 Exc 14] Let n be a positive integer show Sum_{k = 1, oo} |_ n/2^k + 1/2 _| = n --- S P O I L E R --- Solution A0: Use induction in variable n. Only the floor function is proved. Case n=0: trivial. Case n->n+1: We want to show n+1 = |_(n+1)/m_| + |_(n+2)/m_| + |_(n+3)/m_| + ... + |_(n+m)/m_|. The rhs is rewritten as |_n/m_| + |_(n+1)/m_| + |_(n+2)/m_| + |_(n+3)/m_| + ... + |_(n+m)/m_| - |_n/m_| = n + |_(n+m)/m_| - |_n/m_| = n + |_n/m + 1_| - |_n/m_| = n + 1. Solution A1: [GKP88] Substitute n = [mx] in the equation of problem A0. Then use the simplification |_(|_x_|+m)/n_| = |_(x+m)/n_| for real x and positive integers m, n. Solution A1: [Engel 1998] If 0 <= x < 1/n then the equation is correct since both sides are 0. Now suppose that x is arbitrary. If we increase x by 1/n, each of the terms on the rhs will shift by one place, except the last one, which becomes the first one increased by 1. The lhs also increases by 1. From here it is easy to conclude that the equality holds for any x. Solution A3: write x as a binary fraction x = a0 + a1 / 2 + a2 / 4 + a3 / 8 + a4 / 16 + ... with a0 integral and a1, a2, ... are 0 or 1. Then we can compute b(k,x) := [2^k x] = [2^k a0 + 2^(k-1) a1 + ... ak + delta] with 0 <= delta < 1 = 2^k a0 + 2^(k-1) a1 + ... ak Now we can simplify [x] + [2x] + [4x] + [8x] + [16x] + [32x] = b(0,x) + b(1,x) + b(2,x) + b(3,x) + b(4,x) + b(5,x) = a0 + 2 a0 + a1 + 4 a0 + 2 a1 + a2 + 8 a0 + 4 a1 + 2 a2 + a3 + 16 a0 + 8 a1 + 4 a2 + 2 a3 + a4 + 32 a0 + 16 a1 + 8 a2 + 4 a3 + 2 a4 + a5 = = 63 a0 + 31 a1 + 15 a2 + 7 a3 + 3 a4 + a5. Therefore the range of [x] + [2x] + [4x] + [8x] + [16x] + [32x] is 63*Z + {0,31} + {0,15} + {0,7} + {0,3} + {0,1} = 63*Z + {0,1,3,4,7,8,10,11,15,16,18,19,22,23,25,26, 31,32,34,35,38,39,41,42,46,47,49,50,53,54,56,57} As 12345 = 60 (modulo 63) it is not in the range. Solution A8: In {1,2,...,n} exactly |_n/k_| integers are divisible by k. Thus, the right sum counts the number of integers divisible by 1,2,...,n. The left side does the same. Let S(n) = {(x,y) in N^2 : 0 < xy <= n } then a(n) = #S(n). Let v = |_sqrt(n)_| then by inclusion exclusion a(n) = #{(x,y) in S(n)|x<=v or y<=v} = #{(x,y) in S(n)|x<=v} + #{(x,y) in S(n)|y<=v} - #{(x,y) in S(n)|x<=v and y<=v}. [HoR89] showed that the sum is approximatly n * (log(n) + 2*gamma - 1), where gamma is the Euler-Mascheroni number = 0.57721566490. This follows from the solution of problem L too. [PoS24, II.42] Table: a(n) = tau(1) + tau(2) + ... + tau(n) 1,3,5,8,10,14,16,20,23,27,29,35,37,41,45,50,52,58,60,66,70,74,76,84,87,91,95,101 Solution A9: (Seiffert) Choose the integers j and r, such that m = jn + r, j>=0 and 0<=r p0*q0 <= p0*n (with equality iff p0=0) => p0*q0/n <= p0 (with equality iff p0=0) we have shown the first inequality pq/n <= Sum. To show the second inequality we are looking for upper bound of p0 - p0*q0/n. p0 - p0*q0/n // p0*q0/n is monotonic in q0 and we assumed p0<=q0. <= p0 - p0*p0/n = n * p0/n * (1 - p0/n) // using xy <= (x+y)^2/4 <= n/4 This shows the upper bound Sum <= pq/n + n/4 with equality iff 2p=2q=0 (mod n). Now apply the floor and ceiling function to sharpen the bounds. We use the property that floor and ceiling are monotonic and Sum integral. _ _ _ _ | pq/n | <= | Sum | = Sum = |_Sum_| <= |_pq/n + n/4_|. Solution E1: (Engel and Sillke) Show sqrt(4n+1) <= sqrt(n) + sqrt(n+1) < sqrt(4n+2) for n >= 0. This can be shown by repeated squaring. Upper bound sqrt(n) + sqrt(n+1) < sqrt(4n+2) <=> 2n+1 + 2sqrt(n(n+1)) = (sqrt(n) + sqrt(n+1))^2 < 4n+2 <=> sqrt(n(n+1)) < (n + (n+1))/2. The last is the arithmetic geometric mean inequality sqrt(xy) < (x+y)2. Lower bound sqrt(n) + sqrt(n+1) >= sqrt(4n+1) <=> 2n+1 + 2sqrt(n(n+1)) = (sqrt(n) + sqrt(n+1))^2 >= 4n+1 <=> sqrt(n(n+1)) >= n <=> n(n+1) >= n^2 <=> n >= 0. Now there is no square in the open interval (4n+1, 4n+4) as squares are 0 or 1 modulo 4. Therefore there is an integer k>=0 with k^2 <= 4n+1 < 4n+4 <= (k+1)^2. Let r(n) be a sequence with sqrt(4n+1) <= r(n) < sqrt(4n+4) then k <= sqrt(4n+1) <= r(n) < k+1. Using x<=y => |_x_| <= |_y_| we get k <= |_sqrt(4n+1)_| <= |_r(n)_| <= r(n) < k+1 and this means k = |_sqrt(4n+1)_| = |_r(n)_| as there is no integer between k and k+1. There are many sequences we can use for r. For instance sqrt(4n+d) for some real constant 1<=d<4. And sqrt(n) + sqrt(n+1) is a suitable r. Therefore |_sqrt(4n+d)_| = |_sqrt(n) + sqrt(n+1)_| for every 1<=d<4 and integral n. Solution E2: (Binz) Let x = sqrt(n) + sqrt(n+1) + sqrt(n+2). Then x^2 = 3n+3 + 2(sqrt(n(n+1)) + sqrt(n(n+2)) + sqrt((n+1)(n+2)). For n>=1 the inequalities (n + 2/5 )^2 < n(n+1) < (n + 1/2)^2 (n + 7/10)^2 < n(n+2) < (n + 1 )^2 (n + 7/5 )^2 < (n+1)(n+2) < (n + 3/2)^2 lead to 9n + 8 < x^2 < 9n + 9 and therefore, |_x_| = |_sqrt(9n+8)_|; the case n = 0 is verified directly. Solution E2: (Sillke) First we try to find good bounds for s(n) = sqrt(n-1) + sqrt(n) + sqrt(n+1) with n>=1. s(n) = sqrt(n-1) + sqrt(n) + sqrt(n+1) = sqrt(n) * ( sqrt(1 - 1/n) + 1 + sqrt(1 + 1/n) ). Now we only have to estimate the factor t(1/n) = s(n)/sqrt(n). t(x) = sqrt(1 - x) + 1 + sqrt(1 + x) = 1 + sqrt((sqrt(1 - x) + sqrt(1 + x))^2) = 1 + sqrt(2 + 2 sqrt(1 - x^2)) Knowing that sqrt is monotonic increasing function and using the inequality sqrt(1-y) <= 1 - y/2 we derive the upper bound t(x) <= 1 + sqrt(4 - x^2) = 1 + 2 sqrt(1 - x^2/4) <= 3 - x^2/4. Using y <= sqrt(y) for 0<=y<=1 we get the lower bound t(x) >= 1 + sqrt(4 - 2x^2) = 1 + 2 sqrt(1 - x^2/2) >= 3 - x^2 = sqrt(9 - 6x^2 + x^4) >= sqrt(9 - 6x^2). Therefore we have sqrt(9n - 6/n) <= sqrt(n)*t(1/n) <= (3 - 1/(4n^2)) sqrt(n) < sqrt(9n). For n>=3 we have 6/n <= 2. This yields sqrt(9n-2) <= s(n) < sqrt(9n) for n>=3. Testing n=2 and n=1 we see that this inequality is valid for n=2 too but not for n=1. Now there is no square in the open interval (9n-2, 9n) as 9n-1 = -1 (modulo 3) but squares are 0 or 1 modulo 3. Therefore there is an integer k>=0 with k^2 <= 9n-2 < 9n <= (k+1)^2. Let r(n) be a sequence with sqrt(9n-2) <= r(n) < sqrt(9n) then k <= sqrt(9n-2) <= r(n) < k+1. Using x<=y => |_x_| <= |_y_| we get k <= |_sqrt(9n-2)_| <= |_r(n)_| <= r(n) < k+1 and this means k = |_sqrt(9n-2)_| = |_r(n)_| as there is no integer between k and k+1. There are many sequences we can use for r. For instance sqrt(9n-d) for some real constant 0=2. Checking the case n=1 by hand we have shown |_sqrt(9n-d)_| = |_s(n)_| for every 0= 1. In the same way we get _ _ _ _ | sqrt(9n-d) | = | s(n) | for every 0<=d<2 and integral n >= 1. Table: with apr(n) = (3 - 1/(4n^2)) sqrt(n) n sqrt(9n-2) s(n) apr(n) sqrt(9n) --+-----------+-----------+-----------+---------- 1 2.645751 2.414213 2.750000 3.000000 2 4.000000 4.146264 4.154252 4.242640 3 5.000000 5.146264 5.148039 5.196152 4 5.830951 5.968118 5.968750 6.000000 5 6.557438 6.685557 6.685843 6.708203 6 7.211102 7.331309 7.331458 7.348469 7 7.810249 7.923668 7.923755 7.937253 8 8.366600 8.474178 8.474232 8.485281 9 8.888194 8.990704 8.990740 9.000000 Solution E2: (Sillke) (first part) By the Binomial Theorem we have for x in [0,1] the convergent series sqrt(1+x) = Sum_{k>=0} Binomial(1/2,k) x^k = 1 + 1/2 x - 1/8 x^2 + 1/16 x^3 - 5/64 x^4 + O(x^5) sqrt(1-x) = Sum_{k>=0} Binomial(1/2,k) (-x)^k = 1 - 1/2 x - 1/8 x^2 - 1/16 x^3 - 5/64 x^4 + O(x^5) t(x) = sqrt(1-x) + 1 + sqrt(1+x) = 3 - 1/4 x^2 - 5/32 x^4 + O(x^6) This series is even. All terms are negative except the first. Therefore each partial series is an upper bound of t(x). Define a function e(x) as t(x) = 3 - e(x) x^2. Then e(x) is monotonic increasing as its series has only positive terms. This gives the lower bound 3 - e(1) x^2 <= t(x) for 0<=x<=1. As t(1) = sqrt(2)+1 we get e(1) = 2 - sqrt(2) = 0.58578 Solution E3: (Engel and Sillke) First we try to find good bounds for s(n) = sqrt(n-1) + sqrt(n) + sqrt(n+1) with n>=1. This is the same step as in the problem E2 but now we use the Power-Mean-Inequality as an alternate proof. (x+y)/2 <= Sqrt((x^2+y^2)/2) for x,y>=0 with equality iff x=y. So (sqrt(n-1) + sqrt(n+1))/2 < sqrt(n). This yields the upper bound s(n) < 3sqrt(n). (x+y)/2 >= sqrt(xy) for x,y>=0 with equality iff x=y. So (sqrt(n-1) + sqrt(n+1))/2 > sqrt(sqrt(n^2-1)) and as sqrt(n) > sqrt(sqrt(n^2-1)) we get the lower bound s(n) > 3sqrt(sqrt(n^2-1)). We want to get s(n) > 3sqrt(n - 1/9). Now 3sqrt(sqrt(n^2-1)) > 3sqrt(n - 1/9) <=> n^2-1 > (n - 1/9)^2 <=> n > 41/9. As s(2)>3sqrt(2 - 1/9), s(3)>3sqrt(3 - 1/9), s(4)>3sqrt(4 - 1/9) we have shown 9n-1 < ( s(n) )^2 < 9n for n>=2. This yields 9n-1 = |_(sqrt(n-1) + sqrt(n) + sqrt(n+1))^2_| and _ _ 9n = | (sqrt(n-1) + sqrt(n) + sqrt(n+1))^2 |. Solution E3: (Sillke) Using the bound (see appendix (***)) for the geometric and arithmetic mean we get sharp estimates for the expression s = (sqrt(n) + sqrt(n+1) + sqrt(n+2))^2 = 3n + 3 + 2(sqrt(n(n+1)) + sqrt(n(n+2)) + sqrt((n+1)(n+2))). s >= 3n + 3 + 2((n + 1/2) - 1/(8n) + (n + 1) - 4/(8n) + (n + 3/2) - 1/(8n+8)) > 9n + 9 - 3/(2n) > 9n + 8 for n >= 2. s <= 3n + 3 + 2((n + 1/2) - 1/(8n+4) + (n + 1) - 4/(8n+8) + (n + 3/2) - 1/(8n+12)) < 9n + 9 - 3/(2n+2). For the last inequality we used 2/(a+b) = 1/A <= 1/H = 1/2(1/a + 1/b). Solution E4: (Sillke) By the power mean inequality have the lower bound G (geometric mean) and the upper bound A (arithmetic mean) G = (k(k+1)...(k+p))^(1/(p+1)) <= ((sqrt(k) + sqrt(k+1) + ... + sqrt(k+p))/(p+1))^2 < (2k+p) / 2 = A. Now use the fact that G can be estimated from below (see appendix (**)) A ( 1 - 1/2 V/k^2 ) <= exp(-1/2 V/k^2) A <= G with the variance V = ((k-A)^2 + (k+1-A)^2 + ... + (k+p-A)^2)/(p+1). As the variance is translation invariant we can calculate V for k=0. V = ((0 - p/2)^2 + (1 - p/2)^2 + ... + (p - p/2)^2)/(p+1) = (0^2 + 1^2 + ... + p^2)/(p+1) - (p/2)^2 = p(2p+1)/6 - p^2/4 = p(p+2)/12. ([GKP88, Sect. 2.5] shows 7 ways to find the sum of consecutive squares.) This yields the inequalities (p+1)^2 (2k+p) / 2 (1 - p(p+2)/(24k^2)) <= (sqrt(k) + sqrt(k+1) + ... + sqrt(k+p))^2 < (p+1)^2 (2k+p) / 2 So we are left with the problem to find k such that p(p+1)^2(p+2)(k+p/2)/(24k^2) <= 1. This is a quadratic equation of k k^2 - p(p+1)^2(p+2)(k+p/2)/24 >= 0. (Now x^2-ax-ab >= 0 for x>=a+b, a,b>=0) Let k0 = p(p+1)^2(p+2)/24 + p/2 = Binomial(p+3,4) - Binomial(p+2,3)/2 + p/2. Substituting k = k0 + t into (1) shows that it is valid for t >= 0. Furthermore k0 cannot be lowered by a constant to satisfy (1). The first values show that the found k0 is quite good. p : 1 2 3 4 5 6 7 8 9 10 k0 : 1 4 11.5 27 55 101 171.5 274 417 610 Solution E5: (Sillke) As k = |_sqrt(k^2)_| = |_sqrt(k^2+1)_| = ... = |_sqrt(k^2+2k)_| we have |_sqrt(k^2)_| + |_sqrt(k^2+1)_| + ... + |_sqrt(k^2+2k)_| = k(2k+1). Let w = |_sqrt(n)_| then |_sqrt(1)_| + |_sqrt(2)_| + ... + |_sqrt(w^2-1)_| = Sum_{0<=k=1. Now for x>0 we have ub(x) < ub0(x) <=> 2/3 x sqrt(x + 1/4) < 2/3 (x + 1/8) sqrt(x) <=> x(x+1/4) < (x+1/8)^2. By the binomial theorem we can show that ub(n) = ub2(n) + O(1/n^(5/2)) with ub2(n) = ub0(n) - 1/(192sqrt(n)) + 1/(1536sqrt(n^3)). As the series of sqrt(1 + 1/(4n)) has alternating coefficients we again find ub(n) < ub2(n) < ub0(n). Excercise for the reader, show f(n) <= ub(n) for positive integers. n f lb ub0 ub ---+------+----------+----------+---------- 1 0 0.000000 0.250000 0.245356 2 1 0.649916 1.003469 1.000000 3 2 1.675426 2.108439 2.105551 4 3 3.000000 3.500000 3.497474 5 5 4.580882 5.139899 5.137626 6 7 6.389711 7.002083 7.000000 7 9 8.405881 9.067319 9.065385 8 11 10.613540 11.320647 11.318834 9 13 13.000000 13.750000 13.748288 10 16 15.554805 16.345374 16.343747 11 19 18.269144 19.098301 19.096748 12 22 21.135463 22.001488 22.000000 13 25 24.147186 25.048574 25.047143 14 28 27.298526 28.233940 28.232561 15 31 30.584336 31.552582 31.551248 16 34 34.000000 35.000000 34.998708 17 38 37.541346 38.572123 38.570869 18 42 41.204581 42.265242 42.264022 19 46 44.986237 46.075962 46.074774 20 50 48.883123 50.001157 50.000000 Solution E6: Use the inequality 2(sqrt(n+1)-sqrt(n)) < 1/sqrt(n) < 2(sqrt(n)-sqrt(n-1)). The explanation is the 1/sqrt(n+1) < Integral_{t from n to n+1} 1/sqrt(t) dt < 1/sqrt(n). Solution E7: (Sillke) 2 sqrt(n+1) / (sqrt(n+1) - sqrt(n)) = 2 / (1 - 1/sqrt(1 + 1/n)) The Binomial theorem gives (1 + x)^(-1/2) = Sum_{k>=0} Binomial( -1/2, k ) * x^k = 1 - 1/2 x + 3/8 x^2 - 5/16 x^3 + O(x^4) 2 / (1 - 1/sqrt(1 + x)) = 4/x + 3 - 1/4 x + O(x^2) So we get the asymptotic expansion 2 sqrt(n+1) / (sqrt(n+1) - sqrt(n)) = 4n + 3 - 1/(4n) + O(1/n^2) which shows that the upper bound will be quite sharp. For n >= 0 we will show the inequality 4n + 2 <= 2 sqrt(n+1) / (sqrt(n+1) - sqrt(n)) < 4n + 3. Let us define f(z) = 2 sqrt(z+1) / (sqrt(z+1) - sqrt(z)) = 2/(1-1/sqrt(1+1/z)) for z>0 and f(0) = 2. Now f(z) > 4z+2 <=> sqrt(1 + 1/z) < 1 + 1/(2z) <=> 1 + 1/z < 1 + 1/z + 1/(2z)^2 for z > 0. And f(z) < 4z+3 <=> sqrt(1 + 1/z) > 1 + 1/(2z + 1/2) <=> 1 + 1/z > 1 + 4/(4z + 1) + 4/(4z + 1)^2 <=> 16z^2 + 8z < (4z + 1)^2. After checking z=0 we get 4n + 2 <= f(n) < 4n + 3 with equality iff n=0. And we are done. For z>=1 we can improve the lower bound although we don't need it f(z) > 4z + 3 - 1/(4z) <=> sqrt(1 + 1/z) < 1 + 1/(2z + 1/2 - 1/(8z)) <=> (2z + 1/2 - 1/(8z))^2 < 4z^2 + 2z - 1/4 <=> 0 < 1/(8z) - 1/(8z)^2 <= z>1/8. Solution E9: [Oau00 Problem 2-14] Problem E2 shows that f(n) = |_sqrt(9n+8)_| - |_sqrt(9n+1)_|. (a) Now we show that the range of f for positive integers is V = {0, 1}. As sqrt(9x + 8) <= sqrt(9x + 1) + 1 <=> 3 <= sqrt(9x + 1) <=> 8/9 <= x we have sqrt(9n + 1) <= sqrt(9n + 8) <= sqrt(9n + 1) + 1 for n >= 1. This gives |_sqrt(9n + 1)_| <= |_sqrt(9n + 8)_| <= |_sqrt(9n + 1)_| + 1 and subtracting |_sqrt(9n + 1)_| we get 0 <= f(n) <= 1. (Further f(0) = 1). (b) f(n) = 1 if and only if n is of the form 9k^2 + 4k, 9k^2 + 14k + 5, 9k^2 + 8k + 1, 9k^2 + 10k + 2 for an integer k>=0. Solution F1: (Con Amore Problem Group) By the power mean inequality we have (n + (n+1))/2 > ((n^(1/3) + (n+1)^(1/3))/2)^3 > sqrt(n*(n+1)) and consequently, (8n + 4)^(1/3) > n^(1/3) + (n+1)^(1/3) > (64n^2 + 64n)^(1/6) > (64n^2 + 48n + 9)^(1/6) = (8n + 3)^(1/3) Moreover the existence of a positive integers n and k such that (8n + 5)^(1/3) > k > (8n + 3)^(1/3) would imply 8n + 5 > k^3 > 8n + 3 that mean 8n + 4 = k^3 which is impossible as even cubic residues modulo 8 must be 0. We conclude that for 3 <= d < 5 |_ n^(1/3) + (n+1)^(1/3) _| = |_ (8n + d)^(1/3) _|. Solution F1: (David Callan) We claim that 8n + 3 and (n^(1/3) + (n+1)^(1/3))^3 have the same integral part. The desired result follows since |_a_| = |_b_| readily implies |_a^(1/3)_| = |_b^(1/3)_|. Now (n^(1/3) + (n+1)^(1/3))^3 = 2n + 1 + 3n(1 + 1/n)^(1/3) + 3n(1 + 1/n)^(2/3). For n>=1, the latter two summands each have a binomial expansion that is alternating, decreasing after the second term. The binomial expansion (1+x)^p = 1 + p x + p(p-1)/2 x^2 + O(x^3) with exponent 0 < p < 1 is alternating after the second term and absolute convergent for |x| <= 1. Using the familiar "first omitted term" error estimate, we find 3n(1 + 1/n)^(1/3) = 3n + 1 - e1 with 0 < e1 < 1/(3n) and 3n(1 + 1/n)^(2/3) = 3n + 2 - e2 with 0 < e2 < 1/(3n) and the claim follows. Solution F2: (Sillke) Let f(n) = ((n-1)^(1/3) + (n+1)^(1/3))^3. We will show the better bounds 8n - 3/n < f(n) < 8n - 8/(3n) for n>=2 (the upper bound even for n>=1). By the binomial theorem we have (1+x)^(1/3) = 1 + 1/3 x - 1/9 x^2 + O(x^3). Therefore f(n) = n ((1-1/n)^(1/3) + (1+1/n)^(1/3))^3 = 8n (1 - 1/(9n^2) + O(1/n^4))^3 = 8n - 8/(3n) + O(1/n^3). The order gets better as each second term cancels. We found a very close approximation for n large. Let b(n) = 8n - 8/(3n). When is b(n) = f(n)? 8n - 8/(3n) = f(n) = ((n-1)^(1/3) + (n+1)^(1/3))^3 = 2n + 3 (n^2 - 1)^(1/3) ((n-1)^(1/3) + (n+1)^(1/3)) => (6n - 8/(3n))^3 = 27 (n^2 - 1) f(n) = 27 (n^2 - 1) (8n - 8/(3n)) => (3n^2 - 4/3)^3 = 27 n^2 (n^2 - 1) (n^2 - 1/3) for n != 0 Expanding the terms and canceling gives 16n^2 - 64/27 = 9n^2 => n^2 = 64/(7*27) > 1/3. Therefore we have only one positive root n. Now 7/12 > n = sqrt(64/(7*27)). Checking n=1 we see 2 = f(1) < b(1) = 16/3. This yields the inequality f(n) < b(n) for n >= 7/12. Let c(n) = 8n - 3/n. When is c(n) = f(n)? The same derivation as for the function b(n) gives after expanding the terms and canceling n^4 - 3 n^2 + 1 = 0. The largest root is n = (1 + sqrt(5))/2 the golden ratio. As c(n) is smaller then f(n) for large n it is a lower bound for all n larger then this root. Thus we have shown that 8n - 1 <= c(n) < f(n) < b(n) < 8n for n >= 3 as required. Let ap(n,d) = 8n - d/n then the table shows how good the approximation is. n 8n-1 ap(n,3) f(n) ap(n,8/3) --+------+----------+----------+----------- 1 7 5.000000 2.000000 5.333333 2 15 14.500000 14.567000 14.666667 3 23 23.000000 23.083933 23.111111 4 31 31.250000 31.322170 31.333333 5 39 39.400000 39.461019 39.466667 6 47 47.500000 47.552308 47.555556 7 55 55.571429 55.617011 55.619048 8 63 63.625000 63.665305 63.666667 9 71 71.666667 71.702749 71.703704 10 79 79.700000 79.732638 79.733333 Solution F2: (Engel) It suffices to prove that 8n - 1 < ((n-1)^(1/3) + (n+1)^(1/3))^3 < 8n for n >= 3 is equivalent to 6n - 1 < 3(((n-1)(n-1)(n+1))^(1/3) + ((n-1)(n+1)(n+1))^(1/3)) < 6n. Now find bounds for the two cube roots. We find upper bounds by the arithmetic geometric inequality with 3((n-1)(n-1)(n+1))^(1/3) < (n-1)+(n-1)+(n+1) = 3n - 1 and 3((n-1)(n+1)(n+1))^(1/3) < (n-1)+(n+1)+(n+1) = 3n + 1. Then show that for n>=3 we have the lower bounds (3n - 1.5)^3 < 27(n-1)(n-1)(n+1) and (3n + 0.5)^3 < 27(n-1)(n+1)(n+1). This is easy to check as the difference of the rhs and the lhs is a polynomial of 2nd order. So calculating the values at -1, 1, 3 show changing signs. This is sufficient. Solution G1: Let A(n) = {(x,y) in ZxZ : 2<=x, 2<=y, x log(y) <= log(n)}. Now #A(n) can be determined by counting row or column wise. The summation about x gives (positive terms for x <= log_2(n)) |_n^(1/2)-1_| + |_n^(1/3)-1_| + |_n^(1/4)-1_| + .. + |_n^(1/n)-1_|. The summation about y gives (positive terms for y <= sqrt(n)) |_log_2(n)-1_| + |_log_3(n)-1_| + |_log_4(n)-1_| + ... + |_log_n(n)-1_|. Adding n on both sumes gives the desired equation. Solution G2: Let A(a,b) = {(x,y) in ZxZ : 1<=x, 1<=y, (x/a)^2 + (y/b)^2 <= 1}. Now #A(a,b) can be determined by counting row or column wise. This gives the desired equation. Solution G3: The solution is related to the Lucas numbers V. We need the properties V(0) = 2, V(1) = 1, V(n+1) = V(n) + V(n-1) (recurence) V(n) = t^n + s^n (formular) with x^2 - x - 1 = (x - t)(x - s) where t = (1 + sqrt(5))/2 = 1.6180339887, s = (1 - sqrt(5))/2 = -0.6180339887. Now V(n) and |_t^n_| are almost the same as (n even) t^n < V(n) <= t^n + 1, t^n < |_t^n_| + 1 <= t^n + 1 => V(n) = |_t^n_| + 1. (n odd ) t^n - 1 < V(n) <= t^n, t^n - 1 < |_t^n_| <= t^n => V(n) = |_t^n_|. Therefore V(1) + V(2) + ... + V(n) = |_t_| + |_t^2_| + ... + |_t^n_| + |_n/2_|. Using the recurence relation V(n) = V(n+2) - V(n+1) we can simplify V(n) + ... + V(2) + V(1) = V(n+2) - V(n+1) + ... + V(4) - V(3) + V(3) - V(2) = V(n+2) - V(2) = V(n+2) - 3. So we get |_t_| + |_t^2_| + ... + |_t^n_| = V(n+2) - |_n/2_| - 3 = = t^(n+2) + s^(n+2) - n/2 + (1 - (-1)^n)/4 - 3. Solution G4: V(0) = 3, V(1) = 2, V(2) = 6, V(n+1) = 2V(n) + V(n-1) - V(n-2) (recurence) V(n) = t^n + s^n + r^n (formular) with x^3 - 2x^2 - x + 1 = (x - t)(x - s)(x - r) t = 1/(1 - r) = 2.246979603717467 = [2,4,20,2,3,1,6,10,5,..] s = 1/(1 - t) = -0.801937735804838 = - [0,1,4,20,2,3,1,6,10,5,..] r = 1/(1 - s) = 0.554958132087371 = [0,1,1,4,20,2,3,1,6,10,5,..] Let S(n) = |_t_| + |_t^2_| + ... + |_t^n_| and T(n) = V(1) + V(2) + ... + V(n) = (t^(n+1) - 1)/(t - 1) + (s^(n+1) - 1)/(s - 1) + (r^(n+1) - 1)/(r - 1) - V(0) = (-s)*t^(n+1) - r*s^(n+1) - t*r^(n+1) + V(1) - V(0) Now V(n) and |_t^n_| are almost the same and therefore we get S(n) = T(n) - |_n/2_|. n t^n V(n) S(n) T(n) ---+------------+--------+--------+-------- 1 2.247 2 2 2 2 5.049 6 7 8 3 11.345 11 18 19 4 25.492 26 43 45 5 57.279 57 100 102 6 128.705 129 228 231 7 289.197 289 517 520 8 649.820 650 1166 1170 9 1460.132 1460 2626 2630 10 3280.887 3281 5906 5911 Solution L2: (David C. Ulrich) Presumably we already know that 1 - 1/2 + 1/3 ... = log(2). Seems like you should be able to derive what you need from a few facts: (i) [n/k] / n -> 1/k as n->infinity (for k fixed) (ii) 0 <= [n/k] / n <= 1/k (iii) [n/(k+1)] <= [n/k] (iv) If you have an alternating series (terms alternate in sign and are non-increasing in absolute value) then the absolute value of the difference between the sum and a partial sum is no larger than the absolute value of the first omitted term. I'd let eps > 0, then choose N so 1/N < eps. Now if n > N then the difference between f(n)/n and 1 - [n/2] / n + [n/3] / n - ... +- [n/N] / N is less than 1/N < eps in absolute value, similarly the difference between 1 - 1/2 + 1/3 - ... +- 1/N and log(2) is less than eps. (Both of these estimates follow from (iv); (ii) and (iii) show that we can apply (iv) here.) And now if n is large enough (possibly has to be much larger than N) the difference between those two finite sums is also less than eps by (i) (note that N is fixed!) So if n is large enough then the difference between f(n)/n and log(2) is less than 3*eps. Almost good enough. Appendix: [PeM82] Let x[1], x[2], ..., x[n] be positive real numbers with arithmetic mean A = (x[1] + x[2] + ... + x[n])/n, geometric mean G = (x[1] * x[2] * ... * x[n])^(1/n), and variance V = ((x[1]-A)² + (x[2]-A)² + ... + (x[n]-A)²)/n. If M = max(x[1], x[2], ..., x[n]) and m = min(x[1], x[2], ..., x[n], then exp(1/2 V/M²) <= A/G <= exp(1/2 V/m²) (*) exp(-1/2 V/m²) A <= G <= exp(-1/2 V/M²) A (**) Proof: We use a simple application of Taylor's formular with Lagrange's remainder: f(x) = f(a) + (x-a) * f'(a) + (x-a)²/2 * f''(w) with w between x and a. Apply this formular for the function f = ln. For a, b in [m,M], there is a value w in [m,M] such that ln(b) = ln(a) + (b-a)/a - (b-a)²/(2w²). (1) Summing the inequalities m <= x[i] <= M over i in 1..n we get m <= A <= M. To proceed, take a = A and let b = x[i]. The value of w in [m,M] corresponding to x[i] will be denoted w[i]. Then (1) becomes ln(x[i]) = ln(A) + (x[i]-A)/A - (x[i]-A)²/(2w[i]²), which can be rewritten (x[i]-A)²/(2w[i]²) = ln(A) - ln(x[i]) + (x[i]-A)/A. Applying the inequality m <= w[i] <= M to the left side we get (x[i]-A)²/(2M²) <= ln(A) - ln(x[i]) + (x[i]-A)/A <= (x[i]-A)²/(2m²). Summing these inequalities over i in 1..n, we obtain n*V/(2M²) <= n*ln(A) - ln(x[1] * x[2] * ... * x[n]) <= n*V/(2m²). Dividing by n yields V/(2M²) <= ln(A/G) <= V/(2m²) which yields (*) as asserted. As V >= 0 we notice 1 <= exp(1/2 V/M²) <= A/G, we obtain the classical A.M.-G.M. inequality G <= M. Further G = A if and only if V = 0 (i.e. if and only if x[1] = x[2] = ... = x[n]). Let a >= b > 0 and A=A(a,b)=(a+b)/2, G=G(a,b)=sqrt(ab), H=H(a,b)=2ab/(a+b) then (a-b)^2/(8A) <= A - G <= (a-b)^2/(8G). (***) Proof: Using H <= G <= A and G*G = A*H we get H <= H(A,H) <= G(A,H) = G <= A(A,H) <= A. A - G >= A - A(A,H) = (A-H)/2 = (a-b)^2/(8A). G - H <= A(A,H) - H = (A-H)/2 = (a-b)^2/(8A). As G*(G-H) = H*(A-G) we get A - G <= (a-b)^2/(8G). |Binomial[x,n]| = |x(x-1)(x-2)...(x-n+1)|/n! = x(x-1)...(x-|_x_|)(|_x_|+1-x)...(n-1-x)/n! with x < n <= x(x-1)...(x-|_x_|) 1 2 ... (n-1-|_x_|)/n! = x(x-1)...(x-|_x_|) / ((n-|_x_|)(n-|_x_|+1)...n) Example: Let 0 < x < 1 then |Binomial[x,n]| <= x/n. With the help of the gamma function one can show that |Binomial[x,n]| = O(1/n^(1+x)). References: 10USA81: 10. U.S.A. Mathematical Olypiad (1981-05-05) (reprinted: Mathematics Magazine 54:3 (May 1981) 153 Problems 54:5 (Nov. 1981) 278-279 Solutions) 13CMO81: 13. Canadian Mathematical Olypiad (1981-05-06) (reprinted: Mathematics Magazine 54:3 (May 1981) 153 Problems 54:5 (Nov. 1981) 279-280 Solutions) 19CMO87: 19. Canadian Mathematical Olympiad (1987-??-??) 28CMO96: 28. Canadian Mathematical Olympiad (1996-??-??) Alf65: U. Alfred; B-79, Fibonacci Quarterly 3 (1965) 324 proposal by U. Alfred Ban93: Seung-Jin Bang; P1410 Floor function Mathematics Magazine 65:5 (Dec 1992) 348 proposal by Seung-Jin Bang Mathematics Magazine 66:5 (Dec 1993) 341 solutions Con Amore, David Callan Ben83: Mih\'aly Bencze; F 2423 Kozepiskolai Mathematikai Lapok, 67 (1983) 222 Ben85: Mih\'aly Bencze; P 11 Canadian Mathematical Society Notes 17:5 (1985) 8 Bog96: Alexander Bogomolny; The Floor Function, www.cut-the-knot.com/arithmetic/whole_part.html Bro75: Alfred Brousseau; Q628, Mathematics Magazine 48 (1975) 295 & 302 Bru78: Paul S. Bruckman; B-377: Counting lattice points, Fibonacci Quarterly 16 (1978) 184 proposal by Paul S. Bruckman Fibonacci Quarterly 17 (1979) 185 solutions J. M. Metzger Eng98: Arthur Engel; Problem-solving strategies, Problem Books in Mathematics. New York, NY: Springer. x, 403 p. (1998) ISBN 0-387-98219-1/hbk Zbl 887.00002 Chap 14.6 Integer Function Fer89: Peter J. Ferraro; E3317 Proposal: AMM 96(1989)254 by Peter J. Ferraro GKP88: Ronald L. Graham, Donald E. Knuth, Oren Pataschnik; Concrete Mathematics, Addison Wessley, Reading (1994) 2nd Ed. Chap 3: Integer Functions Sect 3.1: Floors and Ceilings Sect 3.2: Floor/Ceiling Applications Sect 3.3: Floor/Ceiling Recurrences Sect 3.4: Mod: the Binary Operation Sect 3.5: Floor/Ceiling Sums Ham83: F. David Hammer; AMM 90 (1983) 483 proposal by David Hammer AMM 95 (1988) 133 solution by J. C. Binz, James Propp Problem E3010 HoR89: L. Hoehn and J. Ridenhour; Summations involving computer-related functions, Mathematics Magazine, 62 (1989), 191-196. Ive62: K. E. Iverson, A programming language, Wiley, 1962. (invents the notation |_ _|) Kis883: V. V. Kisil; M801, Kvant (1983/5) 44 proposal by V. V. Kisil Kvant (1983/8) 50 solution Knu68: Donald E. Knuth; The Art of Computer Programming Vol. 1, Fundamental Algorithms, Addison Wessley, Reading (1973) 2nd Ed. Chapter 1.2.4: Integer Functions and Elementary Number Theory Excercise 1.3.2.16-17 fixed precision harmonic series Knu87: Donald E. Knuth; Problem 1280: Floor function identity, Mathematics Magazine, 60 (1987) 329 proposal by Donald E. Knuth Mathematics Magazine, 61 (1988) 319 solution by H.-J. Seiffert KOMAL82: P 363 Kozepiskolai Mathematikai Lapok, 64 (1982) 223 Kor52: P. P. Korowkin; Ungleichungen, Berlin, Deutscher Verlag der Wissenschaften, 19?? Kleine Erg\"anzungsreihe zu den Hochschulb\"uchern der Mathematik, Band 4. (russion edition: Moskow 1952) Moi82: Luc Moisotte 1932 exercices de mathematiques pour l'oral du CAPES de mathématiques et des concours des Grandes Ecoles. Dunod Université 1982 Paris NiZ60: Ivan Niven, Herbert S. Zuckerman; An Introduction to the Theory of Numbers, John Wiley, New York (1972) 3rd edition. (1st edition (1960)) (german: Einf\"uhrung ind die Zahlentheorie I, BI 46 (1976)) Chap 4: Functions in Number Theory Sect 4.1: The Function [x] Oua00: Abderrahim Ouardini; Mathématiques de Compétition, 112 problèmes corrigés, Ed. Ellipse, 2000, Paris, ISDN 2-7298-0125-1 PeM82: M. Perisastry, V. N. Murty Bounds for the Ratio of the Arithmetic Mean to the Geometric Mean The College Mathematical Journal 13:2 (1982) 160-161 PARAB82: Q 524, Parabola 18 (1982/1) 22 proposal Parabola 18 (1982/3) 34 solution Pol17: George P\'olya; Archiv der Mathematik und Physik, Serie 3, 26 (1917) 196-201 PoS24: George P\'olya and Gabor Szeg\"o; Problems and Theorems in Analysis, vol. I, Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen. Band 193. Springer-Verlag, 1972, (german: Aufgaben und Lehrs\"atze aus der Analysis I, Springer-Verlag, 1924) Zbl 236.00003 Band II, Abschnitt VIII: Zahlentheorie Band II, Abschnitt VIII Kapitel 1: Zahlentheoretische Funktionen SCY62: D. O. Shklarsky, N. N. Chentzov, I. M. Yaglom; The USSR Olympiad Problem Book, Freeman 1962 Tue99: Hans J. H. Tuenter; Another problem for Carl Friedrich: on the sums Sum_{i=1..n} ceil(i/p) and Sum_{i=1..n} floor(i/p) Mathematical Gazette 83:498 (Nov. 1999) 495-496 Tue00: Hans J. H. Tuenter; On the sums Sum_{i=1..n} ceil(i/p)^m and Sum_{i=1..n} floor(i/p)^m Pi Mu Epsilon Journal 11:2 (2000) 97-99 Nick-52: Nick Hobson; Floor function sum, Nick's Mathematical Puzzles 52, http://www.qbyte.org/puzzles/p052s.html solution Let n be a positive integer and x a real number, show |_nx_| = |_x_| + |_x + 1/n_| + |_x + 2/n_| + ... + |_x + (n-1]/n_|. -- http://www.mathematik.uni-bielefeld.de/~sillke/ mailto:Torsten.Sillke@uni-bielefeld.de