2
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ 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$. $\endgroup$
    – Joe Silverman
    Commented Jan 20, 2020 at 23:41
  • $\begingroup$ 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... $\endgroup$
    – Dudi Frid
    Commented Jan 21, 2020 at 5:51
  • $\begingroup$ 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$ $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Jan 21, 2020 at 8:06
  • 2
    $\begingroup$ @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$. $\endgroup$
    – Joe Silverman
    Commented Jan 21, 2020 at 12:53
  • $\begingroup$ @DudiFrid Do you agree with my edits? $\endgroup$
    – Rodrigo de Azevedo
    Commented May 9, 2023 at 9:42

1 Answer 1

Reset to default
1
$\begingroup$

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$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ My experiments show that the minimum is unnecessarily attained in $\lceil n/2 \rceil$...:\ $\endgroup$
    – Dudi Frid
    Commented Jan 24, 2020 at 8:44
  • $\begingroup$ @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$ $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Jan 24, 2020 at 8:46
  • $\begingroup$ 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$ $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Jan 24, 2020 at 9:07
  • $\begingroup$ ...up to 10000 by now $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Jan 24, 2020 at 9:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .