Recitation 5 Base case: P(O)is true by definition; the perimeter of the infected region is at most I after 0 time steps, because I is defined to be the perimeter of the initially-infected region Inductive step: We now show that P(h)implies P(k+ 1)for all k >0. So, fix any k>0 and assume that P(k)is true; that is, after k steps, the perimeter of the infected region is at most I After step k+l the primeter can only change because some squares are newly infected. By the rules above, each newly-infected square is adjacent to at least two previously-infected squares. Thus, for each newly-infected square, at least two edges are removed from the perimenter of the infected region, and at most two edges are added to the perimeter Therefore, the perimeter of the infected region can not increase and is at most I after k+1 steps as well. Hence, P(k+ 1)is true By induction, we conclude that P(k) is true for all nk>0 Now, if an n x n grid is completely infected then the perimeter of the infected region is 4n. Thus, the whole grid can become infected only if the perimeter is initially at least 4n Since each square has perimeter 4, at least n squares must be infected initiallyRecitation 5 6 Base case: P(0) is true by definition; the perimeter of the infected region is at most I after 0 time steps, because I is defined to be the perimeter of the initially­infected region. Inductive step: We now show that P(k) implies P(k + 1) for all k ≥ 0. So, fix any k ≥ 0 and assume that P(k) is true; that is, after k steps, the perimeter of the infected region is at most I. After step k+1 the primeter can only change because some squares are newly infected. By the rules above, each newly­infected square is adjacent to at least two previously­infected squares. Thus, for each newly­infected square, at least two edges are removed from the perimenter of the infected region, and at most two edges are added to the perimeter. Therefore, the perimeter of the infected region can not increase and is at most I after k + 1 steps as well. Hence, P(k + 1) is true. By induction, we conclude that P(k) is true for all nk ≥ 0. Now, if an n × n grid is completely infected, then the perimeter of the infected region is 4n. Thus, the whole grid can become infected only if the perimeter is initially at least 4n. Since each square has perimeter 4, at least n squares must be infected initially