# 1, 3, 6, what is the next number of the sequence?

I've heard (and believed even without proof) that given any finite sequence there is more than one formula for which the same first inputs give the same first outputs.

Given that:

f(1)=1 f(2)=3 f(3)=6

One possible function is f(x) = x(x+1)/2.

So, I tried to find another polynomial function for which f(1)=1, f(2)=3 and f(3)=6, but for which f(4) is not 10, but got no success. So I ask: Can it be done? (please provide an example :))

I find this question interesting because often we can make a conjecture by finite induction which is wrong (like the proposed "prime-producing polynomials" which always start to fail after some time :P)

• The next number of the sequence is 42, obviously. – Did Feb 2 '14 at 16:47
• @did do you mean becuase it is the meaning of life? – Jorge Fernández Hidalgo Feb 2 '14 at 17:15
• @user4140 Afraid I do. – Did Feb 2 '14 at 17:22
• There is also $f(x)=\begin{cases}1&x=1\\3&x=2\\6&x=3\\47.9027347&otherwise \end{cases}$ which is a fine formula – Ross Millikan Mar 5 '14 at 0:09

Let us take the simplest case after a quadratic. Then let $$f(x)=a+b x+c x^2+d x^3$$ So we can build three equations from which we can eliminate $b$,$c$ and $d$ as a function of $a$. As a result, we have
$$b=\frac{1}{6} (3-11 a)$$ $$c=a+\frac{1}{2}$$ $$d=-\frac{a}{6}$$

You can now select any number for $a$. The cubic will always go through the three data points and $f(4)=10-a$

• For the lazy, WolframAlpha can fit that cubic for you ;) – David H Feb 2 '14 at 16:42
• Also, in case you're interested, the cubic corresponding to $f(4)=k$ is apparently $f(x)=\frac{x(x+1)}{2}+(10-k)(1-\frac{11}{6}x+x^2-\frac16x^3)$. – David H Feb 2 '14 at 16:45

Let $a$ be any real number.

Then, by Lagrange interpolation formula the function:

$$f(x)=\frac{(x-2)(x-3)(x-4)}{-6}+3\frac{(x-1)(x-3)(x-4)}{2}+6\frac{(x-1)(x-2)(x-4)}{-2}+a\frac{(x-1)(x-2)(x-3)}{6}$$

satisfies $f(1)=1, f(2)=3, f(3)=6, f(4)=a$.

So anything is the right answer...

Just for fun: setting $a=cat$ you get the pattern, $1,2,3,cat$.

P.S. This is not the only formula which satisfies these conditions. If $g$ is any function, then

$$f(x)+g(x)(x-1)(x-2)(x-3)(x-4)$$ also satisfies the pattern $1,3,6,a$.

Yes, you are correct. There are indeed more than a sequence that starts with $1,3,6$. The function you input is the triangular number function. OEIS gives other types of sequences too!

Theorem: For any finite sequence of numbers $(a_1,a_2\dots a_n)$ there is at least 1 polynomial such that $f(i)=a_i$ for all $i$ between $1$ and $n$.

Proof: First we prove for all i there is polynomial suc that p(i)=a_i and for other integers betwenn 1 and n it is 0.

Proof:function

$g_i(x)=(x+1)(x+2)\dots(x-(i-1))(x-(i+1)\dots(x-n)=k$ when $x=i$ and 0 for other integers between 1 and n. Therefore the function

$p_i(x)=\dfrac{(x+1)(x+2)\dots(x-(i-1))(x-(i+1)\dots(x-n)}{k}\cdot a_i=a_i$when $x=i$ and $0$ for other integers between 1 and n.

Now check the polynomial $p(x)=p_1(x)+p_2(x)\dots+p_n(x)$ fits the sequence perfectly.

Theorem: For any list $(a_1,a_2\dots a_n)$ there exist infinite polynomials such that $f(i)=a_i$ for all $i$ between $1$ and $n$.

Proof: by the above theorem there are polynomials satisfying $(a_1,a_2\dots a_n,k)$ for any real k. Clearly all those polynomials also satisfy $(a_1,a_2\dots,a_n,k)$ and they are uncountably many.

This also shows the next number in the sequence could be any number, and there would still be a "polynomial formula" to back you up

• There is a mistake in your proof of Lagrange Iterpolation. $k$ is not a constant, it depends on $i$, thus $k$ and $p_i$ are not polynomials. You need to divide by the right constant and multiply by $a_i$. – N. S. Feb 2 '14 at 16:39
• I'm sorry, I have no Idea what lagrange interpolation is, I am building n different polynomials $p_i$ and then I'm adding them to get a new one p(x) that satisfies everything.@N.S. so why is $p_i$ not a polynomial? – Jorge Fernández Hidalgo Feb 2 '14 at 16:41
• Oh, I got you, got it. – Jorge Fernández Hidalgo Feb 2 '14 at 16:42
• You have the right idea, is just that $k$ is not constant. Set $p_i(x)=a_i\frac{g_i(x)}{g_i(i)}$ and it works.. And you rediscover Lagrange interpolation ;) – N. S. Feb 2 '14 at 16:43
• Got it, thanks.Is it fine now? – Jorge Fernández Hidalgo Feb 2 '14 at 16:46