Functions, Graphs, Sequences and Recurrence

Introduction

Functions, graphs, sequences and recurrence relations provide a common mathematical language for describing change. In information technology, they are used to analyse algorithms, model storage and network growth, estimate system performance, describe population or transaction changes, and design iterative computations. A function relates an input to an output; a graph displays that relationship; a sequence describes values indexed by discrete time or position; and a recurrence relation defines later values from earlier ones.

The central skill is not merely calculating values. It is selecting an appropriate model, identifying its assumptions, interpreting parameters, and recognising when the model is no longer reliable.

Learning Objectives

By the end of this chapter, you should be able to:

• define functions, domains, codomains and ranges;
• evaluate and combine functions and determine compositions;
• analyse linear, polynomial, exponential and logarithmic functions;
• interpret intercepts, slopes, roots, asymptotes and transformations from graphs;
• distinguish arithmetic and geometric sequences;
• use explicit and recursive sequence definitions;
• solve and interpret first-order linear recurrence relations;
• connect recurrence relations with algorithmic iteration and computational complexity;
• evaluate the limitations and ethical implications of mathematical models.

1. Functions as Computational Models

A function is a rule that assigns exactly one output to each permitted input. We write f: A → B, where A is the domain, B is the codomain, and f(x) is the output associated with input x. The range is the set of outputs actually produced and is therefore a subset of the codomain.

For example, f(x) = 2x + 3 is a function from the real numbers to the real numbers. If the domain is the integers from 0 to 10, the same rule describes a different function because the permitted inputs have changed.

A relation fails to be a function if one input has two different outputs. The vertical-line test gives a graphical version of this principle: a curve represents a function of x if every vertical line intersects it at most once.

Evaluation and inverse functions

To evaluate f(x) = x² − 4x + 1 at x = 3, substitute 3:

An inverse function reverses the input-output process. A function has a function inverse only when it is one-to-one on the specified domain. If y = f(x), interchange x and y and solve for y. For f(x) = 3x − 5,

The domain of f⁻¹ is the range of f, and its range is the domain of f. A quadratic such as f(x)=x² is not one-to-one on all real numbers, but it becomes invertible when restricted to x ≥ 0.

Operations and composition

For functions f and g,

Composition is order-sensitive. If f(x)=2x+1 and g(x)=x², then (f∘g)(x)=2x²+1, whereas (g∘f)(x)=(2x+1)².

2. Linear and Polynomial Functions

Linear functions

A linear function has the form

where m is the slope and b is the vertical intercept. For two distinct points (x₁,y₁) and (x₂,y₂), with x₁ ≠ x₂,

The slope measures the change in output per unit change in input. Its units are output units divided by input units. A positive slope indicates increase, a negative slope indicates decrease, and zero slope indicates a constant function.

Worked example. A cloud service charges a fixed monthly fee of $40 plus $0.08 per gigabyte transferred. If x is gigabytes and C(x) is cost in dollars, then

For 250 GB, C(250)=40+20=60. The intercept represents the fixed charge; the slope represents marginal cost per gigabyte. This model is appropriate only while the pricing policy remains linear and no tiered charges apply.

Polynomial functions

A polynomial is

where the coefficients a₀,…,aₙ are constants and aₙ ≠ 0. Its degree is n. A polynomial of degree n has at most n real zeros and at most n−1 turning points.

The zeros or roots are values satisfying p(x)=0. Factoring is often useful. For

the roots are 2 and 3. The graph crosses or touches the horizontal axis at roots, although an even-multiplicity root generally touches and turns rather than crossing.

The quadratic function

has axis of symmetry x=−b/(2a). Its roots, when real, are

The discriminant Δ=b²−4ac determines the number of real roots: two if Δ>0, one repeated root if Δ=0, and none if Δ<0.

3. Exponential and Logarithmic Functions

An exponential function has the form

where a ≠ 0, b>0, and b≠1. Here a is the initial value and b is the multiplicative factor for each one-unit increase in x. If b>1, the function grows; if 0<b<1, it decays.

A percentage growth model is

where A₀ is the initial amount, r is the growth rate per period expressed as a decimal, and t is the number of periods. For decay at rate d, use A(t)=A₀(1−d)ᵗ, provided 0≤d≤1.

