Is there an easy way to reverse engineer a function?

Question

I have a function for which I know:

$f(2) = 2x -3y \\ f(3) = 5x - 6y \\ f(4) = 9x - 10 y \\ f(5) = 14x - 15y$

Assuming that $f$ is a polynomial, how do I find the general expression for $f$? After many minutes of fiddling I eventually found that this general expression works:

$f(N) = \frac{N(N+1)-2}{2}x - \frac{N(N+1)}{2}y$.

It's easy to verify that the expression works, but I found this by trial-and-error and I don't know if it's either unique or the simplest solution.

Answer 1

You know : $f(2) = 2x -3y \\ f(3) = 5x - 6y \\ f(4) = 9x - 10 y \\ f(5) = 14x - 15y$

Which means you know the function is in the form of

$f(N) = Ax - By$

where A and B are expressions involving N.

You can find polynomial expressions for A and B by using polynomial interpolation.

For A, the data points you use are $(2,2),(3,5),(4,9),(5,14)$.

For B, the data points you use are $(2,3),(3,6),(4,10),(5,15)$.

Putting these into an online lagrange interpolation calculator, it finds that $A = N^2/2 + N/2 - 1$ and $B = N^2/2 + N^2$ which is the same solution you found.

Answer 2

This is called Regression.

$$f(N) = f1(N)x + f2(N)y$$

First, you need to define what is the desired form of your expression, or what you mean "simplest". For example, people use linear form $\hat{f_1}(N) = a_1 N + b_1$, $\hat{f_2}(N) = a_2 N + b2$.

Second, you need to define the metric to evaluate the performance of you regression. For example to minimize the squared error $$\epsilon = \sum_N (\hat{f_1}(N) - f_1(N))^2 = \sum_N (a_1 N + b_1 - f_1(N))^2$$

The partial derivations of $\epsilon$ yield the values of $a_1$ and $b_1$ that minimize the squared error.

In your case, if you choose correctly the form of $f_1(N) = a_1N^2+b_1N+c_1$, the partial derivations will yield $a_1 =N^2/2, b_1=N/2$ and $c_1=-1$.

Note that all mathematical softwares have the regression functions but you always have to choose the form. And the solution is surely not unique.

Answer 3

First of all, a disclaimer: I am not answering how to extend a number sequence here. The answer in that case would not be unique, because despite anything that we know about the values of a function at given points - the function may have any values at any other point. However, we are restricting ourselves to finding the polynomials in $N$ that satisfy the given equalities.

