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
    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
    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$
    – მამუკა ჯიბლაძე
    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
    Jan 21, 2020 at 12:53
  • $\begingroup$ @DudiFrid Do you agree with my edits? $\endgroup$
    – Rodrigo de Azevedo
    May 9 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
    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$
    – მამუკა ჯიბლაძე
    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$
    – მამუკა ჯიბლაძე
    Jan 24, 2020 at 9:07
  • $\begingroup$ ...up to 10000 by now $\endgroup$
    – მამუკა ჯიბლაძე
    Jan 24, 2020 at 9:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.