0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ The expression is certainly not unique, since there are infinitely many sequences which start $2, 5, 9, 14, \dots$. $\endgroup$ – Patrick Stevens Jan 15 '18 at 23:55
  • $\begingroup$ Such a method does not exist and cannot exist. For all we know, you can have $f(6)=0, f(7)=\pi, f(8)=\sqrt{2}x, f(9)=y^{\text{the day of my birthday}}$ etc. In your case, you have restricted functions to those which are linear in $x$ and $y$, and then you are trying to continue the sequences $2,5,9,14,\ldots$ and $3,6,10,15,\ldots$. Again, that can be done in many ways. If you know those coefficients are polynomial in $N$, where $N$ is the argument of $f$, then the actual polynomial can be found as the Lagrange interpolation polynomial (see: en.wikipedia.org/wiki/Lagrange_polynomial) $\endgroup$ – user491874 Jan 15 '18 at 23:57
  • 1
    $\begingroup$ I just assumed your funcction would repeat periodically, so 2, 5, 9, 14, 2, 5, 9, 14, in which case your expressions are incorrect. $\endgroup$ – Michael Jan 15 '18 at 23:57
  • $\begingroup$ (Cont'd) To be precise, Lagrange interpolation is giving you the polynomial of smallest degree (= the number of points given or less), i.e. it will give you one (and the simplest one at that) out of still infinitely many solutions. And don't forget solutions that are not polynomial in $N$ at all... $\endgroup$ – user491874 Jan 16 '18 at 0:00
  • $\begingroup$ As the comments suggest, you generally need some external assumptions in order to do what you want. Maybe you know the answer is a polynomial, or something like that. But none of that will be implied by a handful of values. $\endgroup$ – lulu Jan 16 '18 at 0:01
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, fixed by using N in the expressions instead. $\endgroup$ – ksikka Jan 16 '18 at 0:43
1
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ We don't want regression here but interpolation (and extrapolation). This is because it is given that the function has to have exact values at the given points. You may get the same result, but the philosophy is different. $\endgroup$ – user491874 Jan 16 '18 at 0:14
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.)

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.