Minimization with a Polynomial Parameter

If we define $p_j(X) \; = \; \prod_{0 \le k \le 9 \atop k \neq j}(X - 2k) \hspace{2cm} 0 \le j \le 9$ then each polynomial $p_j(X)$ has degree $9$ and $\begin{aligned} p_j(2j) & = \; \prod_{0 \le k \le 9 \atop k \neq j}2(j-k) \; = \; (-1)^{9-j} 2^9 j! (9-j)! \\ p_j(20) & = \; \prod_{0 \le k \le 9 \atop k \neq j} 2(10-k) \; = \; 2^9 \frac{10!}{10-j} \end{aligned}$ and so the polynomial $P(X)$ is given by Lagrange interpolation: $P(X) \; = \; \sum_{j=0}^9 \frac{\alpha_j}{p_j(2j)}p_j(X)$ where $\alpha_j \; = \; \left\{ \begin{array}{lll} F_{2j+1} & \hspace{1cm} & 1 \le j \le 9 \\ P(0) & & j = 0 \end{array} \right.$ Thus $P(20) \; = \; \sum_{j=0}^9 \frac{\alpha_j}{p_j(2j)} p_j(20) \; = \; \sum_{j=0}^9 (-1)^{j+1}\binom{10}{j}\alpha_j \; = \; 10858 - P(0)$ Thus $P(0)^2 + P(20)^2 \; = \; P(0)^2 + \big(P(0) - 10858\big)^2 \; = \; 2\big(P(0) - 5429\big)^2 + 2\times5429^2$ which is minimized when $P(0) = \boxed{5429}$ .

---

To prove the final formula identifying $P(20)$ ...

Suppose that $u$ is either of the roots of the equation $X^2 - X - 1 = 0$ . Then $\begin{aligned} - u & = \; 1 - u^2 \\ (-1)^n u^n & = \; \left(1 - u^2\right)^n \; = \; \sum_{k=0}^n {n \choose k}(-1)^ku^{2k} \\ (-1)^nu^{n+1} & = \; \sum_{k=0}^n {n \choose k}(-1)^k u^{2k+1} \end{aligned}$ If $p > q$ are the two roots of $X^2 - X - 1 = 0$ then we know that $\sqrt{5}F_n = p^n -q^n$ for all $n \ge 0$ . Thus means that $(-1)^n F_{n+1} \; = \; \sum_{k=0}^n (-1)^k{n \choose k}F_{2k+1}$ From this we deduce that $\sum_{j=1}^n (-1)^{j+1}{n+1 \choose j}F_{2j+1} \; = \; (-1)^n\left[\sum_{j=0}^{n+1} (-1)^{n+1+j}{n+1 \choose j}F_{2j+1} - (-1)^{n+1} - F_{2n+1}\right] \; = \; (-1)^n\left[F_{n+2} -(-1)^{n+1} - F_{2n+3}\right]$ and hence $P(20) \; = \; F_{21} - F_{11} + 1 - P(0) \; = \; 10858 - P(0)$

EDIT: This solution is incorrect. In particular, the value written for $P(0)$ is incorrect.

Using the identity $\sum_{k \geq 0} \binom{n-k}{k} = F_{n+1}$ observe that there is a constant $c$ such that $P(x) = \binom{x}{0} + \binom{x-1}{1} + ... + \binom{x - 9}{9} + c(x - 2)(x-4)...(x-18).$ Then, $\begin{aligned} P(20) & = F_{21} - 1 + c 18!! \\ P(0) & = 1 - c 18!!. \end{aligned}$ So, $P(20) = F_{21} - P(0)$ . Hence, $P(0)^2 + P(20)^2$ is minimized when $P(0) = F_{21}/2 = \boxed{5473}$ .