1.7 Proof by induction

To prove P(n) for all integers n≥n₀, prove P(n₀), assume P(k) for an arbitrary k≥n₀, then use that assumption to prove P(k+1).

The assumption is used only for the arbitrary case, not asserted for every value without proof. State the domain and simplify the target P(k+1) until the expression contains the inductive hypothesis.

For 1+2+…+n=n(n+1)/2, the base case n=1 is true; adding k+1 to the assumed sum k(k+1)/2 gives (k+1)(k+2)/2.

Checking many numerical cases is not induction, and proving P(k)→P(k+1) without a valid base case proves nothing about the starting chain.

A conjecture is a statement suggested by patterns in initial cases. Induction can then prove it if the base case and inductive implication are valid for the stated domain.

Use small values to identify the likely formula, factorisation or invariant, but do not treat pattern matching as evidence of universal truth. Check parity, starting index and exceptional values before writing the proof.

The first differences of a sequence may suggest a quadratic formula. Test several terms, formulate P(n), then prove P(n₀) and P(k)⇒P(k+1) rather than extrapolating from the table.

A pattern that works for ten values can fail at the next; conjecture and proof are different learning jobs.