Basisfall

Basisfall, commonly called the base case, is the starting point of a proof by mathematical induction. When proving a statement P(n) for all integers n in a given range, one first confirms that P(n) holds for the smallest n in that range. This verification anchors the argument; without a valid base case, the inductive step alone cannot establish the result.

After establishing the base case, the inductive step shows that if the statement holds for some n, it also holds for n+1 (or for the next value in the range). Together, the base case and the induction step yield that P(n) is true for all n in the domain.

Sometimes multiple base cases are required, for example when the domain starts at a value greater than 0 or when using strong induction.

Examples: Prove that the sum of the first n natural numbers equals n(n+1)/2 for all n≥1. Base case n=1: 1 = 1(2)/2. Inductive step: assume true for n, then show for n+1. Another example is the Fibonacci sequence, where P(1) and P(2) are established as base cases before proving P(n)→P(n+1) via the recurrence.

Basisfall is distinct from the inductive step; both are needed. In computer science, the base case is also the termination condition for recursive algorithms.