A courtyard meeting these constraints exsists, at least for n= 2 B For larger values of n, is there a way to tile a 2n x 2n courtyard with L-shaped tiles and a statue in the center? Let's try to prove that this is so Theorem 4. For all n >0 there exists a tiling of a 2n x 2n courtyard with Bill in a central square Proof.( doomed attempt) The proof is by induction. Let P(n)be the proposition that there exists a tiling of a 2n x 2n courtyard with bill in the center. Base case: P(O)is true because Bill fills the whole courtyard Inductive step: Assume that there is a tiling of a 2n x 2n courtyard with Bill in the center for some n>0. We must prove that there is a way to tile a 2n+ x 2n+ courtyard with Bill in the center Now were in trouble! The ability to tile a smaller courtyard with Bill in the center does not help tile a larger courtyard with Bill in the center. We can not bridge the gap between P(n)and P(n+ 1). The usual recipe for finding an inductive proof will not work When this happens, your first fallback should be to look for a stronger induction hy pothesis; that is, one which implies your previous hypothesis. For example, we could make P(n)the proposition that for every location of Bill in a 2n x 2n courtyard, there exists a tiling of the remainder This advice may sound bizzare: "If you can't prove something, try to prove something more grand! " But for induction arguments, this makes sense. In the inductive step, where you have to prove P(n)=P(n+1), you're in better shape because you can assume P(n which is now a more general, more useful statement. Let's see how this plays out in the case of courtyard tiling Proof(successful attempt) The proof is by induction. Let P(n) be the proposition that for every location of Bill in a 2n x 2n courtyard, there exists a tiling of the remainder Base case: P(O)is true because Bill fills the whole courtyard Inductive step: Asume that P(n)is true for some n 20; that is, for every location of Bill in a 2n x 2n courtyard, there exists a tiling of the remainder. divide the 2n+l x 2n+ courtyard into four quadrants, each 2n x 2. One quadrant contains Bill (B in the diagram below) Place a temporary Bill (X in the diagram) in each of the three central squares lying outside his quadrant: q8 Induction I A courtyard meeting these constraints exsists, at least for n = 2: B For larger values of n, is there a way to tile a 2n × 2n courtyard with L­shaped tiles and a statue in the center? Let’s try to prove that this is so. Theorem 4. For all n ≥ 0 there exists a tiling of a 2n ×2n courtyard with Bill in a central square. Proof. (doomed attempt) The proof is by induction. Let P(n) be the proposition that there exists a tiling of a 2n × 2n courtyard with Bill in the center. Base case: P(0) is true because Bill fills the whole courtyard. Inductive step: Assume that there is a tiling of a 2n × 2n courtyard with Bill in the center for some n ≥ 0. We must prove that there is a way to tile a 2n+1 × 2n+1 courtyard with Bill in the center... Now we’re in trouble! The ability to tile a smaller courtyard with Bill in the center does not help tile a larger courtyard with Bill in the center. We can not bridge the gap between P(n) and P(n + 1). The usual recipe for finding an inductive proof will not work! When this happens, your first fallback should be to look for a stronger induction hy￾pothesis; that is, one which implies your previous hypothesis. For example, we could make P(n) the proposition that for every location of Bill in a 2n ×2n courtyard, there exists a tiling of the remainder. This advice may sound bizzare: “If you can’t prove something, try to prove something more grand!” But for induction arguments, this makes sense. In the inductive step, where you have to prove P(n) ⇒ P(n + 1), you’re in better shape because you can assume P(n), which is now a more general, more useful statement. Let’s see how this plays out in the case of courtyard tiling. Proof. (successful attempt) The proof is by induction. Let P(n) be the proposition that for every location of Bill in a 2n × 2n courtyard, there exists a tiling of the remainder. Base case: P(0) is true because Bill fills the whole courtyard. Inductive step: Asume that P(n) is true for some n ≥ 0; that is, for every location of Bill in a 2n ×2n courtyard, there exists a tiling of the remainder. Divide the 2n+1 ×2n+1 courtyard into four quadrants, each 2n × 2n . One quadrant contains Bill (B in the diagram below). Place a temporary Bill (X in the diagram) in each of the three central squares lying outside this quadrant: