CS 70 Discrete Mathematics for CS

Fall 2004  Rao  HW 1

Due Thu, September 9 at 3:29PM (283 Soda or in-class)

1. (10 pts.) Todo.

If you haven.t already done so, you should get an account on cory.eecs. You.ll be able to use your account to read the newsgroup (ucb.class.cs70), LATEX your homework, etc. You can get an account by logging in as newacct with password newacct at any terminal on the second floor of Soda Hall and following the prompts.

2. (5 pts.) Any questions? What’s the one thing you’d most like to see explained better in lecture or discussion sections? A one-line answer would be appreciated.

3. (15 pts.) Inference rules For each of the following, define proposition symbols for each simple proposition in the argument (for example, P = “The Bears will win next Saturday”). Then write out the logical form of the argument. If the argument form corresponds to a known inference rule, say which it is. If not, show that the proof is correct using truth tables.

(a) The sun will shine today or It will be cloudy today. It is not cloudy today. Thus the sun will shine today.

(b) The car is blue. Thus, the car is blue or the car goes fast.

(c) Nomar played in the Cubs game last night. If Nomar plays last night and he has any chance to score, he will score a run. If he scores a run, the Cubs can not draw 0-0 with the Braves last night. Last night, the Cubs drew 0-0 with the Braves. Hence, Nomar did not have any chance last night.

(d) The Bears will win next Saturday and next Sunday. Therefore, the Bears will win next Saturday.

(e) A robot can pick up the green block if it is clear. The green block is clear if the blue block is not on the green block. The blue block is not on top of the green block. Therefore, the robot can pick up the green block.

4. (20 pts.) Prove or disprove: (In the following, the notation ⌈x⌉, the ceiling of x, denotes the smallest integer greater than or equal to the real number x. The notation ⌊x⌋, the floor of x, denotes the largest integer less than or equal to the real number x. See Rosen, p.65.)

(a) Every positive integer can be expressed as the sum of two squares.

(b) Every positive integer can be expressed as the sum of three squares.

(c) ⌊⌈x⌉⌋ = ⌈x⌉ for all real x.

(d) ⌊x + y⌋ = ⌊x⌋ + ⌊y⌋ for all real x, y.

(e) ⌊\sqrt{⌈x⌉}⌋ = ⌊\sqrt{x}⌋ for all real x > 0.

(f) For all rational numbers a and b, a^{b} is also rational.

5. (15 pts.) Simple induction Prove that 2^{n} < n! for all large enough integers n > n_{0}. What is n_{0}.

6. (20 pts.) Strengthening the claim

The following is an example where it is easier to prove a stronger result than a weaker one:

(a) Try to prove by induction that 1 + 1/4 + 1/9 + ··· + 1/n^{2} < 2 for all positive integers n. What happens?

(b) (Extra credit) Prove the same inequality using calculus. [Hint: find an integral whose value is related to that of the series.]

(c) Prove by induction that 1 + 1/4 + 1/9 + ··· + 1/n^{2} < 2 − 1/n for all positive integers n.

7. (15 pts.) Less simple induction Prove that n infinite straight lines divide the plane into (n^{2}+ n + 2)/2 regions, provided no lines are parallel and no three lines meet at a point.