--I won't explain "why this is perfectly obvious"... but the fact k^2 is the correct leading term can be seen as "obvious" to some degree essentially because maxima behave like quadratics. More precisely, the binomial function has a max and mean at n/2 and it has std deviation of order n (exactly n? anyhow exactly known) and the quadratic approximation that agrees with those facts plus the fact the binomial is always integer valued is enough to see you aren't going to be able to get any valley between the peaks if n>LargeEnoughConst*k^2. (The sum of two concave-down quadratics, or indeed of any two concave-down functions, is concave-down. The binomial function is concave down if we stay in a region near enough to its max, and is approximately quadratic there.) Now I would think by using stirling series you could probably with enough effort extract all the higher order terms you want, given that you found 3 terms using numerical hogwash.