We prove that $(j,k) = (2019, 1010)$ is a valid solution. More generally, let $p(x)$ be the polynomial of degree $N$ such that $p(2n+1) = F_{2n+1}$ for $0 \leq n \leq N$. We will show that $p(2N+3) = F_{2N+3}-F_{N+2}$.

Define a sequence of polynomials $p_0(x),\ldots,p_N(x)$ by $p_0(x) = p(x)$ and $p_k(x) = p_{k-1}(x)-p_{k-1}(x+2)$ for $k \geq 1$. Then by induction on $k$, it is the case that $p_k(2n+1) = F_{2n+1+k}$ for $0 \leq n \leq N-k$, and also that $p_k$ has degree (at most) $N-k$ for $k \geq 1$. Thus $p_N(x) = F_{N+1}$ since $p_N(1) = F_{N+1}$ and $p_N$ is constant.

We now claim that for $0\leq k\leq N$, $p_{N-k}(2k+3) = \sum_{j=0}^k F_{N+1+j}$. We prove this again by induction on $k$: for the induction step, we have $$\begin{align*} p_{N-k}(2k+3) &= p_{N-k}(2k+1)+p_{N-k+1}(2k+1) \\ &= F_{N+1+k}+\sum_{j=0}^{k-1} F_{N+1+j}. \end{align*}$$ Thus we have $p(2N+3) = p_0(2N+3) = \sum_{j=0}^N F_{N+1+j}$.

Now one final induction shows that $\sum_{j=1}^m F_j = F_{m+2}-1$, and so $p(2N+3) = F_{2N+3}-F_{N+2}$, as claimed. In the case $N=1008$, we thus have $p(2019) = F_{2019} - F_{1010}$.