Worked example. A data set contains 8,000 records and grows by 12% each month. After 6 months,

The result is an estimate, because the model assumes a constant proportional rate and ignores storage policies, deletions and changes in usage.

The natural exponential model is

where e≈2.71828 and k is the continuous growth constant per time unit. The discrete and continuous models are not interchangeable unless their rates are converted appropriately.

The logarithm is the inverse of exponentiation:

with b>0, b≠1, and x>0. Important identities include

The logarithm is defined only for positive arguments over the real numbers. Logarithmic scales are valuable when values span several orders of magnitude, as in algorithmic complexity, signal strength and data visualisation.

Worked example. To find the time required for a quantity to double under 8% monthly growth, solve 2=(1.08)^t:

Thus doubling occurs after approximately 10 complete months if observations are restricted to whole months.

4. Reading and Transforming Graphs

A graph communicates both numerical and structural information. Important features include:

• the domain and range;
• horizontal and vertical intercepts;
• increasing and decreasing intervals;
• maximum and minimum values;
• symmetry;
• discontinuities and asymptotes;
• scale, units and possible distortion.

For a function y=f(x), the transformation y=f(x)+k shifts the graph vertically by k, while y=f(x−h) shifts it horizontally by h. The function y=−f(x) reflects it in the horizontal axis, and y=f(−x) reflects it in the vertical axis. Horizontal transformations require particular care because the sign inside the function is reversed.

A rational function may have a vertical asymptote where its denominator is zero, unless a factor cancels and creates a removable discontinuity. For example,

has a hole at x=1, not a vertical asymptote. Cancellation does not restore the excluded input.

Graph interpretation must consider the axes. A graph with a compressed vertical scale can make small changes appear large; a graph beginning above zero can hide relative differences. Professional reports should label units, identify the data source and avoid misleading scales.

5. Sequences and Series

A sequence is an ordered list a₁,a₂,a₃,…, usually indexed by positive integers. The subscript identifies position, not a power. An explicit formula gives aₙ directly; a recursive formula gives an initial value and a rule for obtaining later terms.

Arithmetic sequences

An arithmetic sequence has constant difference d:

The sum of its first n terms is

These formulas assume a finite sequence with integer n≥1.

Geometric sequences

A geometric sequence has constant ratio r:

For r≠1, the first n terms sum to

If |r|<1, the infinite geometric series converges to

The infinite formula does not apply when |r|≥1, because the terms do not approach zero or the partial sums do not settle at a finite value.

Worked example. A backup system stores 500 MB initially and creates successive copies at 60% of the preceding copy size. The first five copy sizes form a geometric sequence with a₁=500, r=0.6:

The infinite idealised total is 1,250 MB, but it cannot represent the first five terms; the infinite formula applies to all terms continuing indefinitely and is larger than the first term alone. Here, because the first five sum is actually 500(1−0.6⁵)/0.4 = 1,344.8, the infinite sum calculation should be checked: 500/0.4=1,250. Since the finite partial sum cannot exceed the infinite sum for positive terms, the correct finite value is 1,250(1−0.6⁵)=1,217.6 MB. The error illustrates why algebraic verification is essential: the correct finite formula is Sₙ=a₁(1−rⁿ)/(1−r), giving 1,217.60 MB.

6. Recurrence Relations and Iteration

A recurrence relation defines a term from earlier terms. For example,

generates 2, 5, 8, 11, … . It is an arithmetic sequence, and its explicit form is aₙ=2+3(n−1).

A first-order linear recurrence has the form

where a and c are constants and x₀ is given. If a≠1, its closed form is

Equivalently, using the equilibrium value x*=c/(1−a),

The equilibrium formula assumes a≠1. If |a|<1, aⁿ→0, so xₙ→x*. If a>1, deviations generally grow; if a<0, values may alternate around the equilibrium. When a=1, the recurrence is xₙ=xₙ₋₁+c, giving xₙ=x₀+nc.

Worked example. A server queue contains 100 jobs. Each cycle, 70% remain and 20 new jobs arrive:

The equilibrium is x*=20/(1−0.7)=66.67. Thus,

