# Generating Polynomials through points

Suppose the function $f$ goes through the points $(x_1, y_1)$ and $(x_2, y_2)$. $f$ can be represented as the polynomial,

$$
f(x) = (x-x_2)\left(\frac{y_1}{x_1-x_2}\right) + (x-x_1)\left(\frac{y_2}{x_2-x_1}\right)
$$

Notice that,
$$
\begin{align*}
f(x_1) &= (x_1-x_2)\left(\frac{y_1}{x_1-x_2}\right) + (x_1-x_1)\left(\frac{y_2}{x_2-x_1}\right) \\
&=y_1 + 0 \\
f(x_2) &= (x_2-x_2)\left(\frac{y_1}{x_1-x_2}\right) + (x_2-x_1)\left(\frac{y_2}{x_2-x_1}\right) \\
&=0 + y_2
\end{align*}
$$

Since all $x_n, y_n$ are integers, all coefficients will be rational. A similar method works for more points as well. Suppose $g$ passes through $(x_1, y_1), (x_2, y_2),$ and $(x_3, y_3)$. $g$ can be represented as,

\begin{align*}
g(x) &= (x-x_2)(x-x_3)\left( \frac{y_1}{(x_1 - x_2)(x_1-x_3)} \right) \\
&+ (x-x_1)(x-x_3)\left( \frac{y_2}{(x_2 - x_1)(x_2-x_3)} \right) \\
&+ (x-x_1)(x-x_2)\left( \frac{y_3}{(x_3 - x_1)(x_3-x_2)} \right). \\
\end{align*}

## Recursive method

Suppose $f$ is already defined, and we want the same property

\begin{align*}
g(x_1) &= f(x_1) = y_1 \\
g(x_2) &= f(x_2) = y_2 \\
g(x_3) &= y_3. \\
\end{align*}

This means that the poly $g(x) - f(x)$ has zeros at $x_1$ and $x_2$. Therefore we get,

\begin{align*}
g(x) - f(x) &= a(x-x_1)(x-x_2) \\
g(x) &= a(x-x_1)(x-x_2) + f(x)
\end{align*}

for some constant $a$. We can solve for $a$ since we know $g(x_3) = y_3$.

\begin{align*}
g(x_3) = y_3 &= a(x_3-x_1)(x_3-x_2) + f(x_3) \\
y_3 - f(x_3) &= a(x_3-x_1)(x_3-x_2) \\
a &= \frac{y_3 - f(x_3)}{(x_3-x_1)(x_3-x_2)}
\end{align*}

Putting everything together, we can see that,

$$
g(x) = \left(\frac{y_3 - f(x_3)}{(x_3-x_1)(x_3-x_2)}\right)(x-x_1)(x-x_2) + f(x)
$$

So long all points have integer coordinates, $g(x)$ will have rational coefficients.