[net.ai] Proof by induction, fun & entertainment

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