# Find closed-form expression to $f(n)$

For all $$n \in \mathbb{N}$$, let $${\mathcal A}_n := \left\{\lceil n/2\rceil, \lceil n/2\rceil+1,\dots, n-1 \right\}$$ and

$$f(n) := \begin{cases} \min\limits_{a \in {\mathcal A}_n} \frac 1 4 \binom n a f(a) & \text{if n\geq 4}\\ \qquad 1 & \text{otherwise} \end{cases}$$

I am looking for a closed-form expression for $$f(n)$$, but I could not find it.

So far what I have done is to try to get it into Python, I got the first 100 values, and I thought I would be able to guess the closed-form expression, but it is too difficult to guess it.

The first 10 values are:
$$\begin{array}{cl} n & f(n) \\ \hline 0 & 1 \\ 1 & 1 \\ 2 & 1 \\ 3 & 1 \\ 4 & 1.0 \\ 5 & 1.25 \\ 6 & 1.875 \\ 7 & 3.28125 \\ 8 & 6.5625 \\ 9 & 14.765625 \end{array}$$

Putting it in MS Excel I found that it is NOT an exponential expression as I guessed, but I couldn't find any more.

• Your $f(n)$ depends on $f(n)$, so you probably meant for $a$ to range from $n/2$ up to $n-1$, not up to $n$. Did you notice that $f(2n)=f(2n-1)$ for $n\ge4$? (At least, that's true for $4\le n\le 15$. I didn't check further.) Have you tried looking at the sequence of numerators of the $f(n)$, since the denominators are just powers of $2$. Jan 20, 2020 at 23:41
• It was a typo, I fixed it, thanx! But $\forall n\gneq m>3. f(n)\ne f(m)$ according to my Python program... And yes, even when omitting the $\frac 1 4$ factor, it is still very hard to guess the genral closed form expression... Jan 21, 2020 at 5:51
• An experimental observation, if this helps - minimum is actually attained on $\lceil n/2\rceil$ for $n\geqslant14$. In particular, this implies that $f(2n)=2f(2n-1)$ for $2n\geqslant16$, and $f(2n+1)=\frac14\binom{2n+1}nf(n+1)$ for $2n+1\geqslant15$ Jan 21, 2020 at 8:06
• @DudiFrid Sorry, my comment had a missing 2. It should say $f(2n)=2\cdot f(2n-1)$. And I just checked this up to $n\approx50$. Jan 21, 2020 at 12:53
• @DudiFrid Do you agree with my edits? May 9 at 9:42

The following answer depends on what I mentioned in a comment — that the minimum is attained on $$\lceil n/2\rceil$$ for $$n>13$$; I don't know how to prove it. For $$n\geqslant3$$, $$f(n)=\frac1{3\times4^{\lceil n/2^\ell\rceil+\ell-5/2}}\frac{n!}{\operatorname{rni}(n/2)!\operatorname{rni}(n/4)!\operatorname{rni}(n/8)!\cdots\operatorname{rni}(n/2^\ell)!}$$ where $$\ell=\max(0,\lceil\log_2(n/13)\rceil)$$ and $$\operatorname{rni}(x)$$ is the nearest integer to $$x$$, with the convention $$\operatorname{rni}(n+\frac12)=n$$ for integer $$n$$.
• My experiments show that the minimum is unnecessarily attained in $\lceil n/2 \rceil$...:\ Jan 24, 2020 at 8:44
• @DudiFrid I meant for $n\geqslant14$, let me add it. Did you find any counterexample? Sometimes it is also attained at $n-1$, but for all $n\geqslant14$ that I checked it is attained at $\lceil n/2\rceil$ Jan 24, 2020 at 8:46
• I am now running another kind of check, currently it shows that $f(n)=\frac14\binom n{\lceil\frac n2\rceil}f(\lceil\frac n2\rceil)$ for $14\leqslant n\leqslant7500$ Jan 24, 2020 at 9:07