The Role of Theory in Computer Science - Models of Computation: Exploring the Power of Computing - page 15

section we saw proof by reduction: in each step the condition to be established was translated
into another condition until a condition was found that was shown to be true.
Proofs by induction use predicates , that is, functions of the kind P : ￿

→B

.The

truth value of the predicate P : ￿ on the natural number n , denoted P ( n ) ,is1or0

depending on whether or not the predicate is Tr u e or False .
Proofs by induction are used to prove statements of the kind, “For all natural numbers
n ,predicate(orproperty) P is true.” Consider the function S 1 : ￿

→B

→

defined by the

following sum:

n

S 1 ( n )= j (1.1)

j = 1

We use induction to prove that S 1 ( n )= n ( n + 1 ) / 2istrueforeach n

∈

.

DEFINITION 1.3.1 A proof by induction has a predicate P ,a basis step ,an induction hy-
pothesis ,andan inductive step . The basis establishes that P ( k ) is true for integer k .The
induction hypothesis assumes that for some fixed but arbitrary natural number n

k ,thestate-
ments P ( k ) , P ( k + 1 ) , ... , P ( n ) are true. The inductive step is a proof that P ( n + 1 ) is true
given the induction hypothesis.

≥

It follows from this definition that a proof by induction with the predicate P establishes
that P is true for all natural numbers larger than or equal to k because the inductive step
establishes the truth of P ( n + 1 ) for arbitrary integer n greaterthanorequalto k .Aso,
induction may be used to show that a predicate holds for a subset of the natural numbers. For
example, the hypothesis that every even natural number is divisible by 2 is one that would be
defined only on the even numbers.
The following proof by induction shows that S 1 ( n )= n ( n + 1 ) / 2for n

≥

0.

LEMMA 1.3.1 For all n ≥ 0 , S 1 ( n )= n ( n + 1 ) / 2 .
Proof PREDICATE: Thevalueofthepredicate P on n , P ( n ) ,is Tr u e if S 1 ( n )= n ( n +
1 ) / 2and False otherwise.
BASIS STEP: Clearly, S 1 ( 0 )= 0 from both the sum and the closed form given above.
INDUCTION HYPOTHESIS: S 1 ( k )= k ( k + 1 ) / 2for k = 0, 1, 2, ... , n .
INDUCTIVE STEP: By the definition of the sum for S 1 given in ( 1.1 ), S 1 ( n + 1 )= S 1 ( n )+
n + 1. Thus, it follows that S 1 ( n + 1 )= n ( n + 1 ) / 2 + n + 1. Factoring out n + 1and
rewriting the expression, we have that S 1 ( n + 1 )=( n + 1 )(( n + 1 )+ 1 ) / 2, exactly the
desired form. Thus, the statement of the theorem follows for all values of n .

We now define proof by contradiction.

DEFINITION 1.3.2 A proof by contradiction has a predicate P . The complement ¬P of P is
shown to be False , which implies that P is Tr u e .

} ∗ suggest that L
contains only strings other than with an odd number of 1's. Let P be the predicate “ L
contains strings other than with an even number of 1's.” We show that it is true by assuming

The examples shown earlier of strings in the language L = { 00 ∪ 1