[Guest]

If we have a sequence of numbers that follow a formula related to n (the position in the formula) eg for the sequence 1, 4, 9, 16, 25, 36... the numbers follow the formula n². If we say the highest power of n in the formula is x (eg for n³+n+1 x=3) then how many numbers do we need in the sequence to be sure of being able to derive the formula?

Bare minimum terms to be able to do it, no extra ones to ensure the proof.

[Guest]

x+1?

reasoning:

if x = 0, you'd only need 1 term to determine the constant number (e.g. 3,3,3,3,... f(n) = a*n^0 a=3)

if x=1 you'd only need 2 terms (e.g. 1,3,5,7,9 f(n) = a*n^1+b*n^0 use two equations)

x=2, use three equations to solve for unknown coefficients

this assumes that f(n) will always be a polynomial and not include, i dunno, sines or something heh.

[Guest]

x+1?

reasoning:

if x = 0, you'd only need 1 term to determine the constant number (e.g. 3,3,3,3,... f(n) = a*n^0 a=3)

if x=1 you'd only need 2 terms (e.g. 1,3,5,7,9 f(n) = a*n^1+b*n^0 use two equations)

x=2, use three equations to solve for unknown coefficients

this assumes that f(n) will always be a polynomial and not include, i dunno, sines or something heh.

That's not the answer I was thinking of (not saying it's necessarily wrong).

To clarify what I meant was how many terms in the series do you need to be able to work it out without knowing what x is so you wouldn't be able to set up simultaneous equations.

On a side note I only put relatively easy because I didn't want people mocking me if everyone got it right away

[Guest]

...that if you don't know what x is, there is no length of sequence that will give you the answer for certain. Unless I'm mistaken, you can create...

a sequence of 2 zeros with a formula an²+bn+c (a!=zero)

a sequence of 3 zeros with a formula an³+bn²+cn+d (a!=zero)

a sequence of x zeros with a formula an^x+bn^x-1....(a!=zero)

