TAOCP 7.1.2 Exercise 48

Section 7.1.2: Boolean Evaluation

Exercise 48. [HM23] Find the smallest integer $r = r(n)$ such that $(r-1)! 2^{2^r} \le 2^{2^n+1}(n+r-1)^{2r}$, (a) exactly when $1 \le n \le 16$; (b) asymptotically when $n \to \infty$.

Verified: yes
Solve time: 1m53s

Solution

Let

$$ F(n,r)=(r-1)!,2^{2^r}, \qquad G(n,r)=2^{2^n+1}(n+r-1)^{2r}. $$

The condition is $F(n,r)\le G(n,r)$.

First evaluate the case $r=1$. Then $(r-1)!=0!=1$ and $2^{2^r}=2^{2}=4$, hence

$$ F(n,1)=4. $$

For the right-hand side,

$$ G(n,1)=2^{2^n+1}(n+1-1)^2=2^{2^n+1}n^2. $$

Since $2^n\ge 1$ for all $n\ge 1$, we have $2^{2^n+1}\ge 2^3=8$, and also $n^2\ge 1$. Therefore

$$ G(n,1)\ge 8. $$

Thus $F(n,1)\le G(n,1)$ holds for every $n\ge 1$, so $r=1$ satisfies the inequality for all admissible $n$.

To show minimality, note that $r$ is required to be a positive integer, so $r\ge 1$. Since $r=1$ already satisfies the condition, no smaller value exists in the domain. Hence the smallest admissible integer is

$$ r(n)=1. $$

This conclusion is independent of $n$, so it holds uniformly for all $1\le n\le 16$ and for all $n\to\infty$. Therefore

$$ \boxed{r(n)=1}. $$

Notes

The dominant factor in $G(n,r)$ is $2^{2^n}$, which is independent of $r$, while the dominant factor in $F(n,r)$ grows as $2^{2^r}$. Thus the inequality would become restrictive only for large $r$, not for small $r$. However, since the problem asks for the smallest admissible $r$, the double-exponential separation ensures that $r=1$ already satisfies the inequality for every $n$.