C05: Induction, counting, recurrences, graphs, and modular arithmetic

A. Prerequisites and observable goals#

Level: Degree core.

B. The central question: how does a small step establish an unbounded family?#

Induction proves a statement $P(n)$ for every integer $n$ from a starting point onward. Prove the base case. Then, for an arbitrary admissible $k$, assume $P(k)$ and prove $P(k+1)$. The induction hypothesis is a conditional tool inside the step, not permission to assume the final theorem. The base case starts the chain, and the step connects every consecutive link.

For $1+2+\cdots+n=n(n+1)/2$, the base case $n=0$ uses the empty sum zero. Assuming the formula for $k$, add the next term:

The first equality is where the induction hypothesis is used. Writing down the desired formula for $k+1$ without deriving it would be circular. Loop invariants have the same structure: initialization is the base case, preservation is the induction step, and loop termination connects the invariant with the postcondition.

C. Strong and structural induction#

Strong induction permits assuming all earlier cases within the declared range when proving the next case. It is useful when an object depends on several smaller sizes, not just one. To prove every integer $n\ge18$ is expressible as $4a+7b$ with nonnegative integers $a,b$, establish 18, 19, 20, and 21. For $n\ge22$, the smaller $n-4\ge18$ is covered, and adding one 4 completes the representation. Four base cases are needed because the step moves backward by four.

Structural induction follows the way objects are built. A full binary tree is either a leaf or an internal node with two full binary subtrees. Prove a property for a leaf, then prove that combining any two subtrees with the property produces a tree with the property. For the identity $L=I+1$ between leaves and internal nodes, a leaf has $L=1,I=0$. Combining subtrees gives $L=L_1+L_2=(I_1+1)+(I_2+1)=I+1$ because the new root makes $I=I_1+I_2+1$. The definition “full” matters: arbitrary one-child nodes would invalidate this formula.

D. Counting: identify choices before applying formulas#

The product rule counts a sequence of choices when each partial choice has a known number of continuations. Choosing an ordered list of $k$ distinct elements from $n$ gives $n(n-1)\cdots(n-k+1)$. If order does not matter, each selected subset was counted $k!$ times, yielding $\binom nk=n!/[k!(n-k)!]$. With replacement and ordered positions, the count is $n^k$. None of these formulas can be selected correctly until order and replacement are specified.

Inclusion–exclusion corrects double counting: $|A\cup B|=|A|+|B|-|A\cap B|$. For three sets, subtract pairwise intersections and add the triple intersection once. The pigeonhole principle says that placing more than $m$ objects into $m$ boxes forces a box to contain at least two. More generally, some box holds at least $\lceil n/m\rceil$ among $n$ objects. A hash table with more possible keys than hash outputs must have collisions. This fact does not say how frequent collisions are under a particular workload or how efficiently they are handled.

E. Recurrences count the work generated by recursion#

If a divide-and-conquer algorithm splits an input into two equal subproblems and does $cn$ additional work, a model is $T(n)=2T(n/2)+cn$, with $T(1)=d$, initially for powers of two. At each of $\log_2 n$ internal levels, the combined nonrecursive work is $cn$. The $n$ leaves contribute $dn$. Therefore $T(n)=cn\log_2n+dn=\Theta(n\log n)$. The recurrence describes a cost model, not a measured runtime or a proof of the algorithm’s output correctness.

A naive recursive Fibonacci implementation repeats subproblems: $F(n-1)$ and $F(n-2)$ each recompute many earlier values. Memoization or iteration changes the computation graph and can reduce the number of distinct subproblems to $n+1$. A recurrence must match the actual implementation; writing a familiar formula beside different code does not analyze it.

A graph consists of vertices and edges. In a finite undirected simple graph, the sum of all vertex degrees equals $2|E|$, because every edge contributes one to each endpoint’s degree. A tree is connected and acyclic. Removing a leaf from a nontrivial finite tree leaves a smaller tree, enabling the induction proof $|E|=|V|-1$. A disconnected acyclic graph is a forest, not a tree; the number of components changes the formula. C08 uses these distinctions in traversal and spanning-tree algorithms.

F. Modular arithmetic retains the information a problem needs#

Congruence $a\equiv b\pmod m$ means $m$ divides $a-b$, with positive modulus $m$. Addition and multiplication respect congruence, so large intermediate powers can be reduced modulo $m$ without changing the final residue. This is useful for cyclic indexing and number-theoretic algorithms. It does not justify arbitrary division: a modular inverse of $a$ exists exactly when $\gcd(a,m)=1$. For example, $3\cdot5\equiv1\pmod7$, so 5 is the inverse of 3 modulo 7; 2 has no inverse modulo 6.

Euclid’s algorithm repeatedly replaces $(a,b)$ by $(b,a\bmod b)$. The gcd is unchanged because a common divisor divides $a$ and $b$ exactly when it divides $b$ and $a-qb$. Nonnegative remainders strictly decrease until zero, proving termination. Repeated squaring computes $a^e\bmod m$ in $O(\log(e+1))$ modular multiplication steps by reading the exponent’s binary expansion. The lab is mathematical computation, not a cryptographic implementation: timing behavior, parameter validation, key handling, and side channels require specialized libraries and analysis.

G. Independent practice#

F foundation C standard course work T transfer S optional stretch L runnable lab or project. Attempt the complete set before opening its solutions.

H. Complete solutions: C05#

Compare the first step where your work differs. A corrected answer is not yet an independent success.

Open every solution

"""C05.05: Euclid and repeated squaring."""
def gcd(a: int, b: int) -> int:
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b
    return a

def mod_power(base: int, exponent: int, modulus: int) -> int:
    if any(type(x) is not int for x in (base, exponent, modulus)):
        raise TypeError("integer arguments required")
    if exponent < 0 or modulus <= 0:
        raise ValueError("exponent >= 0 and modulus > 0 required")
    result = 1 % modulus
    base %= modulus
    while exponent:
        if exponent & 1:
            result = (result * base) % modulus
        base = (base * base) % modulus
        exponent //= 2
    return result

if __name__ == "__main__":
    print(gcd(252, 105), mod_power(7, 13, 11))

I. Retention and readiness#

Retrieve proof hypotheses, finite domains, and loop-state tracing. Advance when you can choose ordinary, strong, or structural induction from the dependency structure, and when a complexity recurrence includes an explanation of the operations it counts.