Functions, Sequences, Summations, and Proof Techniques

1. FUNCTIONS

Definition
A function is a mathematical rule that defines a relationship between two sets. Think of it as a machine
that takes an input and produces exactly one output. Formally, a function f: A → B assigns to each
element x in a set A (called the domain) exactly one element y in a set B (called the codomain). The
actual set of outputs from a function is called the range.

Simple Analogy: A function is like a vending machine - you put in money (input) and get exactly one
item (output).

Key Concepts
Domain: The set of all possible inputs (like all the coins/bills the vending machine accepts)

Codomain: The set into which all outputs must fall (like all possible items in the vending machine)

Range: The set of actual outputs (like the items actually available for purchase)

Image: Another name for range

Pre-image: The input value(s) that produce a specific output

Function Notation
f(x) = y: function f applied to x gives y

f: A → B: f maps elements from set A to B

y = f(x): y is the image of x under function f

Simple Examples
a) Basic Mathematical Functions:
f(x) = x + 5 (adds 5 to any input)
f(3) = 3 + 5 = 8

f(0) = 0 + 5 = 5

g(x) = 2x (doubles any input)

g(4) = 2(4) = 8
g(-3) = 2(-3) = -6
 b) Real-World Examples:
Temperature conversion: C(F) = (F - 32) × 5/9
C(32) = 0°C (freezing point)
C(212) = 100°C (boiling point)

Area of a circle: A(r) = πr²

A(3) = π(3)² = 9π square units

c) Nigerian Context Examples:

Exchange rate: N(D) = D × 460 (dollars to naira)
N(100) = 46,000 naira

School fees calculator: F(c) = c × 50,000 (fee per credit unit)

F(20) = 1,000,000 naira for 20 credit units

d) Computer Science Examples:

Hash functions: h(x) = x mod 10 (maps data to table indexes 0-9)
h(157) = 7

h(2023) = 3

Types of Functions

1. Injective (One-to-One)

Different inputs always produce different outputs

Test: If f(a) = f(b), then a = b

Example: f(x) = 2x + 1
f(1) = 3, f(2) = 5, f(3) = 7 (all different outputs)

Real-world: Student ID numbers (each student has a unique ID)

2. Surjective (Onto)

Every element in the codomain has at least one pre-image in the domain

Range = Codomain

Example: f: ℝ → ℝ, f(x) = x³
Every real number has a cube root

Real-world: Every possible grade (A, B, C, D, F) is assigned to at least one student

3. Bijective (One-to-One and Onto)

 Each input corresponds to a unique output, AND every output is mapped

Invertible functions

Example: f(x) = 2x + 3 from ℝ to ℝ

Real-world: Passport numbers (each person has exactly one, and each number belongs to exactly
one person)

Function Composition
Combining functions: (g ∘ f)(x) = g(f(x))

Read as "g composed with f"

Apply f first, then apply g to the result

Examples:

1. f(x) = x + 1, g(x) = 2x
(g ∘ f)(x) = g(f(x)) = g(x + 1) = 2(x + 1) = 2x + 2
(g ∘ f)(3) = 2(3) + 2 = 8

2. f(x) = x², g(x) = x + 5

(g ∘ f)(x) = g(x²) = x² + 5

(f ∘ g)(x) = f(x + 5) = (x + 5)²

Note: (g ∘ f)(x) ≠ (f ∘ g)(x) in general

Inverse Functions
A function f has an inverse f⁻¹ if f is bijective

f⁻¹(f(x)) = x and f(f⁻¹(x)) = x

Steps to find inverse:
1. Replace f(x) with y

2. Swap x and y

3. Solve for y

4. Replace y with f⁻¹(x)

Example: f(x) = 2x + 3

1. y = 2x + 3

2. x = 2y + 3

3. 2y = x - 3, so y = (x - 3)/2
 4. f⁻¹(x) = (x - 3)/2

Verification: f(f⁻¹(x)) = f((x-3)/2) = 2((x-3)/2) + 3 = x - 3 + 3 = x ✓

Special Functions in Computer Science

1. Floor Function ⌊x⌋

Largest integer ≤ x

Examples: ⌊3.7⌋ = 3, ⌊-2.3⌋ = -3, ⌊5⌋ = 5

Use: Array indexing, memory allocation

2. Ceiling Function ⌈x⌉

Smallest integer ≥ x

Examples: ⌈3.7⌉ = 4, ⌈-2.3⌉ = -2, ⌈5⌉ = 5

Use: Determining number of pages needed, resource allocation

3. Modular Arithmetic: x mod n

Remainder when x is divided by n

Examples: 17 mod 5 = 2, -3 mod 5 = 2, 15 mod 5 = 0

Use: Hash tables, cyclic data structures, cryptography

Piecewise Functions
Functions defined by different rules on different intervals

Example: Absolute value function

