Proof Questions 1. An induction proof has a base case and an induction step. The
ID: 3210033 • Letter: P
Question
Proof Questions
1. An induction proof has a base case and an induction step. The beginning of the induction step is an assumption that the theorem has held true up to some point. That assumption is sometimes called an induction hypothesis. In this proof, what is the author’s exact statement of the assumption?
2. The author uses the induction assumption (hypothesis) twice in the proof. State the exact phrases where the assumption is used.
Figure 6.6.4: Proof of theorem relating graph powers and matrix powers (Theorem 6.6.1) Theorem: Let G be a directed graph with n vertices and let A be the adjacency matrix for G. Then for any k 2 1, Ak is the adjacency matrix of Gk, where Boolean addition and multiplication are used to compute Ak Proof. The proof is by induction on k. For the base case, k = 1 . By definition G1-6, and Al-A is the adjacency matrix for G Now assume that Ak1 is the adjacency matrix for G1, and prove that Ak is the adjacency matrix for G. Since Ak-1 is the adjacency matrix for Gk1 (A is 1 if and only if there is a walk in graph G of length k-1 from vertex i to vertex j. We will show that (A is 1 if and only if there is a walk of length k in G from vertex i to vertex j Suppose that (Abu-1. Since Ak = A Ak-1, by definition of matrix multiplication, Since (A 1, there is at least one x in the range from 1 through n such that Axr(A 1. For that value ofx, Aux-1 and (Ak1 Since Ax 1, there is an edge from vertex i to vertex x in G. Since (A 1, by the inductive hypothesis, there is a walk of length k-1 in G from vertex x to vertex j. The edge from i to x, followed by the length k- 1 walk from x to j, results in a walk of length k in G from vertex i to vertex j. Now suppose that there is a walk of length k in G from vertex i to vertex j. Let x be the second vertex visited on the walk. There is an edge in G from vertex i to vertex x and walk of length k-1 in G from vertex x to vertex j. By induction, Ax-1 and (A -1. Therefore by definition of Boolean matrix multiplication, (Aku :1Explanation / Answer
1. Induction hypothesis is ''A^{k-1} is the adjecency matrix of G^{k-1}''.
The answers for 2 are the following
First time the induction hypothesis is used in the phrase ''Since A^{k-1} is the adjecency matrix of G^{k-1}, (A^{k-1})_in is 1 if and only if''.
Second time induction hypothesis is used in the phrase ''Since (A^{k-1})_ij = 1 by induction hypothesis, there is a walk of length''
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.