Discrete Computational Structures Homework Assignment #8

CS 230 : Discrete Computational Structures

Homework Assignment #8

Suggested Reading: Rosen Sections 5.3; Lehman et al. Chapters 5, 6.1 - 6.2, 7
For the problems below, explain your answers and show your reasoning.
1. [8 Pts] Prove that f0 − f1 + f2 − · · · − f2n−1 + f2n = f2n−1 − 1 where fi are the Fibonacci
numbers.
(a) Base case: k = 1, f0 − f1 + f2 = f1 − 1 aka 0 − 1 + 1 = 1 − 1 = 0
(b) Induction Hypothesis: f0 − f1 + f2 − · · · − f2k−1 + f2k = f2k−1 − 1
(c) Prove: f0 − f1 + f2 − · · · − f2k−1 + f2k − f2(k+1)−1 + f2(k+1) = f2(k+1)−1 − 1
(d) (f2k−1 − 1) − f2(k+1)−1 + f2(k+1) = f2(k+1)−1 − 1 IH
(e) f2k−1 − f2k+1 + f2k+2 = f2k+1
(f) f2k−1 − f2k+1 + (f2k+1 + f2k) = f2k+1 f2k+2 = f2k+1 + f2k
(g) (f2k−1 + f2k) = f2k+1
(h) f2k+1 = f2k+1 QED
2. [12 Pts] Let S defined recursively by (1) 4 ∈ S and (2) if s ∈ S and t ∈ S, then st ∈ S. Let
A = {4
i
| i ∈ Z+}. Prove that
(a) [6 Pts] A ⊆ S by mathematical induction.
i. Base case: k = 1, 41 = 4 ∈ S
ii. Induction Hypothesis: s, t ∈ S, 4k = st ∈ S
iii. Prove: x, y ∈ S, 4k+1 = xy ∈ S
iv. 4 ∗ 4
k = xy
v. 4 ∗ st = xy IH
vi. 4 ∈ S and st ∈ S, so xy, 4
k+1 ∈ S QED
(b) [6 Pts] S ⊆ A by structural induction.
i. Base case: 4 = 41
, so 4 ∈ S and 4 ∈ A
ii. Induction Hypothesis: x, y ∈ S, assume x, y ∈ A. By (2), xy ∈ S
iii. Prove: xy ∈ A
iv. x, y ∈ A, so x = 4a
, a ∈ Z
+ and y = 4b
, b ∈ Z
+ IH
v. xy = 4a+b
, a + b ∈ Z
+. Therefore, xy ∈ A Def. of A; QED
3. [5 Pts] Define the set S = {2
k3
m5
p
| k, m, p ∈ Z} inductively. You do not need to prove that
your construction is correct.
Basis: k, m, p = 0, 1 ∈ S
Inductive Step: if a ∈ S and b ∈ {2, 3, 5}, then ab ∈ S
4. [10 Pts] Consider the following state machine with five states, labeled 0, 1, 2, 3 and 4. The
start state is 0. The transitions are 0 → 1, 1 → 2, 2 → 3, 3 → 4, and 4 → 0.
Prove that if we take n steps in the state machine we will end up in state 0 if and only if
n is divisible by 5. Argue that to prove the statement above by induction, we first have to
strengthen the induction hypothesis. State the strengthened hypothesis and prove it.
(a) Predicate: P(n): After n steps, the state machine is in state 0 iff n is divisible by 5.
(b) Basis: 5 | 0, so P(0) is true
(c) Inductive Step: Assume P(k)
(d) Prove: P(k + 1)
(e) Suppose 5 | k. By IH, statemachine is in 0 after k steps. However, 5 6 | k + 1 because
the state machine is in state 1 after k + 1 steps. State machine is in state 0 after k + 1
steps iff 5 | k + 1. Both are false, therefore P(k + 1)
(f) Should 5 6 | k, By IH, state machine is in state 1, 2, 3, or 4. We cannot know if going
1 step after k steps will result in state 0. We need a stronger hypothesis to account for
the other states.
(g) Stronger Induction Hypothesis: P(n): After n steps, the state machine is in state p,
where p = n % 5.
(h) Prove ∀n, P(n)
i. Basis: n = 0, state machine is in state 0 and 0 = 0%5
ii. Induction Steps:
A. Case 1: k % 5 = 0, By IH, in state 0 after k steps.
B. Case 2: k % 5 = 1, By IH, in state 1 after k steps.
C. Case 3: k % 5 = 2, By IH, in state 2 after k steps.
D. Case 4: k % 5 = 3, By IH, in state 3 after k steps.
E. Case 5: k % 5 = 4, By IH, in state 4 after k steps.
iii. Proof by Case:
A. Case 1: k + 1 % 5 = 1, By IH, in state 1 after k + 1 steps.
B. Case 2: k + 1 % 5 = 2, By IH, in state 2 after k + 1 steps.
C. Case 3: k + 1 % 5 = 3, By IH, in state 3 after k + 1 steps.
D. Case 4: k + 1 % 5 = 4, By IH, in state 4 after k + 1 steps.
E. Case 5: k + 1 % 5 = 0, By IH, in state 5 after k + 1 steps.
5. [10 Pts] A robot wanders around a 2-dimensional grid. He starts out at (0,0) and can take
the following steps: (-1,+3), (+2,-2) and (+4,0). Define a state machine for this problem.
Then, define a Preserved Invariant and prove that the robot will never get to (2,0).
States: {(a, b) | a, b ∈ Z}, Transitions:
{(a, b) → (a − 1, b + 3),(a, b) → (a + 2, b − 2),(a, b) → (a + 4, b)}
(a) Preserved Invariant Theorem: For every reachable state s = (a, b), (a − b) % 4 = 0
(b) Basis: (0, 0) is reachable in 0 steps.
(c) Induction Hypothesis: Assume (r1 − r2) % 4 = 0 for any state r = (r1, r2) that is
reachable in k steps.
(d) Prove: (s1 − s2) % 4 = 0 for any state s = (s1, s2) that is reachable in k + 1 steps.
(e) r1 − r2 = 4n, n ∈ Z Definition of % 4 = 0
(f) 3 CASES:
i. CASE 1: reach s in k + 1 steps
ii. (s1, s2) = (r1 − 1, r2 + 3)
iii. r1 − 1 − (r2 + 3) = 4n − 4 by IH
iv. 4(n − 1), so (s1 − s2) % 4 = 0
i. CASE 2: reach s in k + 1 steps
ii. (s1, s2) = (r1 + 2, r2 − 2)
iii. r1 + 2 − (r2 − 2) = 4n + 4 by IH
iv. 4(n + 1), , so (s1 − s2) % 4 = 0
i. CASE 3: reach s in k + 1 steps
ii. (s1, s2) = (r1 + 4, r2)
iii. r1 + 4 − r2 = 4n + 4 by IH
iv. 4(n + 1), , so (s1 − s2) % 4 = 0
QED
(g) Therefore, (2, 0) is not reachable because 2 - 0 % 4 = 2, not 0.
6. [15 Pts] Let L = {(a, b) | a, b ∈ Z,(a − b) mod 4 = 0}. We want to program a robot that can
get to each point (x, y) ∈ L starting at (0, 0).
(a) [5 Pts] Give an inductive definition of L. This will describe the steps you want the
robot to take to get to points in L starting at (0, 0). Let L
0 be the set obtained by your
inductive definition.
L
0
is the set of all points, starting at (0, 0), that is reachable taking the following steps:
(-1,+3), (+2,-2), and (+4,0)
(b) Extra Credit [5 Pts] Prove inductively that L
0 ⊆ L, i.e., every point that the robot
can get to is in L.
i. Base case: (0, 0) is a reachable in 0 steps defined by L
0 and in L because (0−0) % 4 =
0
ii. Inductive Hypothesis: Suppose (x, y) ∈ L
0
, therefore reachable by the defined steps.
iii. Prove: (x, y) ∈ L.
iv. By the Preserved Invariant Theorem proved in question 5, if (x, y) ∈ L
0
, (x−y) % 4 =
0
v. By definition of L, (x, y) ∈ L QED
(c) Extra Credit [5 Pts] Prove that L ⊆ L
0
, i.e., the robot can get to every point in L.
To prove this, you need to give the path the robot would take to get to every point in L
from (0, 0), following the steps defined by your inductive rules.
See Image:
For more practice, work on the problems from Rosen Sections 5.3; Lehman et al. Chapters 5, 6.1 -
6.2, 7