|x| = { x if x ≥ 0
{ -x if x < 0

Real-world Example: Shipping cost function

Cost(w) = { 5 if 0 < w ≤ 1
{8 if 1 < w ≤ 3
{ 12 if 3 < w ≤ 5

2. SEQUENCES AND SUMMATIONS

Definition of Sequence
A sequence is a function from natural numbers to a set of values. It's an ordered list of elements, often
defined by a formula. Think of it as a numbered list where each position has a specific value.

Notation: {aₙ} or a₁, a₂, a₃, ... where n represents the position

Types of Sequences

a) Arithmetic Sequence

Each term increases by a fixed value (common difference d)

General form: aₙ = a₁ + (n - 1)d

First term: a₁

Common difference: d = aₙ₊₁ - aₙ

Examples:

1. 5, 8, 11, 14, 17, ... (d = 3)

a₁ = 5, aₙ = 5 + (n-1)×3 = 3n + 2

a₁₀ = 3(10) + 2 = 32

2. 100, 95, 90, 85, ... (d = -5)

a₁ = 100, aₙ = 100 + (n-1)×(-5) = 105 - 5n

a₆ = 105 - 5(6) = 75

Real-world: Monthly salary with fixed raises, seat numbers in a theater

b) Geometric Sequence

Each term is multiplied by a fixed ratio r

General form: aₙ = a₁ × r^(n-1)

First term: a₁

Common ratio: r = aₙ₊₁/aₙ

Examples:

1. 3, 6, 12, 24, 48, ... (r = 2)

a₁ = 3, aₙ = 3 × 2^(n-1)
a₅ = 3 × 2⁴ = 3 × 16 = 48

2. 1000, 500, 250, 125, ... (r = 0.5)

a₁ = 1000, aₙ = 1000 × (0.5)^(n-1)
 a₄ = 1000 × (0.5)³ = 1000 × 0.125 = 125

Real-world: Population growth, compound interest, radioactive decay

c) Fibonacci Sequence

Each term is the sum of the previous two

F₁ = 1, F₂ = 1, Fₙ = Fₙ₋₁ + Fₙ₋₂ for n ≥ 3

Sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

Examples:

F₃ = F₂ + F₁ = 1 + 1 = 2

F₆ = F₅ + F₄ = 5 + 3 = 8

F₁₀ = 55

Real-world: Rabbit population growth, spiral patterns in nature, financial markets

d) Special Sequences

Factorial Sequence: n! = n × (n-1) × (n-2) × ... × 2 × 1

1!, 2!, 3!, 4!, 5!, ... = 1, 2, 6, 24, 120, ...

0! = 1 (by definition)

Powers of 2: 2⁰, 2¹, 2², 2³, ... = 1, 2, 4, 8, 16, ...

Important in computer science (memory sizes, binary trees)

Recurrence Relations
Defines terms using previous ones.

Examples:

1. Linear Recurrence: T(n) = 2T(n-1) + 1, T(1) = 1

T(1) = 1

T(2) = 2(1) + 1 = 3

T(3) = 2(3) + 1 = 7

T(4) = 2(7) + 1 = 15

Solution: T(n) = 2ⁿ - 1

2. Divide and Conquer: T(n) = T(n/2) + 1, T(1) = 1

 Common in algorithms like binary search

Solution: T(n) = log₂ n + 1

3. Fibonacci: F(n) = F(n-1) + F(n-2), F(1) = F(2) = 1

Summation Notation
Summation uses the symbol Σ (sigma) to indicate repeated addition of terms.

General form: Σᵢ₌ₘⁿ aᵢ (read as "sum from i equals m to n of aᵢ")

i: index of summation (dummy variable)

m, n: lower and upper bounds

aᵢ: general term

Common Summation Formulas

1. Sum of first n natural numbers: Σᵢ₌₁ⁿ i = n(n+1)/2
Example: Σᵢ₌₁⁵ i = 1+2+3+4+5 = 15 = 5(6)/2

2. Sum of squares: Σᵢ₌₁ⁿ i² = n(n+1)(2n+1)/6

Example: Σᵢ₌₁³ i² = 1+4+9 = 14 = 3(4)(7)/6

3. Sum of cubes: Σᵢ₌₁ⁿ i³ = [n(n+1)/2]²

Example: Σᵢ₌₁³ i³ = 1+8+27 = 36 = [3(4)/2]² = 6²

4. Geometric series: Σᵢ₌₀ⁿ rⁱ = (rⁿ⁺¹ - 1)/(r - 1), r ≠ 1

Example: Σᵢ₌₀⁴ 2ⁱ = (2⁵-1)/(2-1) = 31

Step-by-Step Examples
Example 1: Calculate Σᵢ₌₁⁴ (2i + 1)

Method 1 (Direct): (2×1+1) + (2×2+1) + (2×3+1) + (2×4+1) = 3+5+7+9 = 24

Method 2 (Properties): Σᵢ₌₁⁴ (2i + 1) = 2Σᵢ₌₁⁴ i + Σᵢ₌₁⁴ 1 = 2(10) + 4 = 24

Example 2: Calculate Σᵢ₌₂⁵ i²

Direct: 2² + 3² + 4² + 5² = 4 + 9 + 16 + 25 = 54

Using formula: Σᵢ₌₁⁵ i² - Σᵢ₌₁¹ i² = 55 - 1 = 54

Properties of Summation
1. Linearity: Σ(aᵢ + bᵢ) = Σaᵢ + Σbᵢ

2. Constant Multiple: Σ(c × aᵢ) = c × Σaᵢ

 3. Splitting: Σᵢ₌₁ⁿ aᵢ = Σᵢ₌₁ᵏ aᵢ + Σᵢ₌ₖ₊₁ⁿ aᵢ

4. Index Shifting: Σᵢ₌₁ⁿ aᵢ = Σⱼ₌₀ⁿ⁻¹ aⱼ₊₁

Applications in Computer Science

Time Complexity Analysis: Nested loops create summations
for i = 1 to n: for j = 1 to i: ... gives Σᵢ₌₁ⁿ i = O(n²)

Algorithm Analysis: Merge sort, quick sort

Data Structure Operations: Array processing, tree traversals

Probability: Expected values, variance calculations

3. PROOF TECHNIQUES

Why Proofs Are Important

Proofs provide rigorous verification of mathematical statements and ensure algorithm correctness. In
computer science, proofs:

Verify program correctness

Analyze algorithm efficiency

Establish security properties

Validate mathematical models

Structure of a Proof
Every proof should have:

a) Statement: What you're proving

