Maths Apps Unit 3 Exam Preparation Guide

Recurrence Relations

Using recurrence rules to calculate terms in a sequence.

Finding the recurrence relation

Using two equations to calculate the value of r and d.

tn+1 = rtn + d, t1 = a

General formula for recurrence relations.

Recurrence relations for arithmetic sequences

tn+1 = tn + d, t1 = a.

Recurrence relations for geometric sequences

tn+1 = rtn, t1 = a.

Graphical representation of recurrence relations

Interpreting graphs - arithmetic or geometric or neither.

Increase indefinitely

A behavior of a sequence where values grow without bound.

Decrease indefinitely

A behavior of a sequence where values shrink without bound.

Steady state solution

A solution where the sequence stabilizes over time.

Long term steady state solution

Calculating from recurrence relation for long-term behavior.

Basic concepts/definitions in Graphs

Vertices, edges, loop, isolated vertex, multiple edges.

Simple graph

A graph without loops or multiple edges.

Connected graph

A graph where there is a path between every pair of vertices.

Complete graph

A graph where every pair of vertices is connected; includes calculating using formula where n is the number of vertices.

Subgraph

A graph formed from a subset of vertices and edges of another graph.

Directed graph

A graph where edges have a direction.

Bipartite graph

A graph whose vertices can be divided into two disjoint sets.

Adjacency matrix

A matrix used to represent a graph, where rows and columns represent vertices.

Loop

1 edge that connects a vertex to itself.

Degree

Number of edges linked to the vertex; loops counted as 2.

Degree sum

2 x number of edges.

Planar Graphs

Graphs with no edges that cross.

Euler's Formula

V = E - F + 2, where V is vertices, E is edges, F is faces.

Walk

Can include repeated edges and vertices.

Path

Open or closed. No repeated edges or vertices.

Trail

Open or closed. Vertices repeated, edges not repeated.

Eulerian graph

Starts and finishes at the same vertex, includes every edge once only.

Semi-Eulerian

Starts and finishes at different vertices, includes every edge once only.

Hamiltonian path

Every vertex once only, starts and finishes at different vertices.

Hamiltonian cycle

Every vertex once only, starts and finishes at the same vertex.