Back to Discrete Mathematics: An Open Introduction

Polynomial Fitting

Recovering a closed formula for a sequence with constant kth differences by fitting a polynomial through those differences.

Discrete Mathematics: An Open Introduction, Polynomial Fitting

Status

FlagsLoading your progress…

5 exercises

Exercise 6

Consider the sequence $1, 3, 7, 13, 21, \ldots$ . Explain how you know the closed formula for the sequence will be quadratic. Then “guess” the correct formula by comparing this sequence to the squares $1, 4, 9, 16, \ldots$ (do not use polynomial fitting).

2.5

Exercise 7

Use a similar technique as in the previous exercise to find a closed formula for the sequence $2, 11, 34, 77, 146, 247,\ldots$ .

2.5

Exercise 9

Generalize this exercise: Find a closed formula for the sequence of differences of $a_n = an^2 + bn + c$ . That is, prove that every quadratic sequence has arithmetic differences.

2.5

Exercise 10

Can you use polynomial fitting to find the formula for the $n$ th term of the sequence 4, 7, 11, 18, 29, 47, …? Explain why or why not.

2.5

Exercise 11

Will the $n$ th sequence of differences of $2, 6, 18, 54, 162, \ldots$ ever be constant? Explain.

2.5