b) Given: What you know (assumptions)

c) To Prove: What you need to show

d) Proof: Logical steps from given to conclusion

e) Conclusion: Restatement of what was proved

Types of Proof Techniques

a) Direct Proof

Start from known facts and logically deduce the conclusion using definitions, previously proven theorems,
and logical rules.

Template:
 Given: P (premise)

To Prove: Q (conclusion)

Proof: P → ... → Q

Example 1: Prove that if n is even, then n² is even.

Given: n is even

To Prove: n² is even

Proof:
Since n is even, n = 2k for some integer k
Then n² = (2k)² = 4k² = 2(2k²)

Since 2k² is an integer, n² is even

Example 2: Prove that the sum of two odd numbers is even.

Given: a and b are odd integers

To Prove: a + b is even

Proof:
Since a is odd, a = 2m + 1 for some integer m

Since b is odd, b = 2n + 1 for some integer n

Then a + b = (2m + 1) + (2n + 1) = 2m + 2n + 2 = 2(m + n + 1)

Since (m + n + 1) is an integer, a + b is even

b) Proof by Contrapositive

Instead of proving P → Q, prove ¬Q → ¬P (contrapositive)

Logically equivalent to the original statement

Often easier when the contrapositive is more natural to prove

Example: Prove that if n² is odd, then n is odd.

Direct approach is difficult

Contrapositive: If n is even, then n² is even

Proof:
Assume n is even, so n = 2k for some integer k

Then n² = (2k)² = 4k² = 2(2k²)

Since 2k² is an integer, n² is even

 Therefore, if n² is odd, then n must be odd

c) Proof by Contradiction

Assume the opposite of what you want to prove and show it leads to a logical contradiction.

Template:

Given: P

To Prove: Q

Proof: Assume ¬Q, derive a contradiction, conclude Q

Example 1: Prove that √2 is irrational.

Assume: √2 is rational

Then: √2 = p/q where p, q are integers with no common factors

Squaring: 2 = p²/q², so 2q² = p²

This means: p² is even, so p is even

Let: p = 2k, then 2q² = (2k)² = 4k², so q² = 2k²

This means: q² is even, so q is even

Contradiction: Both p and q are even, contradicting "no common factors"

Conclusion: √2 is irrational

Example 2: Prove there are infinitely many prime numbers.

Assume: There are finitely many primes: p₁, p₂, ..., pₖ

Consider: N = p₁ × p₂ × ... × pₖ + 1

Analysis: N > 1, so N has a prime divisor p

If: p is one of p₁, p₂, ..., pₖ, then p divides N - (p₁ × p₂ × ... × pₖ) = 1

Contradiction: No prime divides 1

Conclusion: There are infinitely many primes

d) Proof by Cases

Divide the domain into exhaustive cases and prove each separately.

Example 1: Prove n² - n is even for all integers n.

Case 1 (n is even): n = 2k
n² - n = (2k)² - 2k = 4k² - 2k = 2(2k² - k)
 Since (2k² - k) is an integer, n² - n is even

Case 2 (n is odd): n = 2k + 1
n² - n = (2k+1)² - (2k+1) = 4k² + 4k + 1 - 2k - 1 = 4k² + 2k = 2(2k² + k)

Since (2k² + k) is an integer, n² - n is even

Conclusion: n² - n is even for all integers n

Example 2: Prove |xy| = |x||y| for all real numbers x, y.

Case 1 (x ≥ 0, y ≥ 0): xy ≥ 0, so |xy| = xy = |x||y|

Case 2 (x ≥ 0, y < 0): xy ≤ 0, so |xy| = -xy = x(-y) = |x||y|

Case 3 (x < 0, y ≥ 0): xy ≤ 0, so |xy| = -xy = (-x)y = |x||y|

Case 4 (x < 0, y < 0): xy > 0, so |xy| = xy = (-x)(-y) = |x||y|

Conclusion: |xy| = |x||y| for all real numbers x, y