How to Solve a Polynomial Number Sequence

Given a polynomial sequence (e.g. 1, 2, 4, 7, 11), how can we easily find the next number in that sequence?

http://digg.com/programming/How_to_Solve_a_Polynomial_Number_Sequence

First of all, each of the numbers in a polynomial sequence is a result of a polynomial function on n (where n = 1, 2, 3, ...). In other words, f(n) = amnm + am-1nm-1 + am-2nm-2 + ... + a2m2 + a1m + a0. The example above (1, 2, 4, 7, 11) can be represented by the polynomial function f(n) = 0.5n2 - 0.5n + 1.

Checking,
f(1) = 0.5(1)2 - 0.5(1) + 1 = 1
f(2) = 0.5(2)2 - 0.5(2) + 1 = 2
f(3) = 0.5(3)2 - 0.5(3) + 1 = 4
f(4) = 0.5(4)2 - 0.5(4) + 1 = 7
f(5) = 0.5(5)2 - 0.5(5) + 1 = 11

Hence, the next number in the sequence is
f(6) = 0.5(6)2 - 0.5(6) + 1 = 16

With this knowledge, how can we find the next number in a given polynomial sequence? Initially, i tried to find a0, a1, ..., am in the function f(n) = amnm + am-1nm-1 + am-2nm-2 + ... + a2m2 + a1m + a0 and work on from there. That would work, but for sure it was very tedious, especially if we have a high-degree polynomial function.

I then did a search for other methods to do this, and came across this page: http://www.everything2.com/index.pl?node_id=1026695. The first idea (by ariels) on that page is a simple and powerful method for solving polynomial sequences without having to solve for the coefficients of the function itself. You can read up on the method by visiting the link itself; my contribution here would be a Java programme which makes use of the algorithm described by that method:

import java.util.ArrayList;
import java.util.List;

public class Main
{
    public static final void main(String[] args)
    {
        int numInput = args.length;

        List<int[]> sequencesList = new ArrayList<int[]>(100);

        int currentSeqLen = numInput;
        int[] currentSequence = new int[currentSeqLen + 1];
        boolean constantFound = true;

        for (int i = 0; i < currentSeqLen; i++)
        {
            currentSequence[i] = Integer.parseInt(args[i]);

            if (constantFound
                    && (i > 0)
                    && (currentSequence[i] != currentSequence[i - 1]))
            {
                constantFound = false;
            }
        }

        sequencesList.add(currentSequence);

        while (!constantFound)
        {
            int[] prevSequence = currentSequence;

            currentSeqLen--;
            currentSequence = new int[currentSeqLen + 1];
            constantFound = true;

            for (int i = 0; i < currentSeqLen; i++)
            {
                currentSequence[i]
                        = prevSequence[i + 1] - prevSequence[i];

                if (constantFound
                        && (i > 0)
                        && (currentSequence[i] != currentSequence[i - 1]))
                {
                    constantFound = false;
                }
            }

            sequencesList.add(currentSequence);
        }

        for (int i = currentSeqLen; i < (currentSeqLen + 1); i++)
        {
            currentSequence[i] = currentSequence[i - 1];
        }

        for (int i = (sequencesList.size() - 2); i >= 0; i--)
        {
            int[] prevSequence = currentSequence;

            currentSeqLen++;
            currentSequence = sequencesList.get(i);

            for (int j = currentSeqLen; j < (currentSeqLen + 1); j++)
            {
                currentSequence[j]
                        = currentSequence[j - 1] + prevSequence[j - 1];
            }
        }

        System.out.println(currentSequence[numInput]);
    }
}

This programme takes in a sequence of numbers as arguments, and outputs the next number of that polynomial sequence.

E.g.
Input: java Main 1 2 4 7 11
Output: 16