On this page
If you have ever stared at a sum like ⌊(n+1)/2⌋ + ⌊(n+2)/4⌋ + ⌊(n+4)/8⌋ + … and started working out terms one by one, this identity is the shortcut. The proof takes two cases, and once you know it, many greatest integer problems from school, JEE Main, JEE Advanced and olympiad practice shrink to a few lines.
What is Hermite's identity?
Hermite's identity, named after the French mathematician Charles Hermite, says that ⌊x⌋ + ⌊x + 1/n⌋ + ⌊x + 2/n⌋ + … + ⌊x + (n−1)/n⌋ = ⌊nx⌋ for every real number x and every positive integer n (Hermite's identity, Wikipedia).
The symbol ⌊x⌋ is the floor, or greatest integer function: the largest integer not exceeding x. Indian textbooks often write it as [x], the square-bracket notation Carl Friedrich Gauss introduced in 1808; Kenneth Iverson introduced the names floor and ceiling, and the ⌊x⌋ symbol, in his 1962 book A Programming Language (Floor and ceiling functions, Wikipedia). If the graph of [x] still feels shaky, read our guide to greatest integer and fractional part functions first.
Put n = 2 and you get the version this post is about: ⌊x⌋ + ⌊x + 1/2⌋ = ⌊2x⌋.
How do you prove ⌊x⌋ + ⌊x + 1/2⌋ = ⌊2x⌋?
Split x into its integer and fractional parts: x = m + f, where m is an integer and 0 ≤ f < 1. An integer passes straight through a floor, so everything depends on f, and there are only two cases.
If 0 ≤ f < 1/2: ⌊x⌋ = m, and f + 1/2 < 1, so ⌊x + 1/2⌋ = m. The left side is 2m. On the right, 2x = 2m + 2f with 2f < 1, so ⌊2x⌋ = 2m.
If 1/2 ≤ f < 1: ⌊x⌋ = m, and 1 ≤ f + 1/2 < 3/2, so ⌊x + 1/2⌋ = m + 1. The left side is 2m + 1. On the right, 1 ≤ 2f < 2, so ⌊2x⌋ = 2m + 1.
The two sides agree in both cases, so the identity holds for every real x, negatives included. Check x = −0.3: ⌊−0.3⌋ + ⌊0.2⌋ = −1 + 0 = −1, and ⌊−0.6⌋ = −1.
The general case works the same way: at x = m both sides equal nm, and both go up by 1 at exactly the points m + 1/n, …, m + (n−1)/n.
How does it simplify floor sums?
The classic test is Problem 6 of the 1968 International Mathematical Olympiad, which asks you to evaluate, for every natural number n, the sum ⌊(n+1)/2⌋ + ⌊(n+2)/4⌋ + ⌊(n+4)/8⌋ + …, whose k-th term is ⌊(n + 2^k)/2^(k+1)⌋ (IMO 1968 problem set, PDF).
Rewrite each term: (n + 2^k)/2^(k+1) = n/2^(k+1) + 1/2. With x = n/2^(k+1), the term is ⌊x + 1/2⌋.
Apply the identity: ⌊x + 1/2⌋ = ⌊2x⌋ − ⌊x⌋ = ⌊n/2^k⌋ − ⌊n/2^(k+1)⌋.
Write out the sum: (⌊n⌋ − ⌊n/2⌋) + (⌊n/2⌋ − ⌊n/4⌋) + (⌊n/4⌋ − ⌊n/8⌋) + … and every middle term cancels.
Deal with the tail: once 2^(k+1) > n, ⌊n/2^(k+1)⌋ = 0, so nothing is left over. The sum is ⌊n⌋ = n.
Check with n = 10: ⌊11/2⌋ + ⌊12/4⌋ + ⌊14/8⌋ + ⌊18/16⌋ + ⌊26/32⌋ = 5 + 3 + 1 + 1 + 0 = 10.
Sums of ⌊n/2^k⌋ also drive Legendre's formula, so read our post on the highest power of 2 dividing 100! next.
Where else does the identity show up?
Equations: ⌊x⌋ + ⌊x + 1/2⌋ = 7 becomes ⌊2x⌋ = 7, so 7 ≤ 2x < 8, which gives 3.5 ≤ x < 4.
Three-term sums: ⌊5.8⌋ + ⌊5.8 + 1/3⌋ + ⌊5.8 + 2/3⌋ = 5 + 6 + 6 = 17, and ⌊3 × 5.8⌋ = ⌊17.4⌋ = 17.
Graphs: y = ⌊x⌋ + ⌊x + 1/2⌋ is simply the staircase y = ⌊2x⌋, with steps of width 1/2. Compare it with our guide to graphing the greatest integer function.
How should you practise Hermite's identity?
Prove the n = 2 case from a blank page, using the two cases above.
Prove the n = 3 case the same way, with three cases for f.
Do the IMO sum for n = 37 term by term, then by telescoping, and check that both give 37.
Solve ⌊x⌋ + ⌊x + 1/3⌋ + ⌊x + 2/3⌋ = 20. Answer: ⌊3x⌋ = 20, so 20/3 ≤ x < 7.
If a step will not come, the Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning rather than printing an answer. For the definitions underneath, the Fermi Concept Library gives every mathematics concept its own lesson.
