Mathematical induction and invariants

Let P(n) be a property for integers n at least a declared starting value. Induction asks for a proof of P at that starting value and a proof that for every allowed k, P(k) implies P(k + 1). The base establishes one actual truth. The step establishes a conditional rule for arbitrary k; it does not independently assert that P(k) is true. Together they propagate truth to every later integer, by the induction principle for natural numbers.

A missing base leaves the propagation rule with nothing to propagate. A missing step leaves isolated checked instances. The start need not be zero or one: an inequality might hold only from four onward, and then four is the appropriate base. Explicitly state that boundary because the formula for the step may divide by an expression or use an inequality that fails earlier. Extra tested cases are useful for debugging but do not substitute for either required component.

For a sum formula, write the sum through k plus one as the sum through k followed by its new term. The induction hypothesis can replace only the part already covered by k. After that substitution, algebra must reach the formula with k plus one in place of n. Starting with the desired next-case equality and silently invoking it during simplification is circular. You can explore backward, but present a justified implication from the known k-case.

An overly weak claim can make the successor step difficult because it forgets useful information. In a process with several stored quantities, the right invariant may relate all of them rather than constrain just the final output. Strengthening an induction statement adds a proof obligation, yet can make preservation easier by retaining the relationship needed by the update rule. Conversely, an overly strong assertion may be false at initialization. Testing the first few states helps identify a plausible property before proving it.

An invariant is a property true initially and preserved by each allowed transition. If a loop maintains accumulator s and counter k while adding successive integers, a useful property relates s to the sum of the first k integers. Initialization establishes it before the loop, preservation follows from the update equations, and the stopping condition turns it into the desired output claim. Correctness also needs termination when a result is promised; an invariant alone permits a process that runs forever.

The deterministic gradient-descent lab provides another exact recurrence: the next position is one minus the step size times the current position. For a fixed step size strictly between zero and two, the absolute multiplier is less than one. Thus an initially bounded absolute position remains bounded after each update. That invariant is weaker than convergence to zero, which needs an additional geometric-decay argument. Separate the property preserved at every step from the limiting claim about infinitely many steps.