Chilean mathematician Nicolás Sanhueza-Matamala gave me the following problem:

Problem 1. Prove that for any \(c \leq n/3\) we have: \begin{equation} \sum_{r=1}^c \frac{c^r r^c}{r^{2r}} n^r = O(n^c). \end{equation}

Given that there are two variables involved, \(n\) and \(c\), to avoid confusion (some people were confused by this), let me restate the problem unrolling the big-Oh notation to avoid any potential ambiguities.

Problem 1. Define the function \(F(n, c) = \sum_{r = 1}^c \frac{c^r r^c}{r^{2r}} n^r\). Now prove that there is an absolute constant \(K\) and a natural \(n_0\) such that, for any \(n \geq n_0\) it holds that for every \(c \leq \frac{n}{3}\) we have \begin{equation} F(n, c) \leq K \cdot n^c. \end{equation}

This problem came up in Nicolás’ research in combinatorics, while trying to bound some combinatorial expression. At the end, this particular sub-problem didn’t end up being useful for his project, and thus instead of simply throwing this solution to the trash can, I have decided to put it up here.

My solution.

I now present my solution. If any reader of this blog has a nicer one, I’d be thrilled to check it out! Funnily enough, it is crucial that \(c \leq n/3\), as \(c \leq n/2.5\) would make this proof fail!

Start with the following algebra:

The idea of this part is that we have obtained an expression of the form \(n^c \cdot f(c)\), where \(f(c) = \sum_{r = 1}^{c} \left(\frac{c}{r}\right)^{r} \cdot \left(\frac{1}{3}\right)^{c-r}\). Our goal now is, naturally, to argue that \(f(c)\) is bounded above by a constant. As a first step towards this goal, let us prove first that \(f(c)\) is always increasing. In order to do this consider that

We now propose the following claim, which is equivalent to \(f\) being increasing.

Claim 1. \(f(c+1) - f(c) > 0.\)

Proof of Claim 1. Because of the previous equation for \(f(c+1) - f(c)\), what we want to prove is equivalent to.

\begin{equation} \sum_{r=1}^c \left[\frac{1}{3} \left(\frac{c+1}{c}\right)^{r} - 1\right]\left(\frac{c}{r}\right)^{r} \cdot \left(\frac{1}{3}\right)^{c-r} > -1. \end{equation} In turn, this is equivalent to proving \begin{equation} \sum_{r=1}^c \left[1 - \frac{1}{3} \left(1+\frac{1}{c}\right)^{r} \right]\left(\frac{3c}{r}\right)^{r} < 3^{c} \end{equation} but as \(\left(1+\frac{1}{c}\right)^{r} > 1\), we have that \begin{equation} \left[1 - \frac{1}{3} \left(1+\frac{1}{c}\right)^{r} \right]\left(\frac{c}{r}\right)^{r} < \left[1 - \frac{1}{3} \right]\left(\frac{c}{r}\right)^{r}, \end{equation} and thus our claim is implied by \begin{equation} \sum_{r=1}^c \left(\frac{3c}{r}\right)^{r} < \frac{3^{c+1}}{2}. \end{equation} Let us prove that this is the case by induction on \(c\). For \(c=1\) it is equivalent to \(3 < \frac{9}{2}\), which obviously holds. For the general case consider that \(\begin{align} \sum_{r=1}^{c+1} \left(\frac{3(c+1)}{r}\right)^{r} &= \left(\sum_{r=1}^{c} \left(\frac{3(c+1)}{r}\right)^{r}\right) + 3^{c+1}\\ &= \left(\sum_{r=1}^{c} \left(\frac{3c}{r}\right)^{r} \left(\frac{c+1}{c}\right)^r\right) + 3^{c+1}\\ &\leq \left(\sum_{r=1}^{c} \left(\frac{3c}{r}\right)^{r}e \right) + 3^{c+1}\\ % \tag{Using that $(1+1/c)^r \leq (1+1/c)^c \leq e$}\\ &\leq e \cdot \frac{3^{c+1}}{2} + 3^{c+1}\\ %\tag{Inductive hypothesis}\\ &= 3^{c+1} \left(\frac{e}{2} + 1 \right)\\ &\leq 3^{c+2}. \end{align}\)

Now let us study the ratio \(f(c+1)/f(c)\). We have that \(\begin{align} \frac{f(c+1)}{f(c)} &= \frac{\sum_{r = 1}^{c+1} \left(\frac{c+1}{r}\right)^{r} \cdot \left(\frac{1}{3}\right)^{c+1-r}}{\sum_{r = 1}^{c} \left(\frac{c}{r}\right)^{r} \cdot \left(\frac{1}{3}\right)^{c-r}}\\ &= \frac{1}{3} \cdot \frac{\sum_{r = 1}^{c+1} \left(\frac{c+1}{r}\right)^{r} \cdot \left(\frac{1}{3}\right)^{c-r}}{\sum_{r = 1}^{c} \left(\frac{c}{r}\right)^{r} \cdot \left(\frac{1}{3}\right)^{c-r}}\\ &= \frac{1}{3} \cdot \frac{\left(\sum_{r = 1}^{c} \left(\frac{c+1}{r}\right)^{r} \cdot \left(\frac{1}{3}\right)^{c-r}\right) + 3}{\sum_{r = 1}^{c} \left(\frac{c}{r}\right)^{r} \cdot \left(\frac{1}{3}\right)^{c-r}}\\ &= \frac{1}{3} \cdot \frac{\left(\sum_{r = 1}^{c} \left(\frac{c}{r}\right)^{r} \left(\frac{c+1}{c}\right)^{r} \cdot \left(\frac{1}{3}\right)^{c-r}\right) + 3}{\sum_{r = 1}^{c} \left(\frac{c}{r}\right)^{r} \cdot \left(\frac{1}{3}\right)^{c-r}}. \end{align}\)

Now, using that \((1+\frac{1}{c})^r \leq (1+\frac{1}{c})^c \leq e\) for every positive integer \(c\), we have that \(\begin{align} \frac{f(c+1)}{f(c)} &\leq \frac{1}{3} \cdot \frac{e\left(\sum_{r = 1}^{c} \left(\frac{c}{r}\right)^{r} \cdot \left(\frac{1}{3}\right)^{c-r}\right) + 3}{\sum_{r = 1}^{c} \left(\frac{c}{r}\right)^{r} \cdot \left(\frac{1}{3}\right)^{c-r}}\\ &\leq \frac{e}{3} + \frac{1}{\sum_{r = 1}^{c} \left(\frac{c}{r}\right)^{r} \cdot \left(\frac{1}{3}\right)^{c-r}}. \end{align}\)

Now assume, expecting a contradiction, that there is some positive integer \(C\) such that \(f(C) > 11\). This would imply that \begin{equation} \frac{f(C+1)}{f(C)} \leq \frac{e}{3} + \frac{1}{11} < 0.907 + 0.091 = 0.998 < 1, \end{equation} meaning that \(f(C+1) < f(C)\), which contradicts Claim 1. Therefore, \(f(c) \leq 11\) for every integer \(c\), and thus we have our desired inequality: \begin{equation} \sum_{r = 1}^c \frac{c^r r^c}{r^{2r}} n^r \leq n^{c} \cdot\sum_{r = 1}^{c} \left(\frac{c}{r}\right)^{r} \cdot \left(\frac{1}{3}\right)^{c-r} = n^c \cdot f(c) \leq 11 n^c. \end{equation}