calculus polynomial

Question

Use polynomial fitting to find a closed formula for the sequence 3,11,59,189,443,863,...

Answer 1

We will find the lowest-degree polynomial P(x) such that

Eq 1: (P(0), P(1), P(2), P(3), P(4), P(5)) = (3, 11, 59,189, 443, 863)

The Polynomial Interpolation Theorem says:

There exists a unique polynomial P(x) of degree at most n that interpolates n+1 data points

(P(x₀) = y₀,P(x₁) = y₁, ..., P(x_n) = y_n ) where no two x_j are the same.

[Why must no two x_j be the same?]

So there is a unique polynomial P(x) of degree at most 5 that satisfies Eq 1.

The degree of P(x) might be less than 5. It's is fun and easy to determine that degree.

Any sequence that starts (3,11,59,189,443,863,...) has difference sequence:

D⁽¹⁾ = (11-3=8, 59-11=48, 189-59=130, 443-189=254, 863-443=420, ...) .

The sequence D⁽¹⁾ = (8, 48, 130, 254, 420, ...) has difference sequence:

D⁽²⁾ = (48-8=40, 130-48=82, 254-130=124, 420-254=166, ...)

The sequence D⁽²⁾ = (40, 82, 124, 166, ...) has difference sequence

D⁽³⁾ = ( 42, 42, 42, ....)

which stays constant forever for the lowest degree polynomial that fits these first 6 terms.

Note that the difference sequence D⁽⁰⁾ is defined to be the sequence (P(0), P(1), P(2), P(3), …).

Theorem

For any integer k ≥ 0, a polynomial whose D^(k) is a nonzero constant sequence has degree exactly k.

[Try some examples to see that D⁽²⁾ is always linear if P(x) has degree 2. See if you can show that P(x+1) – P(x) always has degree exactly 1 less than P(x), unless P(x) is constant.]

By the way, this shows that polynomial sequences are characterized as sequences that have difference sequence D^(k) all 0's for some sufficiently large integer k (where k is one more than degree of the polynomial).

So the lowest degree polynomial that fits these first six terms (Eq 1) has degree 3. We need not look for a degree 5 polynomial. P(n) can be written as

P(n) = a₃x³ + a₂x² + a₁x + a₀ .

So we really only need the first four terms in our sequence. Let’s find the unique polynomial of degree 3 that satisfies

P(0) = 3; P(1) = 11; P(2) = 59; P(3) = 189.

Those are four linear equations in the four unknowns a₀, a₁, a₂, a₃ , and they are guaranteed to have a unique solution by the theorem below:

Polynomial Interpolation Theorem in Matrix Form: For any n+2 distinct real numbers r₀, r₁ … r_n , the square matrix C = {c_ij = r_i^j: 0 ≤ i,j ≤ n} of powers of the r's is nonsingular. [Why must the r's be distinct?]