# COMPSCI 70 Study Guide - Quiz Guide: Alistair Sinclair, Mathematical Induction, 3 WomenExam

by OC2707247

Department

Computer ScienceCourse Code

COMPSCI 70Professor

Rao SatishStudy Guide

QuizThis

**preview**shows pages 1-2. to view the full**8 pages of the document.**CS 70 Discrete Mathematics and Probability Theory

Fall 2018 Alistair Sinclair and Yun Song HW 2

1 Hit or Miss?

State which of the proofs below is correct or incorrect. For the incorrect ones, please explain

clearly where the logical error in the proof lies. Simply saying that the claim or the induction

hypothesis is false is not a valid explanation of what is wrong with the proof. You do not need to

elaborate if you think the proof is correct.

(a) Claim: For all positive numbers n∈R,n2≥n.

Proof. The proof will be by induction on n.

Base Case: 12≥1. It is true for n=1.

Inductive Hypothesis: Assume that n2≥n.

Inductive Step: We must prove that (n+1)2≥n+1. Starting from the left hand side,

(n+1)2=n2+2n+1

≥n+1.

Therefore, the statement is true.

(b) Claim: For all negative integers n,(−1) + (−3) + ··· + (2n+1) = −n2.

Proof. The proof will be by induction on n.

Base Case: −1=−(−1)2. It is true for n=−1.

Inductive Hypothesis: Assume that (−1) + (−3) + ·· · + (2n+1) = −n2.

Inductive Step: We need to prove that the statement is also true for n−1 if it is true for n, that

is, (−1) + (−3) + ·· · + (2(n−1) + 1) = −(n−1)2. Starting from the left hand side,

(−1) + (−3) + ·· · + (2(n−1) + 1) = ((−1) + (−3) + ··· + (2n+1)) + (2(n−1) + 1)

=−n2+ (2(n−1) + 1)(Inductive Hypothesis)

=−n2+2n−1

=−(n2−2n+1)

=−(n−1)2.

Therefore, the statement is true.

(c) Claim: For all nonnegative integers n, 2n=0.

CS 70, Fall 2018, HW 2 1

Only pages 1-2 are available for preview. Some parts have been intentionally blurred.

Proof. We will prove by strong induction on n.

Base Case: 2×0=0. It is true for n=0.

Inductive Hypothesis: Assume that 2k=0 for all 0 ≤k≤n.

Inductive Step: We must show that 2(n+1) = 0. Write n+1=a+bwhere 0 <a,b≤n. From

the inductive hypothesis, we know 2a=0 and 2b=0, therefore,

2(n+1) = 2(a+b) = 2a+2b=0+0=0.

The statement is true.

Solution:

(a) Note that nis a real number. The proof is incorrect because it does not consider 0 <n<1, for

which the claim is false. Also, by the way it is set up, it can only cover integers for n≥1.

(b) The proof is correct. The base case starts from the correct, identiﬁable end point, then the

inductive step successfully proves that the statement continues to be true towards −∞.

(c) The proof is incorrect. When n=0, we cannot write n+1=1=a+bwhere 0 <a,b≤n=0.

2 A Coin Game

Your "friend" Stanley Ford suggests you play the following game with him. You each start with a

single stack of ncoins. On each of your turns, you select one of your stacks of coins (that has at

least two coins) and split it into two stacks, each with at least one coin. Your score for that turn is

the product of the sizes of the two resulting stacks (for example, if you split a stack of 5 coins into

a stack of 3 coins and a stack of 2 coins, your score would be 3 ·2=6). You continue taking turns

until all your stacks have only one coin in them. Stan then plays the same game with his stack of

ncoins, and whoever ends up with the largest total score over all their turns wins.

Prove that no matter how you choose to split the stacks, your total score will always be n(n−1)

2.

(This means that you and Stan will end up with the same score no matter what happens, so the

game is rather pointless.)

Solution:

We can prove this by strong induction on n.

Base Case: If n=1, you start with a stack of one coin, so the game immediately terminates. Your

total score is zero–and indeed, n(n−1)

2=1·0

2=0.

Inductive Hypothesis: Suppose that if you start with icoins (for ibetween 1 and ninclusive),

your score will be i(i−1)

2no matter what strategy you employ.

Inductive Step: Now suppose you start with n+1 coins. In your ﬁrst move, you must split your

stack into two smaller stacks. Call the sizes of these stacks s1and s2(so s1+s2=n+1 and

s1,s2≥1). Your end score comes from three sources: the points you get from making this ﬁrst

CS 70, Fall 2018, HW 2 2

###### You're Reading a Preview

Unlock to view full version

Only pages 1-2 are available for preview. Some parts have been intentionally blurred.

split, the points you get from future splits involving coins from stack 1, and the points you get

from future splits involving coins from stack 2. From the rules of the game, we know you get s1s2

points from the ﬁrst split. From the inductive hypothesis (which we can apply because s1and s2

are between 1 and n), we know that the total number of points you get from future splits of stack

1 is s1(s1−1)

2and similarly that the total number of points you get from future splits of stack 2 is

s2(s2−1)

2, regardless of what strategy you employ in splitting them. Thus, the total number of points

we score is

s1s2+s1(s1−1)

2+s2(s2−1)

2=s1(s1−1) + 2s1s2+s2(s2−1)

2

=s1(s1−1) + s1s2+s2(s2−1) + s1s2

2

=s1(s1+s2−1) + s2(s1+s2−1)

2

=(s1+s2)(s1+s2−1)

2

Since s1+s2=n+1, this works out to (n+1)(n+1−1)

2, which is what we wanted to show your total

number of points came out to. This completes our proof by induction.

3 Grid Induction

Pacman is walking on an inﬁnite 2D grid. He starts at some location (i,j)∈N2in the ﬁrst quadrant,

and is constrained to stay in the ﬁrst quadrant (say, by walls along the x and y axes). Every second

he does one of the following (if possible):

(i) Walk one step down, to (i,j−1).

(ii) Walk one step left, to (i−1,j).

For example, if he is at (5,0), his only option is to walk left to (4,0); if Pacman is instead at (3,2),

he could walk either to (2,2)or (3,1).

Prove by induction that no matter how he walks, he will always reach (0,0)in ﬁnite time. (Hint:

Try starting Pacman at a few small points like (2,1)and looking all the different paths he could

take to reach (0,0). Do you notice a pattern?)

Solution:

Following the hint, we notice that it seems as though Pacman takes i+jseconds to reach (0,0)

if he starts in position (i,j), regardless of what path he takes. This would imply that he reaches

(0,0)in a ﬁnite amount of time since i+jis a ﬁnite number. Thus, if we can prove this stronger

statement, we’ll also have proved that Pacman reaches (0,0)in ﬁnite time. In order to simplify the

induction, we will induct on the quantity i+jrather than inducting on iand jseparately.

Base Case: If i+j=0, we know that i=j=0, since iand jmust be non-negative. Hence, we

have that Pacman is already at position (0,0)and so will take 0 =i+jsteps to get there.

CS 70, Fall 2018, HW 2 3

###### You're Reading a Preview

Unlock to view full version