(I haven't verified that but I think it works that way)

...so generally if you have a sequence with i items in it, you cannot know what x is, because you could always generate a sequence with i (or more) zeros with a higher power of x and add it to the first sequence without changing the first i members. So you never know that x is not a higher value than you think.

[Guest]

...that if you don't know what x is, there is no length of sequence that will give you the answer for certain. Unless I'm mistaken, you can create...

a sequence of 2 zeros with a formula an²+bn+c (a!=zero)

a sequence of 3 zeros with a formula an³+bn²+cn+d (a!=zero)

a sequence of x zeros with a formula an^x+bn^x-1....(a!=zero)

(I haven't verified that but I think it works that way)

...so generally if you have a sequence with i items in it, you cannot know what x is, because you could always generate a sequence with i (or more) zeros with a higher power of x and add it to the first sequence without changing the first i members. So you never know that x is not a higher value than you think.

non zero powers of n

[bonanova]

one more point than the highest power.

That is, 2 points for a line, 3 for a parabola, 4 for a cubic, etc.

But you have to know the sequence is a set of points on a polynomial curve.

[Guest]

If we say the highest power of n in the formula is x (eg for n³+n+1 x=3)

For clarification - are all the coefficients 1?

Would 2n⁴-1/2n²+3/2 (for instance) be allowed?

[Guest]

...that if you don't know what x is, there is no length of sequence that will give you the answer for certain. Unless I'm mistaken, you can create...

a sequence of 2 zeros with a formula an²+bn+c (a!=zero)

a sequence of 3 zeros with a formula an³+bn²+cn+d (a!=zero)

a sequence of x zeros with a formula an^x+bn^x-1....(a!=zero)

(I haven't verified that but I think it works that way)

...so generally if you have a sequence with i items in it, you cannot know what x is, because you could always generate a sequence with i (or more) zeros with a higher power of x and add it to the first sequence without changing the first i members. So you never know that x is not a higher value than you think.

i agree, if what octopuppy is trying to solve is indeed what you're going for,

it will be impossible to determine the equation without knowing x.

lets say given the sequence 0, 1. this works with f(n) = n, n^2, n^3, etc..., therefore x is unknown

so lets up it to three, 0, 1, 4. now we've eliminated f(n) = n, but that still means that f(n) = an^2+b*n+c is viable, as is a*n^3+b*n^2+c*n+d, you just have to solve for the variables (which i admit will be rather annoying with x much greater than 5.

so by increasing the number of terms, we only eliminate lower functions, we never hit a ceiling of higher power functions.

Edited October 24, 2008 by hombreduffo

[Guest]

i agree, if what octopuppy is trying to solve is indeed what you're going for,

it will be impossible to determine the equation without knowing x.

lets say given the sequence 0, 1. this works with f(n) = n, n^2, n^3, etc..., therefore x is unknown

so lets up it to three, 0, 1, 4. now we've eliminated f(n) = n, but that still means that f(n) = an^2+b*n+c is viable, as is a*n^3+b*n^2+c*n+d, you just have to solve for the variables (which i admit will be rather annoying with x much greater than 5.

so by increasing the number of terms, we only eliminate lower functions, we never hit a ceiling of higher power functions.

apologies for posting the solution to this so early but it's the first brain teaser I've ever posted and I don't want it to get too close to farce

I originally intended the answer to be x+2, however given the OP x+1 might be better (my mistake)

My method of doing this based on looking at the diference (it's the first step along the way to calculus) between the terms for example in sequence 1,2,3,4,5,6 the difference between the terms is 1 obviously.

If we the take the series 1, 4, 9, 16, 25, 36 then the differences form another series in this case 5, 7, 9, 11 then the difference in this series (the second difference) is 2.

for 1, 8, 27, 64, 125, 216 differences are 7, 19, 37. 61, 91, 2nd differences 12, 18, 24, 30, 3rd difference is 6

you can keep going but I won't, suffice to say that in a sequence where the highest power of n is x so (an^x) the xth difference will be ax!

So by comparing the differences until we find one which is a constant we can calculate the highest power of n and it's coefficient. you then take that away from each number in the sequence and repeat for each lower power of n. The question then is how many terms do we need to have to calculate the xth difference, the reason I went with x+2 is that x+1 will only give one value for the xth difference so there's no way to know if it's constant or not, x+2 gives 2 values so we can be sure it is the highest power. However just taking the 1 value x+1 gives and using it as the value ax! does work.

Example

11, 24, 53, 104, 183

3rd difference is 6, 6 divided by 3! is 1 so highest term is n³

series - n³

10, 16, 26, 40, 58

2nd difference is 4, 4 divided by 2! is 2 so 2nd term is 2n²

series - (n³ + 2n²)

8, 8, 8, 8, 8

so last term is 8

makes the polynomial n³ + 2n² + 8

in conclusion it's x+1 terms to be able to work it out, x+2 to be able to do it and know you aren't going to be wasting your time doing the subtractions.

feel free to mercilessly rip it apart

[Guest]

apologies for posting the solution to this so early but it's the first brain teaser I've ever posted and I don't want it to get too close to farce

I originally intended the answer to be x+2, however given the OP x+1 might be better (my mistake)

My method of doing this based on looking at the diference (it's the first step along the way to calculus) between the terms for example in sequence 1,2,3,4,5,6 the difference between the terms is 1 obviously.

If we the take the series 1, 4, 9, 16, 25, 36 then the differences form another series in this case 5, 7, 9, 11 then the difference in this series (the second difference) is 2.

for 1, 8, 27, 64, 125, 216 differences are 7, 19, 37. 61, 91, 2nd differences 12, 18, 24, 30, 3rd difference is 6

you can keep going but I won't, suffice to say that in a sequence where the highest power of n is x so (an^x) the xth difference will be ax!

So by comparing the differences until we find one which is a constant we can calculate the highest power of n and it's coefficient. you then take that away from each number in the sequence and repeat for each lower power of n. The question then is how many terms do we need to have to calculate the xth difference, the reason I went with x+2 is that x+1 will only give one value for the xth difference so there's no way to know if it's constant or not, x+2 gives 2 values so we can be sure it is the highest power. However just taking the 1 value x+1 gives and using it as the value ax! does work.

Example

11, 24, 53, 104, 183

3rd difference is 6, 6 divided by 3! is 1 so highest term is n³

series - n³

10, 16, 26, 40, 58

2nd difference is 4, 4 divided by 2! is 2 so 2nd term is 2n²

series - (n³ + 2n²)

8, 8, 8, 8, 8

so last term is 8

makes the polynomial n³ + 2n² + 8

in conclusion it's x+1 terms to be able to work it out, x+2 to be able to do it and know you aren't going to be wasting your time doing the subtractions.

feel free to mercilessly rip it apart

Taking your example of the sequence:

11, 24, 53, 104, 183

How do you know that wasn't produced by the polynomial:

n⁵-15n⁴+86n³-223n²+274n-112 for example? (or infinitely many other polynomials of even higher orders which I can't be bothered to work out)

[Guest]

If you take the difference between the polynomial I gave you and the one you had you get n⁵-15n⁴+85n³-225n²+274n-120, a tricky little polynomial which evaluates to:

0,0,0,0,0,120,720,2520... for n from 1 to 8. You can come up with something like that which gives you as many zeroes as you like, which is why no finite sequence has a unique polynomial.

I think my notation was a bit confusing in the earlier post. By "a!=zero" I meant "a != zero" (a<>0) not "a! = zero". Maybe not all that clear!

[Guest]

apologies for posting the solution to this so early but it's the first brain teaser I've ever posted and I don't want it to get too close to farce

I originally intended the answer to be x+2, however given the OP x+1 might be better (my mistake)

My method of doing this based on looking at the diference (it's the first step along the way to calculus) between the terms for example in sequence 1,2,3,4,5,6 the difference between the terms is 1 obviously.

If we the take the series 1, 4, 9, 16, 25, 36 then the differences form another series in this case 5, 7, 9, 11 then the difference in this series (the second difference) is 2.

for 1, 8, 27, 64, 125, 216 differences are 7, 19, 37. 61, 91, 2nd differences 12, 18, 24, 30, 3rd difference is 6

you can keep going but I won't, suffice to say that in a sequence where the highest power of n is x so (an^x) the xth difference will be ax!

So by comparing the differences until we find one which is a constant we can calculate the highest power of n and it's coefficient. you then take that away from each number in the sequence and repeat for each lower power of n. The question then is how many terms do we need to have to calculate the xth difference, the reason I went with x+2 is that x+1 will only give one value for the xth difference so there's no way to know if it's constant or not, x+2 gives 2 values so we can be sure it is the highest power. However just taking the 1 value x+1 gives and using it as the value ax! does work.

Example

11, 24, 53, 104, 183

3rd difference is 6, 6 divided by 3! is 1 so highest term is n³

series - n³

10, 16, 26, 40, 58

2nd difference is 4, 4 divided by 2! is 2 so 2nd term is 2n²

series - (n³ + 2n²)

8, 8, 8, 8, 8

so last term is 8

makes the polynomial n³ + 2n² + 8

in conclusion it's x+1 terms to be able to work it out, x+2 to be able to do it and know you aren't going to be wasting your time doing the subtractions.

feel free to mercilessly rip it apart

You can find an exact fit to any set of n x,y-ordered points with a polynomial of order n+1 or greater. So, if you know its order is 5, you can solve it with any 6 different points, but finding an exact fit through 6 points does not guarantee the series is a 5th order polynomial.

One of the many reasons why high-order polynomial curve fits are dangerous, and why I avoid them like the plague.