After three cycles, x₃≈66.67+0.343(33.33)≈78.10. The model predicts convergence because the retention factor is less than 1, although actual queues may be affected by bursts and capacity limits.

Recurrence and algorithms

Many algorithms are naturally described recursively. A binary search on a sorted list reduces the problem size approximately by half at each step, leading to a recurrence of the form

for positive constant c, with a base case for small n. This produces logarithmic growth, T(n)=O(log n). An algorithm that examines every item once has approximately T(n)=T(n−1)+c, producing O(n). Nested processing may produce O(n²). These are growth classifications, not exact execution times; hardware, implementation language and input structure also matter.

A recursive program must have a base case and must move toward it. Without a terminating condition, recursion can exhaust memory or cause a nonterminating process. Iterative and recursive implementations can be mathematically equivalent while differing in memory use, clarity and performance.

7. Applied Case: Capacity Planning for an IT Service

Background. This illustrative case concerns a university authentication service. During ordinary periods, the number of authentication requests per minute grows by 5% each month because of increased system adoption. The current rate is 12,000 requests per minute.

Problem. The service team must estimate demand after 12 months and decide whether current capacity is sufficient. The team also needs a queue model for requests waiting during a processing cycle.

Analysis. A discrete growth model is appropriate for monthly planning:

After 12 months,

Suppose a simplified queue recurrence is Qₙ=0.75Qₙ₋₁+500, with Q₀=2,000. Its equilibrium is

In this idealised model, the initial queue already equals equilibrium, so Qₙ=2,000 for every cycle.

Approach and solution. The team should compare projected demand with tested throughput, add a safety margin, and validate the model against historical observations. If projected demand exceeds tested capacity, options include load balancing, caching, database optimisation and scheduled capacity expansion. The recurrence should be replaced or extended when arrival rates vary by time of day.

Outcome. The exponential model supplies a planning estimate, while the recurrence identifies long-run queue behaviour under stable conditions. Neither model alone proves that the service will perform acceptably.

Learning points. Model choice depends on the mechanism of change. Percentage growth suggests an exponential model; constant additions suggest a linear model. Recurrence relations are useful for operational cycles, but assumptions must be monitored. Capacity decisions should use measured data, stress testing and uncertainty ranges rather than a single predicted number.

8. Limitations, Governance and Best Practice

Mathematical models simplify reality. Linear models may fail when prices are tiered; exponential models may fail when resources or markets saturate; polynomial fits may oscillate or extrapolate dangerously; and recurrence models may omit delays, randomness or feedback. A good analyst states the domain, time horizon, units, initial conditions and parameter sources.

In IT, model outputs can influence resource allocation, fraud detection and access decisions. Governance therefore requires traceable data, documented assumptions, validation, monitoring and appropriate human review. A model trained or calibrated on biased historical data can reproduce unequal outcomes. Automation does not remove accountability: a responsible professional checks whether the model is suitable, interpretable and safe for the decision being made.

Best practice includes:

1. define the problem and variables before selecting a formula;
2. check units and boundary conditions;
3. distinguish interpolation from extrapolation;
4. test predictions against observed data;
5. perform sensitivity analysis by changing uncertain parameters;
6. report approximate values with appropriate precision;
7. document assumptions and revise the model when conditions change.

Chapter Summary

Functions assign one output to each permitted input and provide the foundation for computational and quantitative models. Linear functions describe constant additive change, while polynomial functions represent algebraic relationships with roots and turning points. Exponential functions model constant proportional growth or decay; logarithms reverse exponentiation and are useful for solving unknown exponents and representing large scales.

Graphs reveal intercepts, trends, extrema, discontinuities, asymptotes and transformations, but their interpretation depends on honest axes and units. Arithmetic sequences have constant differences, geometric sequences have constant ratios, and their finite or infinite sums require different conditions. Recurrence relations describe iterative processes. First-order linear recurrences can be solved explicitly and interpreted through equilibrium and stability. Algorithmic recurrences connect directly with complexity classes such as logarithmic, linear and quadratic growth.

In professional IT practice, models support capacity planning, storage estimation, performance analysis and algorithm selection. Their value depends on valid assumptions, verified calculations, empirical validation and responsible governance.

Key Terms

Function: A rule assigning exactly one output to each input in its domain.

