dick@tjalk.UUCP (Dick Grune) (09/21/84)
Claim: All elements of an array A[1..n] are equal to its first element. Proof by induction: Starting case: n = 1. Proof: Obvious, since A[1] = A[1]. Induction step: If the Claim is true for n = N, it is true for n = N + 1. Proof: All elements of A[1..N] are equal (premise), and since A[2..N+1] is an array of length N too, all its elements are equal too. A[N] is in both (sub-)arrays, so A[1] = A[N] and A[N] = A[N+1] -> A[1] = A[N+1] which makes all of A[1..N+1] equal. End of proof of induction step The starting case and the induction step together prove the Claim. End of proof by induction Courtesy of Dick Grune Vrije Universiteit Amsterdam the Netherlands