Let $n$ be an odd number larger than 1, and $f(x)$ is a polynomial with degree $n$ such that $f(k)=2^k$ for $k=0,1,\cdots,n$. Prove that there is only finite integer $x$ such that $f(x)$ is the power of two.
Problem
Source: 2017 Taiwan TST Round 1
Tags: algebra, polynomial
13.04.2018 21:09
My very-old post here would have immediately solve this problem. But unfortunately, no one interested in that and I now also forget where I read it from.
17.04.2018 08:13
Nice problem Clearly $f(x)=\binom x0+\binom x1+\cdots+\binom xn$. As $n>1$ is odd, $f(-1)=0$ so we may write $f(x)=\frac{(x+1)P(x)}{n!}$ for some monic, nonconstant $P(x)\in\mathbb Z[x]$. For every $a$ such that $f(a)$ is a power of 2, there exist $u$ and $v$ that are odd and multiply to $\frac{n!}{v_2(n!)}$ with both $\frac{a+1}u$ and $\frac{P(a)}v$ a power of 2. By infinite Pigeonhole, some choice of $u$ and $v$ yields infinitely many such $a$. As $P$ has degree $n-1\ge2$, for sufficiently large such $a$ we must have $\frac{a+1}u\le\frac{P(a)}v$, so $\frac{a+1}u$ divides $\frac{P(a)}v$. This holds for infinitely many $a$, forcing $x+1\mid P(x)$. But now we claim that $f$ does not have a double root at $x=-1$, creating a contradiction. To do so, we compute the derivative of $\binom x{2k}+\binom x{2k+1}=\binom{x+1}{2k+1}$ at $x=-1$, which is equal to the derivative of $\binom x{2k+1}$ evaluated at $x=0$. This is given by the $x$ coefficient of $\binom x{2k+1}$, which is positive for all $k\ge0$. Summing from $k=0$ to $k=\frac{n-1}2$, $f'(-1)>0$, so we are done. Edit: Alternatively, we may just evaluate $\frac f{x+1}$ directly by noting that $\frac{\binom x{2k}+\binom x{2k+1}}{x+1}=\frac{\binom{x+1}{2k+1}}{x+1}$ is positive at $x=-1$.
28.05.2022 09:42
First note $f(x)=\sum\limits_{t=0}^n \binom xn$. The key observation is $f(-1)=0$ since $n$ is odd, which allows the polynomial to factor and we can consider $\frac{f(x)}{x+1}$ and that gives everything a nice grounding point (or just think of it as $f(x)=\sum\limits_{1\le j\le n, j odd} \binom{x+1}{j}$ which contains $x+1$ as a factor.) First, $\frac{m+1}{n!} | f(m)-f(-1)$, so it follows that $\nu_p(m+1)\le \nu_p(n!)$ for all odd primes. It follows that there must be infinitely many powers of 2 of the form $f(2^kd-1)$ where $d$ is one of the finitely many divisors of $n!$ We have $f(2^kd-1)=\sum\limits_{1\le j\le n, j \text{ odd}} \binom{2^kd}{j}=2^kd \sum_{1\le j\le n} \frac 1j \binom{2^kd-1}{j-1}$ where $j$ is odd. Since $j$ is odd, We have $\binom{2^kd-1}{j-1} = \prod\limits_{t=1}^{j-1} (\frac{2^kd}{t}-1) \equiv 1 (\bmod\; 2^{k-C})$ where $C=\lfloor \log_2(n) \rfloor$. It follows that $\sum_{j \text{ odd}, 1\le j\le n} \frac 1j \binom{2^kd-1}{j-1} \equiv \sum_{j \text{ odd}, 1\le j\le n} (\bmod\; 2^{k-C})$, which means $\nu_2(\sum_{j \text{ odd}, 1\le j\le n} \frac 1j \binom{2^kd-1}{j-1})$ is bounded, call $A$. It follows that $f(2^kd-1)=2^{k+\nu_2(d)+A}$ is linear in $k$, so if $f(2^kd-1)$ is a power of 2 for sufficiently large $k$, $f$ must be linear, absurd!