Discrete Mathematics for Computer Science

56 CHAPTER 1 Sets, Proof Templates, and Induction

Corollary 1 gives a formula for finding the sum of a finite geometric series.

Example 5.

(a) 1 + 3 + 32 + 33 +... + 3 = (1 - 3n+1)/(-2) = (3n+l - 1)/2.

(b) 2+10+50+...+1250=2+2.5+2-52+2.53+2.54

= 2(1 - 55)/(-4)

= 1562

The next example shows how to compute the sum when the first term does not clearly

correspond to what is expected for a term of the form a • r°.

Example 6. Find the sum of

3.2+3.22 +3.23 +... +3.2n

Solution. Rewrite the expression with 3. 2 = 6 as a factor of each term:

(6.2' + 6.21 +... +6.2n-1)

We now have a geometric series with n terms with a = 6 and r = 2. The sum is

n-1

E 6.2i = 6. (1 - 2n)/(-1) = 6. (2 - 1)

i=0

Program Correctness

An important problem in computer science is to prove that a program executes correctly

for all possible data sets. There is no simple way to do this. In fact, it is impossible in

principle to prove correctness for very complicated programs. Many techniques, however,

are useful for proving the correctness of a wide variety of programs.

One method for checking the correctness of a program is to test the program on lots of

data to make sure it comes up with the right answers in each case. Obviously, this technique

is useful, but it can be used only to find errors, not to establish correctness. The problem is

that if no errors are found by running a program on test data, the only conclusion one can

draw with any assurance is that the program works correctly on all the data tested.

Another useful technique is to prove mathematically that the algorithms (the principles

behind the program) are correct. Such proofs are often proofs by induction.

Before we examine some algorithms, we need to explain how we will present the steps

of an algorithm. The language we use is called a pseudocode, because it is a mixture of

normal language and the precise syntax of a programming language.

1.8.1 Pseudocode Conventions

A variable will simply be a name that will represent a place in a computer to store a value.

When we use a variable, like X, we are referring to the value that is stored in the location

the machine assigns to X. A simple assignment statement of the form

variable = expression