Polynomial Fitting in Discrete Mathematics

---

---

Polynomial Fitting is a powerful technique that helps us understand and predict complex patterns in sequences. In discrete mathematics, this method comes in handy while working with sequences that do not follow simple arithmetic or geometric progressions.

In this chapter, we will explain the concept and use-cases of polynomial fitting and its significance in mathematical analysis, with examples for a better understanding.

What is a Sequence?

In discrete mathematics, a sequence is an ordered list of numbers. Terms in sequences follow a specific pattern. While some sequences are straightforward (like arithmetic sequences where the difference between terms is constant), others require more complex analysis to understand their underlying patterns.

The Concept of Differences

If we talk about sequences, it helps in polynomial fitting as well. The key to polynomial fitting lies in analyzing the differences between consecutive terms −

• First differences − Subtract consecutive terms
• Second differences − Take differences of the first differences
• Third differences − Take differences of the second differences.

And so on, until we reach constant differences.

Delta-Constant Sequences (-Constant)

The idea for delta constant is quite interesting. A sequence is called constant when it is the k^th differences are constant. This property is useful in determining the degree of the polynomial formula that describes the sequence −

• ∆⁰ constant − The sequence itself is constant
• ∆¹ constant − First differences are constant
• ∆² constant − Second differences are constant
• ∆³ constant − Third differences are constant

Relationship between Differences and Polynomial Degree

If we focus more deeply, we can get the mathematical framework of it. Theorem states: A sequence has a polynomial formula of degree k if and only if it is ∆^k constant. This relationship is quite useful in determining the following −

• Whether a sequence can be described by a polynomial
• The exact degree of the polynomial needed
• The method to find the formula

General Form of Polynomial Formulas

For a ∆^k constant sequence, the formula will be −

$$\mathrm{a_n \:=\: a_k \:\cdot\: n^k \:+\: a_{k-1} \:\cdot\: n^{k-1} \:+\: \dots \:+\: a_1 \:\cdot\: n \:+\: a_0}$$

They may look quite confusing. But we can easily understand them though examples.

Example 1: Quadratic Sequence Analysis

Let us understand for the sequence: 3, 7, 14, 24, ...

Step-by-Step Analysis −

• First differences: 4, 7, 10, ...
• Second differences: 3, 3, ...

Since second differences are constant, and we need a quadratic formula like −

$$\mathrm{a n^2 \:+\: b n \:+\: c}$$

Finding the Formula −

• When n = 0: 2 = c
• When n = 1: 3 = a + b + 2
• When n = 2: 7 = 4a + 2b + 2

Solving this system −

From the first equation, c = 2

Substituting into others and solving −

• a = 3 / 2
• b = -1 / 2

Final formula −

$$\mathrm{a_n \:=\: \frac{3}{2} n^2 \:-\: \frac{1}{2} n \:+\: 2}$$

Example 2: The Classic Chessboard Problem

Let us see another interesting example on chessboard. Find the total number of squares in an n × n chessboard.

Sequence Analysis −

• Initial terms: 1, 5, 14, 30, 55, ...
• First differences: 4, 9, 16, 25, ...
• Second differences: 5, 7, 9, ...
• Third differences: 2, 2, ...

Since we reach constants at the third difference, we need a cubic formula −

$$\mathrm{a_n \:=\: a n^3 \:+\: b n^2 \:+\: c n \:+\: d}$$

Detailed Solution −

• When n = 0: d = 0
• Using n = 1, 2, and 3:

Now,

• 1 = a + b + c
• 5 = 8a + 4b + 2c
• 14 = 27a + 9b + 3c

Solving the system −

• a = 1 / 3
• b = 1 / 2
• c = 1 / 6

Final formula −

$$\mathrm{a_n \:=\: \frac{1}{3} n^3 \:+\: \frac{1}{2} n^2 \:+\: \frac{1}{6} n}$$

Special Cases and Non-Polynomial Sequences

We have understood the basics of polynomial fitting. But there are some special cases and non-polynomial sequences. We must understand them in contrast to the previous polynomial fitting equations.

Identifying Non-Polynomial Sequences

Not all sequences can be represented by polynomials. We can understand them through some key cases −

• Exponential Sequences Example: 1, 2, 4, 8, 16, ...
• Taking differences never leads to constants
• Growth rate is multiplicative rather than additive
• Recursive Sequences Example: Fibonacci sequence (1, 1, 2, 3, 5, 8, ...)
• Differences follow the original pattern
• No level of differences becomes constant

Practical Implementation

Following are the steps for Polynomial Fitting −

• Calculate successive differences until they become a constant
• Count the number of difference operations as needed to determine the proper polynomial degree
• Set up a system of equations using n + 1 different points (where n is the degree)
• Solve the system to find coefficients
• Finally prepare the formula in standard form

We must always verify the formula by −

• Testing with original sequence values in order
• Checking edge cases from the sequences
• Verifying the pattern that continues beyond given terms

Real-World of Applications of Polynomial Fitting

Polynomial fitting for sequences has several applications in computer science and mathematics.

In mathematical modelling, it can be used for finding growth patterns in natural phenomena, financial forecasting and trend analysis, population studies, and physical systems modelling.

In Computer Science, it can be used for algorithm complexity analysis, data compression, pattern recognition, and computer graphics and animation.

Conclusion

In this chapter, we explained the framework of polynomial fitting in discrete mathematics. Through detailed examples like the quadratic sequence and the chessboard problem, we highlighted the practical application of these concepts.

We have also gone through the limitations of polynomial fitting through our analysis of non-polynomial sequences. Finally, we touched upon the broader applications of polynomial fitting in various fields.