Get 2 days of premium access
Study Guides (380,000)
US (220,000)
Berkeley (5,000)
COMPSCI (500)
Quiz

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


Department
Computer Science
Course Code
COMPSCI 70
Professor
Rao Satish
Study Guide
Quiz

This 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 nR,n2n.
Proof. The proof will be by induction on n.
Base Case: 121. It is true for n=1.
Inductive Hypothesis: Assume that n2n.
Inductive Step: We must prove that (n+1)2n+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 n1 if it is true for n, that
is, (1) + (3) + ·· · + (2(n1) + 1) = (n1)2. Starting from the left hand side,
(1) + (3) + ·· · + (2(n1) + 1) = ((1) + (3) + ··· + (2n+1)) + (2(n1) + 1)
=n2+ (2(n1) + 1)(Inductive Hypothesis)
=n2+2n1
=(n22n+1)
=(n1)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 kn.
Inductive Step: We must show that 2(n+1) = 0. Write n+1=a+bwhere 0 <a,bn. 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 n1.
(b) The proof is correct. The base case starts from the correct, identifiable 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,bn=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(n1)
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(n1)
2=1·0
2=0.
Inductive Hypothesis: Suppose that if you start with icoins (for ibetween 1 and ninclusive),
your score will be i(i1)
2no matter what strategy you employ.
Inductive Step: Now suppose you start with n+1 coins. In your first 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,s21). Your end score comes from three sources: the points you get from making this first
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 first 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(s11)
2and similarly that the total number of points you get from future splits of stack 2 is
s2(s21)
2, regardless of what strategy you employ in splitting them. Thus, the total number of points
we score is
s1s2+s1(s11)
2+s2(s21)
2=s1(s11) + 2s1s2+s2(s21)
2
=s1(s11) + s1s2+s2(s21) + s1s2
2
=s1(s1+s21) + s2(s1+s21)
2
=(s1+s2)(s1+s21)
2
Since s1+s2=n+1, this works out to (n+1)(n+11)
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 infinite 2D grid. He starts at some location (i,j)N2in the first quadrant,
and is constrained to stay in the first 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,j1).
(ii) Walk one step left, to (i1,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 finite 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 finite amount of time since i+jis a finite number. Thus, if we can prove this stronger
statement, we’ll also have proved that Pacman reaches (0,0)in finite 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