I am learning about statistical design of experiments, and in the process of mathematically rigorizing the concepts behind fractional factorial designs of resolution III, I derived an interesting equation:
$$k = \sum_{i=1}^{3}{\lceil{\log_2{k}}\rceil \choose i},$$ for which the solutions $k$ are the Mersenne primes.
How can I show this? Is the above equation algebraic? Is it even solvable analytically?
Recall that a Mersenne prime $k$ is of form $k=2^n-1$ for some positive integer $n$. Then the ceiling function in the RHS becomes $\lceil{\log_2 k}\rceil=\lceil{\log_2{(2^n-1)}}\rceil=\lceil{n+\log_2{(1-2^{-n})}}\rceil$, with the logarithmic term being negative since $1-2^{-n}<1$ for positive $n$. To bound its size, note that
$$\dfrac{d}{dx}\log_2(1-2^{-x})=\dfrac{d}{dx}\frac{\log(1-e^{-x\log 2})}{\log 2}=\frac{e^{-x\log 2}}{1-e^{-x\log 2}}=\frac{1}{2^x-1}>0$$ for $x>0$. Consequently $\log_2(1-2^{-x})$ will be increasing on $[1,\infty)$ and so is bounded below on this interval by its value at $x=1$ i.e. $\log_2(1-2^{-x})>\log_2(1-2^{-1})=-1$. Thus $n-1<n+\log_2{(1-2^{-n})}<n$, so the ceiling function just evaluates to $n$.
Hence the proposed identity simplifies to $$k=2^n-1=\sum_{i=1}^3 \binom{n}{i}=n+\frac{1}{2}n(n-1)+\frac{1}{6}n(n-1)(n-2).$$ But (as noted by Steven Stadnicki in his comments above) the LHS grows exponentially in $n$ while the RHS goes only as $n^3$. Hence this relationship fails for sufficiently large $n$; indeed, for $n=5$ we have $2^5-1=31$ (which is prime) but the RHS sums to $5+10+10=25$. So while the statement is true for small Mersenne primes, it is false for any Mercenne primes at least as big as $31$.
However, suppose we modify the upper bound on the sum from $3$ to $n$. In that case, one may check that the $n=5$ case gives $\sum_{i=1}^5 \binom{5}{i}=31=2^n-1$. To explain this, we recall that the binomial theorem states that $(1+x)^n = \sum_{i=0}^n \binom{n}{i}x^i$. For $x=1$, this gives $2^n=\sum_{i=0}^n \binom{n}{i}$ which (shifting the $i=0$ term, which is $1$, to the LHS) gives the promised identity.
To conclude, this means that a valid statement for any Mersenne prime $k$ is
$$\boxed{\displaystyle k=\sum_{i=1}^{n(k)} \binom{n(k)}{i}}\quad n(k)=\lceil \log_2 k \rceil$$
It should be noted, though, that the restriction to prime $k$ is entirely artificial since we made no use of it anywhere in the above derivation. So any $k=2^n-1$ will satisfy this.