4

How to compute the maximal $k$ such that $ 1\leq k\leq n $ and

$$ {{n+k+1}\choose{n+1}} $$

is odd?

Given $n$, suppose this maximal number is $f(n)$. I want to obtain the explicit expression of the function $f$.

Shiquan
  • 508

2 Answers2

3

Below I allow $0\le k\le n$ to avoid an annoying technicality (that technicality being that disallowing $k=0$ leads to no solutions in some cases).

By Lucas's theorem a binomial coefficient $\binom{s}{t}$ is odd if and only each of the binary digits of $s$ is greater than or equal to the corresponding binary digit of $t$.

Letting $n+1=t$, we are looking for the largest $s$ which fits the above criteria such that $t\le s\le 2t-1$.

Now let's take the binary representation of $t=\left(b_mb_{m-1}\dots b_0\right)_2$ where $b_m=1$ and $b_i\in\{0,1\}$. Multiplying by $2$ gives $2t=\left(b_mb_{m-1}\dots b_00\right)_2=2^{m+1}+\left(b_{m-1}\dots b_10\right)_2$. Note now that $$\left(b_mb_{m-1}\dots b_0\right)_2>\left(b_{m-1}\dots b_00\right)_2$$ because the first $0$ in the right-hand expression appears before the first $0$ in the left-hand expression.

Hence if each digit of $s$ is bigger than or equal to the corresponding digit of $t$ and $s<2t$, we in fact need $s<2^{m+1}$. Now we notice that $2^{m+1}-1$ is the maximal such number and has all $1$s in its binary expansion (so each digit is bigger than or equal to the corresponding digit in $t$).

We conclude $$\binom{s}{t}=\binom{2^{m+1}-1}{t}$$ is the last odd binomial coefficient where $t\le s\le 2t-1$ and $2^m$ is the largest power of $2$ less than $t$ (notice that we can represent this as $m=\left\lfloor\log_2t\right\rfloor$).

Converting back to the original formulation, we get $$f(n)=2^{\left\lfloor\log_2(n+1)\right\rfloor+1}-n-2$$

Peter Woolfitt
  • 21,114
1

The explicit expression what I've found: $$f(n) = \begin{cases} -\infty, & \mbox{if $n$ has the form $2^{j-2}-2$} \\ 2^{1+\left\lfloor\log_2{\left(n+1\right)}\right\rfloor}-n-2, & \mbox{otherwise} \end{cases}$$

I've conjectured this function by calculating a few terms of the sequence $f$.

user153012
  • 12,240