Lec 2 | MIT 6.042J Mathematics for Computer Science, Fall 2010

TL;DR

Using induction, we can prove that any 2^n by 2^n courtyard can be tiled with L-shaped tiles, leaving one square missing.

Transcript

The following content is provided under a Creative Commons license. Your support will help MIT OpenCourseWare continue to offer high quality educational resources for free. To make a donation, or view additional materials from hundreds of MIT courses, visit MIT OpenCourseWare at ocw.mit.edu. PROFESSOR: Last week we talked about the key components o... Read More

Key Insights

• 👍 The base case is crucial in proving the overall theorem.
• 👻 Induction allows for the proof of a larger problem by proving a smaller, related problem.

Questions & Answers

Q: What is the goal of the proof?

The goal is to prove that any 2^n by 2^n courtyard can be tiled with L-shaped tiles, leaving one square missing.

Q: What is the base case?

The base case is when n=0, where there are no tiles to place.

Q: How does the proof progress after the base case?

The proof progresses by assuming that the theorem is true for n and proving it for n+1.

Summary & Key Takeaways

• The goal is to tile a 2^n by 2^n courtyard with L-shaped tiles, omitting one square.

• The base case of n=0 is trivially true since there are no tiles to place.

• Using induction, we assume that the theorem is true for n and prove it for n+1.