The Central Idea
A discrete function is a function whose domain consists of separated inputs rather than every value in an interval.
A typical discrete domain is
\[ \mathbb{N}=\{0,1,2,3,\ldots\}. \]The function may therefore be evaluated at
\[ 0,1,2,3,\ldots \]but not necessarily at values such as
\[ 1.5. \]Discrete change occurs from one allowed input to the next.
Discrete versus Continuous Domains
A continuous model may use every real input in an interval:
\[ x\in[0,10]. \]A discrete model may use only
\[ x\in\{0,1,2,\ldots,10\}. \]The formulas can look similar, but the domains are different.
Domain is part of the function.
A Sequence Is a Discrete Function
A sequence
\[ a_0,a_1,a_2,a_3,\ldots \]can be interpreted as a function
\[ a:\mathbb{N}\to S. \]The value at input \(n\) is written
\[ a_n. \]Thus sequence notation is function notation specialized to a discrete index set.
Example: A Linear Discrete Function
Let
\[ f(n)=3n+2 \]for
\[ n\in\mathbb{N}. \]Then
\[ f(0)=2,\quad f(1)=5,\quad f(2)=8,\quad f(3)=11. \]The outputs form the sequence
\[ 2,5,8,11,\ldots \]Graphing a Discrete Function
A discrete function is typically graphed using separate points.
For
\[ f(n)=3n+2, \]the graph contains points such as
\[ (0,2),\quad(1,5),\quad(2,8),\quad(3,11). \]Connecting the points with a solid line would suggest values at inputs not included in the domain.
Do Not Invent Intermediate Inputs
Suppose
\[ f:\mathbb{N}\to\mathbb{R} \]is defined by
\[ f(n)=n^2. \]The value
\[ f(2) \]is defined.
But
\[ f(2.5) \]is not part of this function unless the domain is explicitly extended.
Finite Discrete Functions
A discrete function may have a finite domain.
For example,
\[ f:\{1,2,3,4\}\to\mathbb{R} \]may be given by
\[ f(1)=7,\quad f(2)=4,\quad f(3)=9,\quad f(4)=6. \]A table may be the most convenient complete representation.
Countably Infinite Discrete Functions
A discrete function may also have an infinite countable domain.
For example,
\[ f(n)=2^n,\qquad n\in\mathbb{N}. \]This produces
\[ 1,2,4,8,16,\ldots \]with one output for every natural-number index.
Tables as Discrete Functions
A table can represent a discrete function by listing inputs and outputs.
| \(n\) | \(f(n)\) |
|---|---|
| 0 | 5 |
| 1 | 8 |
| 2 | 12 |
| 3 | 17 |
The table need not come from a simple formula.
Explicit Rules
An explicit rule computes an output directly from the current input.
For example,
\[ a_n=4n-1. \]To find \(a_{100}\), substitute \(n=100\) directly:
\[ a_{100}=4(100)-1=399. \]Recursive Rules
A recursive rule defines new values using earlier values.
For example,
\[ a_0=5 \]and
\[ a_{n+1}=a_n+3. \]Then
\[ 5,8,11,14,\ldots \]is generated one step at a time.
State Updates as Discrete Functions
A deterministic state update may be written
\[ s_{n+1}=F(s_n). \]The current state \(s_n\) determines the next state \(s_{n+1}\).
Repeated application produces the state sequence
\[ s_0,s_1,s_2,s_3,\ldots \]Stepwise Change
Stepwise change occurs through separated updates rather than continuously.
An account balance recorded at the end of each month may change from
\[ B_0 \]to
\[ B_1 \]to
\[ B_2 \]without the model specifying every intermediate value.
Finite Differences
For a sequence or discrete function, the change from one step to the next is measured by a finite difference.
Define
\[ \Delta a_n=a_{n+1}-a_n. \]This is the discrete analogue of measuring change across neighboring inputs.
Example: First Differences
Consider
\[ 2,5,8,11,14. \]The first differences are
\[ 5-2=3, \] \[ 8-5=3, \] \[ 11-8=3, \]and
\[ 14-11=3. \]Thus
\[ \boxed{\Delta a_n=3}. \]Constant First Difference
A sequence with constant first difference has a linear pattern in its index.
If
\[ \Delta a_n=d, \]then
\[ a_{n+1}=a_n+d. \]This is the recursive form of an arithmetic sequence.
Second Differences
Differences themselves can change.
Consider
\[ 1,4,9,16,25. \]First differences are
\[ 3,5,7,9. \]Their differences are
\[ 2,2,2. \]These are the second differences.
Quadratic Patterns and Second Differences
For values generated by a quadratic function of the index, equally spaced inputs produce constant second differences.
For
\[ a_n=n^2, \]the values
\[ 0,1,4,9,16,\ldots \]have first differences
\[ 1,3,5,7,\ldots \]and constant second difference \(2\).
Difference Tables
A difference table organizes successive finite differences.
For
\[ 1,4,9,16, \]we may display:
| Level | Values |
|---|---|
| Original | 1, 4, 9, 16 |
| First difference | 3, 5, 7 |
| Second difference | 2, 2 |
Discrete Rate of Change
If inputs increase by one unit, the difference
\[ f(n+1)-f(n) \]measures the change per discrete step.
If inputs are separated by some other spacing \(h\), we may compare
\[ f(x+h)-f(x). \]Discrete rate questions depend on how the input steps are defined.
Relative Change
Sometimes absolute change is less informative than proportional change.
If
\[ a_n>0, \]then the relative change from step \(n\) to step \(n+1\) is
\[ \frac{a_{n+1}-a_n}{a_n}. \]This is useful for growth rates, returns, populations, and repeated percentage changes.
Multiplicative Stepwise Change
A sequence may update by multiplication rather than addition.
For example,
\[ a_{n+1}=2a_n \]with
\[ a_0=3 \]produces
\[ 3,6,12,24,48,\ldots \]Constant Ratios
If
\[ \frac{a_{n+1}}{a_n}=r \]is constant, then
\[ a_{n+1}=ra_n. \]This is the recursive structure of a geometric sequence.
Additive and multiplicative updates represent two fundamental forms of stepwise change.
Example: Repeated Percentage Growth
Suppose a quantity increases by \(5\%\) each period.
Then
\[ a_{n+1}=1.05a_n. \]If
\[ a_0=100, \]then
\[ a_1=105, \] \[ a_2=110.25, \]and so on.
Integer-Valued Functions
Many discrete functions produce integer outputs.
For example,
\[ f(n)=2n+1 \]maps natural numbers to odd positive integers.
Counts, ranks, queue lengths, and numbers of objects are naturally integer-valued.
Discrete Domain, Continuous Range
A discrete function does not need an integer-valued range.
For example,
\[ f(n)=\sqrt{n} \]for \(n\in\mathbb{N}\) has a discrete domain but real-valued outputs.
Discreteness may come from the input set even when outputs lie on a continuous numerical scale.
Step Functions
A step function is constant across intervals and changes by jumps at specified boundaries.
A familiar example is the floor function
\[ \lfloor x\rfloor, \]which returns the greatest integer less than or equal to \(x\).
Its output changes only when \(x\) crosses an integer.
Floor Function
For example,
\[ \lfloor2.1\rfloor=2, \] \[ \lfloor2.9\rfloor=2, \]while
\[ \lfloor3\rfloor=3. \]The output stays constant over
\[ [2,3) \]and jumps at \(3\).
Ceiling Function
The ceiling function
\[ \lceil x\rceil \]returns the least integer greater than or equal to \(x\).
For example,
\[ \lceil2.1\rceil=3, \] \[ \lceil2.9\rceil=3, \]and
\[ \lceil3\rceil=3. \]Piecewise-Constant Models
A model may remain fixed for a period and then jump to another level.
For example, a shipping rate might be
\[ C(w)= \begin{cases} 5,&0Threshold Behavior
Stepwise systems often depend on thresholds.
A rule may change when
\[ x\ge10, \]when an inventory falls below a reorder point, or when a score crosses a classification boundary.
Thresholds convert continuous or numerical inputs into discrete decisions.
Indicator Functions
An indicator function records whether a condition is true.
For a set \(A\), define
\[ \mathbf{1}_A(x)= \begin{cases} 1,&x\in A,\\ 0,&x\notin A. \end{cases} \]Indicator functions encode membership numerically.
Binary State Variables
A system with two states can be represented by a binary function.
For example,
\[ s_n\in\{0,1\} \]may indicate
\[ 0=\text{off}, \qquad 1=\text{on}. \]A time sequence of such values describes stepwise state changes.
Discrete Time
A system evolves in discrete time when its state is indexed by separated time steps:
\[ t=0,1,2,3,\ldots \]Examples include daily inventories, annual populations, game turns, and algorithm iterations.
Continuous Time versus Discrete Time
A continuous-time model may consider every
\[ t\ge0. \]A discrete-time model may consider only
\[ t=0,1,2,\ldots \]Even when the real system changes continuously, a discrete model may record it only at selected observation times.
Sampling a Continuous Process
Suppose a temperature varies continuously through the day.
Recording it once per hour produces a discrete sequence:
\[ T_0,T_1,T_2,\ldots,T_{23}. \]The sampled data are discrete even though the underlying physical process may be continuous.
Discrete Models from Counts
Counts are naturally discrete.
The number of customers in a store may be
\[ 0,1,2,3,\ldots \]but not
\[ 2.6. \]Functions describing such quantities often map into \(\mathbb{N}\) or \(\mathbb{Z}\).
Inventory Updates
Inventory can be modeled recursively:
\[ I_{n+1}=I_n+\text{arrivals}_n-\text{departures}_n. \]Each period updates the previous state.
This structure is common in logistics, production, finance, and queueing.
Population by Generation
A population model may use generation number rather than continuous time.
For example,
\[ P_{n+1}=1.2P_n \]models \(20\%\) growth per generation.
The index \(n\) identifies discrete generations.
Algorithm Iterations
Algorithms naturally generate discrete sequences.
If \(x_n\) is the current approximation after \(n\) iterations, then an update rule may have the form
\[ x_{n+1}=F(x_n). \]The sequence records the algorithm's progress one iteration at a time.
Difference Equations
A difference equation relates values of a discrete function at different indices.
For example,
\[ a_{n+1}-a_n=4 \]states that the sequence increases by \(4\) each step.
Difference equations play a role in discrete systems analogous to differential equations in continuous systems.
Difference Equations and Recurrences
The equation
\[ a_{n+1}-a_n=4 \]can be rearranged as
\[ a_{n+1}=a_n+4. \]Thus many difference equations are recurrence relations written in a form emphasizing change.
Fixed Points in Discrete Updates
For an update rule
\[ x_{n+1}=F(x_n), \]a value \(x^*\) is a fixed point when
\[ F(x^*)=x^*. \]Once the system reaches \(x^*\), it remains there under repeated updates.
Example: Fixed State
Suppose
\[ F(0)=1,\qquad F(1)=2,\qquad F(2)=2. \]Then \(2\) is a fixed point because
\[ F(2)=2. \]The state sequence beginning at \(0\) is
\[ 0,1,2,2,2,\ldots \]Periodic Behavior
A discrete process may return to earlier states repeatedly.
For example,
\[ 0,1,0,1,0,1,\ldots \]has period \(2\).
Periodic behavior corresponds to cycles in a state-transition graph.
Monotone Discrete Change
A discrete sequence is increasing when later terms do not fall below earlier terms.
One common condition is
\[ a_{n+1}\ge a_n. \]It is decreasing when
\[ a_{n+1}\le a_n. \]Finite differences make such behavior easy to detect.
Positive and Negative Differences
If
\[ \Delta a_n>0, \]then the function increases from \(n\) to \(n+1\).
If
\[ \Delta a_n<0, \]it decreases across that step.
If
\[ \Delta a_n=0, \]the value remains unchanged.
Discrete Local Maxima and Minima
A term \(a_n\) may be a discrete local maximum if it exceeds neighboring terms:
\[ a_n>a_{n-1} \]and
\[ a_n>a_{n+1}. \]Similar comparisons define local minima.
Neighbor comparisons replace continuous derivative reasoning.
Cumulative Sums
A discrete function can accumulate previous values.
Define
\[ S_n=\sum_{k=0}^{n}a_k. \]Then
\[ S_{n+1}-S_n=a_{n+1}. \]Cumulative totals are common in finance, probability, inventory, and data analysis.
Discrete Change from Cumulative Totals
If \(S_n\) is a cumulative total, then the increment added at step \(n\) can be recovered by subtraction:
\[ a_n=S_n-S_{n-1}. \]Summation and finite differencing therefore act as complementary discrete operations.
Rounding Creates Stepwise Behavior
A continuous calculation may become discrete after rounding.
If the number of required buses is
\[ B(n)=\left\lceil\frac{n}{40}\right\rceil, \]then the output changes in steps.
Passenger counts from \(1\) through \(40\) require one bus, while \(41\) through \(80\) require two.
Capacity Constraints
Discrete step functions often arise from fixed capacities.
If boxes hold \(12\) items each, then the number of boxes required for \(n\) items is
\[ \boxed{B(n)=\left\lceil\frac{n}{12}\right\rceil}. \]The function jumps whenever another box becomes necessary.
Discrete Choice Functions
A function may map numerical inputs into categorical outputs.
For example,
\[ C(x)= \begin{cases} \text{low},&x<10,\\ \text{medium},&10\le x<20,\\ \text{high},&x\ge20. \end{cases} \]The output set is discrete even though the input may be continuous.
Discrete Output versus Discrete Input
A function can be discrete in more than one sense.
It may have a discrete domain.
It may have a discrete range.
Or both may be discrete.
Always identify which part of the model creates the discreteness.
Common Error: Connecting Discrete Points Automatically
Suppose \(f\) is defined only for integer \(n\).
Drawing a continuous line between
\[ (1,f(1)) \]and
\[ (2,f(2)) \]suggests values at noninteger inputs that may not belong to the model.
Common Error: Ignoring the Domain
The formula
\[ f(x)=x^2 \]does not by itself tell us whether \(x\) ranges over
\[ \mathbb{R}, \] \[ \mathbb{Z}, \]or some finite set.
Different domains define different functions.
Common Error: Confusing Difference with Ratio
Additive change uses
\[ a_{n+1}-a_n. \]Multiplicative change uses
\[ \frac{a_{n+1}}{a_n}. \]These measure different patterns.
A sequence may have constant differences, constant ratios, or neither.
Common Error: Treating Stepwise Change as Smooth Change
A shipping price that jumps from
\[ \$5 \]to
\[ \$8 \]at a weight threshold does not pass through every intermediate price.
The model changes by a jump.
Common Error: Forgetting Initial Conditions
A recurrence such as
\[ a_{n+1}=a_n+3 \]does not determine one unique sequence until an initial value is supplied.
The choices
\[ a_0=0 \]and
\[ a_0=10 \]produce different sequences.
A Reliable Procedure for Analyzing Discrete Change
- Identify the domain.
- Determine whether inputs are finite, integer-indexed, or otherwise separated.
- List or compute several consecutive values.
- Check first differences.
- Check ratios when multiplicative growth is plausible.
- Check higher differences when polynomial patterns are suspected.
- Identify any recurrence or state-update rule.
- Locate thresholds, jumps, fixed points, or cycles.
- Distinguish the discrete model from any underlying continuous process.
- Choose a table, point graph, sequence, or recurrence that best represents the structure.
Example: Full Discrete Analysis
Consider
\[ a_n=n^2+1 \]for
\[ n=0,1,2,3,4. \]The values are
\[ 1,2,5,10,17. \]First differences are
\[ 1,3,5,7. \]Second differences are
\[ 2,2,2. \]The constant second difference reflects the quadratic dependence on \(n\).
Practice 1: Evaluate a Discrete Function
Let
\[ f(n)=2n+5 \]for \(n\in\mathbb{N}\).
Find
\[ f(4). \]Practice 2: Allowed Input?
Suppose
\[ f:\mathbb{N}\to\mathbb{R}. \]Is
\[ f(2.5) \]defined under this domain?
Practice 3: First Differences
Find the first differences of
\[ 4,9,14,19,24. \]Practice 4: Second Differences
Find the first and second differences of
\[ 1,4,9,16,25. \]Practice 5: Recursive Update
Let
\[ a_0=2 \]and
\[ a_{n+1}=a_n+4. \]Write the first five terms.
Practice 6: Multiplicative Update
Let
\[ a_0=3 \]and
\[ a_{n+1}=2a_n. \]Find \(a_4\).
Practice 7: Floor Function
Evaluate
\[ \lfloor5.8\rfloor. \]Practice 8: Ceiling Function
Evaluate
\[ \lceil5.2\rceil. \]Practice 9: Capacity Model
A van holds at most \(8\) passengers.
How many vans are required for \(19\) passengers?
Practice 10: Fixed Point
Suppose
\[ F(0)=1,\qquad F(1)=2,\qquad F(2)=2. \]Which state is a fixed point?
Practice Answers
Practice 1
\[ f(4)=2(4)+5=\boxed{13}. \]Practice 2
No. The domain is \(\mathbb{N}\), and \(2.5\notin\mathbb{N}\).
\[ \boxed{f(2.5)\text{ is not defined by the stated function}.} \]Practice 3
\[ 9-4=5,\quad 14-9=5,\quad 19-14=5,\quad 24-19=5. \]Therefore,
\[ \boxed{5,5,5,5}. \]Practice 4
First differences:
\[ 3,5,7,9. \]Second differences:
\[ \boxed{2,2,2}. \]Practice 5
\[ \boxed{2,6,10,14,18}. \]Practice 6
The sequence is
\[ 3,6,12,24,48. \]Therefore,
\[ \boxed{a_4=48}. \]Practice 7
\[ \boxed{\lfloor5.8\rfloor=5}. \]Practice 8
\[ \boxed{\lceil5.2\rceil=6}. \]Practice 9
\[ \left\lceil\frac{19}{8}\right\rceil = \lceil2.375\rceil = \boxed{3}. \]Practice 10
Because
\[ F(2)=2, \]the fixed point is
\[ \boxed{2}. \]What to Remember
- A discrete function has separated allowed inputs.
- A sequence is a function on an ordered discrete index set.
- Finite differences measure change from one discrete step to the next.
- Constant first differences indicate linear index behavior.
- Constant second differences indicate quadratic index behavior for equally spaced inputs.
- Recursive rules generate values from earlier values.
- Step functions change by jumps rather than smooth transitions.
- Floor and ceiling functions are standard stepwise functions.
- Discrete-time models describe systems one stage, period, or iteration at a time.
- Domain restrictions must be respected when evaluating or graphing a discrete function.
The central habit is: identify the allowed inputs first, then measure how the output changes from one allowed input to the next.
Where We Go Next
Discrete functions describe how values change across separated inputs. A more general discrete system may have many possible components, choices, and states that can be assembled into complete configurations.
The next lesson, Configurations and State Spaces, develops systematic ways to represent complete discrete states, combinations of component values, and spaces of possible configurations.