Domain: The set of permitted inputs.

Codomain: The declared set in which function outputs are placed.

Range: The set of outputs actually produced.

Composition: Applying one function to the output of another.

Inverse function: A function that reverses a one-to-one function.

Slope: Change in output divided by change in input.

Polynomial: A finite sum of non-negative integer powers of a variable.

Root: An input for which a function’s output is zero.

Discriminant: The quantity b²−4ac for a quadratic equation.

Exponential function: A function with the variable in the exponent.

Logarithm: The inverse operation of exponentiation.

Sequence: An ordered list indexed by position.

Arithmetic sequence: A sequence with constant successive difference.

Geometric sequence: A sequence with constant successive ratio.

Recurrence relation: A rule defining terms from earlier terms.

Equilibrium: A value that remains unchanged under a recurrence rule.

Asymptote: A line that a graph approaches in a specified limiting sense.

Extrapolation: Predicting beyond the observed or modelled data range.

Algorithmic complexity: The growth of resource requirements as input size increases.

Review Questions

5 Short Answer Questions

1. What is the difference between a function’s codomain and its range?
2. State the slope formula for two points and explain its units.
3. What condition makes an exponential function represent decay?
4. Define an arithmetic sequence and give its explicit formula.
5. Why does a recurrence-based algorithm require a base case?

5 Long Answer Questions

1. Explain domain, range, inverse functions and one-to-one behaviour using a suitable example.
2. Compare linear, polynomial and exponential models, including one appropriate IT application for each.
3. Explain how intercepts, asymptotes and transformations help interpret a graph.
4. Derive the closed form of the recurrence xₙ=axₙ₋₁+c for a≠1 and discuss stability.
5. Discuss the assumptions and limitations of using exponential growth for capacity planning.

3 Analytical / Application Questions

1. A service starts with 5,000 users and grows by 9% per quarter. Construct a model, estimate the number after eight quarters, and explain two reasons the estimate may be inaccurate.
2. A queue follows Qₙ=0.6Qₙ₋₁+80, with Q₀=300. Find the equilibrium and Q₄, then interpret the result.
3. An algorithm satisfies T(n)=T(n/2)+4 for powers of two and T(1)=2. Generate the first few values, identify its growth class, and explain why the base case matters.

Multiple Choice Questions with Answers

Question 1

Which statement best defines a function?

A. Every output has exactly one input

B. Each permitted input has exactly one output

C. Every input has at least two outputs

D. Inputs and outputs must be equal

Correct Answer: B. Each permitted input has exactly one output

Question 2

If f(x)=2x+1 and g(x)=x², what is (f∘g)(x)?

A. (2x+1)²

B. x²+1

C. 2x²+1

D. 2x+2

Correct Answer: C. 2x²+1

Question 3

What is the slope through (2,5) and (6,13)?

A. 2

B. 4

C. 8

D. −2

Correct Answer: A. 2

Question 4

For f(x)=x²−5x+6, which are the roots?

A. 1 and 6

B. 2 and 3

C. −2 and −3

D. 5 and 6

Correct Answer: B. 2 and 3

Question 5

A quantity grows by 10% per period from an initial value A₀. Which model is appropriate?

A. A₀+0.10t

B. A₀(0.10)^t

C. A₀(1.10)^t

D. A₀t+10

Correct Answer: C. A₀(1.10)^t

Question 6

What is the domain of log_b(x) over the real numbers?

A. All real numbers

B. x≥0

C. x>0

D. x<0

Correct Answer: C. x>0

Question 7

What characterises an arithmetic sequence?

A. A constant ratio

B. A constant difference

C. A changing difference and ratio

D. Terms that must all be positive

Correct Answer: B. A constant difference

Question 8

For a₁=3 and r=2, what is the fourth term of the geometric sequence?

A. 6

B. 9

C. 12

D. 24

Correct Answer: D. 24

Question 9

For xₙ=0.5xₙ₋₁+10, what is the equilibrium value?

A. 5

B. 10

C. 20

D. 50

Correct Answer: C. 20

Question 10

The recurrence T(n)=T(n/2)+c generally has which complexity class?

A. O(1)

B. O(log n)

C. O(n)

D. O(n²)

Correct Answer: B. O(log n)