If we know that $f(N)=P(N)x+Q(N)y$ for some polynomials $P$ and $Q$, there is a method to find the polynomials of the least degree that satisfy the given conditions: Lagrange interpolation polynomial (https://en.wikipedia.org/wiki/Lagrange_polynomial). Its general form, for $n$ given points $P(x_i)=y_i, i=1,2,\ldots,n$ is given by:

$$P(x)=\sum_{i=1}^ny_i\prod_{j\ne i, j=1}^n\frac{x-x_i}{x_j-x_i}$$

and it is at most of degree $n-1$. In our particular case, we have:

$$P(2)=2, P(3)=5, P(4)=9, P(5)=14$$

so the Lagrange polynomial looks like this:

$$P(N)=2\frac{(N-3)(N-4)(N-5)}{(2-3)(2-4)(2-5)}+5\frac{(N-2)(N-4)(N-5)}{(3-2)(3-4)(3-5)}+9\frac{(N-2)(N-3)(N-5)}{(4-2)(4-3)(4-5)}+14\frac{(N-2)(N-3)(N-4)}{(5-2)(5-3)(5-4)}$$

or:

$$P(N)=-\frac{1}{3}(N^3-12N^2+47N-60)+\frac{5}{2}(N^3-11N^2+38N-40)-\frac{9}{2}(N^3-10N^2+31N-30)+\frac{7}{3}(N^3-9N^2+26N-24)$$

or:

$$P(N)=\left(-\frac{1}{3}+\frac{5}{2}-\frac{9}{2}+\frac{7}{3}\right)N^3+\left(4-\frac{55}{2}+\frac{90}{2}-21\right)N^2+\left(-\frac{47}{3}+95-\frac{279}{2}+\frac{182}{3}\right)N+\left(20-100+135-56\right)$$

or:

$$P(N)=0\cdot N^3+\frac{1}{2}N^2+\frac{1}{2}N-1$$

which is the same as what you've got. You would do the similar process for $Q$.

Note: Of course, this is very tedious in the general case - to simplify you may need to use any additional information that comes to mind.

• For example, you can spot straight away that $Q(N)=N$'th triangular number, so $Q(N)=\frac{N(N+1)}{2}$ and $P(N)=Q(N)-1=\frac{N(N+1)}{2}-1$.

• Or ... use some calculator that can produce the Lagrange polynomial for you. E.g. Wolfram Alpha.

Answer 4

If you are assuming there is a pattern and that

$f(n) = A_n x - B_n y$ then all you are asking is:

If $A_2= 2; A_3 = 5; A_4 = 9; A_5 = 14$ what is $A_n$? And if $B_2= 3;B_3= 6; B_4 = 10; B_5 = 15$ what is $B_n$?

Well, there is no answer as just because something follows a pattern for $4$ numbers doesn't mean it follows then pattern forever.

But if we asuume the pattern we see that $A_k = A_{k-1} + k$ and $B_k = B_{k-1} + k$ continues forever we have:

So $A_n = A_{n-1} + n = A_{n-2} + (n-1) + n = ..... = A_0 + 1 + 2 +3+.....+n$.

$= A_0 + \sum\limits_{k=0}^n k = A_0 + \frac {n(n+1)}2$ [$*$]

And likewise $B_n = B_0 + \frac{n(n+1)}2$.

So if $A_2 = 2$ Then $A_2 = A_1 +2 = 2$ so $A_1 = 0$ and $A_1 = A_0 + 1 = 1$ so $A_0 = -1$. so $A_n = \frac {n(n+1)}2 - 1$.

And if $B_2 = 3$ than $B_2 =B_1 +2$ so $B_1 = 1$ and $B_0 = 0$.

So $B_n = \frac {n(n+1)}2$.

So $f(n) = x(\frac {n(n+1)}2) - y(\frac {n(n+1)}2)$

IF we assume the pattern that we and $nx - ny$ to each step always holds true. (And we have NO reason on earth to assume that at all.)

---

[$*$] It is a very well known result that $0 + 1 + 2+ 3 + ....... + n = \sum\limits_{k=0}^n k = \frac {n(n+1)}2$.

I'm not going to explain it hear but leave it as an exercise. (It is a rite of passage of all mathematicians to prove this result and every mathematician has stories and memories of where they were when they first learned that.)

Answer 5

We notice $\begin{cases} f(3)-f(2)=3x-3y=3(x-y)\\ f(4)-f(3)=4x-4y=4(x-y)\\ f(5)-f(4)=5x-5y=5(x-y)\\ \end{cases}$

So let assume the pattern is verified for all integers we get $f(n)-f(n-1)=n(x-y)$

This is a telescopic sum $f(n)-f(0)=(x-y)\sum\limits_{k=1}^{n} k\iff f(n)=f(0)+\dfrac{n(n+1)}2(x-y)$

Reporting in $f(2)=f(0)+3x-3y$ gives $f(0)=-x$.

Finally $\boxed{f(n)=\dfrac{n(n+1)}2(x-y)-x}$

Since $f$ is supposed to be a polynomial, let see if it is possible to find a lesser degree polynomial verifying the four initial conditions only.

In this case $f(t)=\frac {t(t+1)}2(x-y)-x$ is degree $2$ so let search for $g(t)=at+b$.

$g(3)-g(2)=a=3(x-y)$ as well as $g(4)-g(3)=a=4(x-y)$ contradiction.