
- Discrete Mathematics - Home
- Discrete Mathematics Introduction
- Mathematical Statements and Operations
- Atomic and Molecular Statements
- Implications
- Predicates and Quantifiers
- Sets
- Sets and Notations
- Relations
- Operations on Sets
- Venn Diagrams on Sets
- Functions
- Surjection and Bijection Functions
- Image and Inverse-Image
- Mathematical Logic
- Propositional Logic
- Logical Equivalence
- Deductions
- Predicate Logic
- Proof by Contrapositive
- Proof by Contradiction
- Proof by Cases
- Rules of Inference
- Group Theory
- Operators & Postulates
- Group Theory
- Algebric Structure for Groups
- Abelian Group
- Semi Group
- Monoid
- Rings and Subring
- Properties of Rings
- Integral Domain
- Fields
- Counting & Probability
- Counting Theory
- Combinatorics
- Additive and Multiplicative Principles
- Counting with Sets
- Inclusion and Exclusion
- Bit Strings
- Lattice Path
- Binomial Coefficients
- Pascal's Triangle
- Permutations and Combinations
- Pigeonhole Principle
- Probability Theory
- Probability
- Sample Space, Outcomes, Events
- Conditional Probability and Independence
- Random Variables in Probability Theory
- Distribution Functions in Probability Theory
- Variance and Standard Deviation
- Mathematical & Recurrence
- Mathematical Induction
- Formalizing Proofs for Mathematical Induction
- Strong and Weak Induction
- Recurrence Relation
- Linear Recurrence Relations
- Non-Homogeneous Recurrence Relations
- Solving Recurrence Relations
- Master's Theorem
- Generating Functions
- Graph Theory
- Graph & Graph Models
- More on Graphs
- Planar Graphs
- Non-Planar Graphs
- Polyhedra
- Introduction to Trees
- Properties of Trees
- Rooted and Unrooted Trees
- Spanning Trees
- Graph Coloring
- Coloring Theory in General
- Coloring Edges
- Euler Paths and Circuits
- Hamiltonion Path
- Boolean Algebra
- Boolean Expressions & Functions
- Simplification of Boolean Functions
- Advanced Topics
- Number Theory
- Divisibility
- Remainder Classes
- Properties of Congruence
- Solving Linear Diophantine Equation
- Useful Resources
- Quick Guide
- Useful Resources
- Discussion
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 kth differences are constant. This property is useful in determining the degree of the polynomial formula that describes the sequence −
- ∆0 constant − The sequence itself is constant
- ∆1 constant − First differences are constant
- ∆2 constant − Second differences are constant
- ∆3 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.