Chinese mathmatical olympiad

Here’s an elementary approach to solve this problem (no lagrange interpolation, nothing).

The key idea here is the connection of $f(i)$ with $f(i-1)$ ,

which is,

$\frac{f(i)}{f(i-1)} = \frac{\binom{N+1}{i-1}}{\binom{N+1}{i}} = \frac{i}{N+2-i}$ .

Now, after re-arranging,

$(N+2-i)f(i) - if(i-1) = 0$ .

The expression on the left side is an $(N+1)^{th}$ polynomial and has N roots.

$(N+2-i)f(i) - if(i-1) = \alpha(i-1)(i-2)\cdots(i-N)(i-r)$ ,

where $r$ represents the root we don’t know about.

Now, this might seem unsolvable because it has not one but two unknowns, but, really, it is not. (You actually have a lot to exploit here!)

First of all, put $i = 0$ ,

$(N+2) = (\alpha)(r)(-1)^{N+1}(N!)$ .

Now, put $i = N+2$ ,

$-(N+2)f(N+1) = (\alpha)((N+1)!)(N+2-r)$ .

For one last time, put $i = N+1$ ,

$f(N+1) - 1 = (\alpha)(N!)(N+1-r)$ .

Now, using the first equation to substitute $\alpha$ for $r$ in the last two and equating the resulting expressions of $f(N+1)$ , we get,

$\frac{(N+2)(N+1-r)}{(-1)^{N+1}r} + 1 = -\frac{(N+1)(N+2-r)}{(-1)^{N+1}r}$ .

Now,

$r = N+1, \space N$ is even.

$r = N+2, \space N$ is odd.

Now, it’s not hard to see that $f(N+1)$ is $1$ and $0$ accordingly as $N$ is even and odd.

We are trying to find the degree $N$ polynomial $f(X)$ such that $f(j) \; = \; \binom{N+1}{j}^{-1} \hspace{2cm} 0 \le j \le N$ This polynomial is uniquely defined, and is given by Lagrange Interpolation as $f(X) \; = \; \sum_{j=0}^N \frac{f(j)}{\pi_j(j)} \pi_j(X)$ where $\pi_j(X) \; = \; \prod_{{0 \le k \le N} \atop {k \neq j}}(X-k) \hspace{2cm} 0 \le j \le N$ Now $\begin{aligned} \pi_j(j) & = \; \prod_{{0 \le k \le N} \atop {k \neq j}}(j - k) \; = \; (-1)^{N-j} j! (N-j)! \\ \frac{f(j)}{\pi_j(j)} & = \; \frac{j! (N+1-j)!}{(N+1)!} \pi_j(j)^{-1} \; = \; (-1)^{N-j}\frac{N+1-j}{(N+1)!} \\ \pi_j(N+1) & = \; \prod_{{0 \le k \le N} \atop {k \neq j}}(N+1-k) \; = \; \frac{(N+1)!}{N+1-j} \end{aligned}$ for all $0 \le j \le N$ , and so $\begin{aligned} f(N+1) & = \; \sum_{j=0}^N \frac{f(j)}{\pi_j(j)} \pi_j(N+1) \; = \; \sum_{j=0}^N (-1)^{N-j} \; = \; \sum_{j=0}^N (-1)^j \\ & = \; \left\{ \begin{array}{lll} 1 & \hspace{1cm} & N \;\;\mathrm{even} \\ 0 & & N \;\; \mathrm{odd} \end{array} \right. \end{aligned}$ so the sum of possible values of $f(N+1)$ is $0 + 1 = \boxed{1}$ .