Aim: What is mathematical Induction?

Do Now
1) How can you 'cover' a 4 by 4 grid with a corner cut out with 5 L-shaped pieces?

2) How can you 'cover' a 4 by 4 grid with opposite corners cute out with 7 dominoes.
ITS IMPOSSIBLE!

How would you solve number 1 using an Inductive Proof?
Goal: Prove any 2^n by 2^n grid with a square missing can be tiled with L shaped pieces
Step 1
Base Case: when n = 1, you have a 2 x 2 grid, which, with one corner missing, can easy be tiled with one L shaped piece.
Step 2
Prove that it works for any value n such that n > 1

Solving other Inductive proofs....

Prove using Induction that 1 + 2 + 3 + ...... + n = n(n+1) / 2
Step 1
Base Case: when n = 1, the sum is equal to one, which is equal to 1(1+1)/2. The base case is true.

Step 2
Assume that this is true for n = k, and prove that if it is true for n = k it will also be true for n = k + 1.

1 + 2 + 3 + ...... + k + (k + 1) = (k+1)((k + 1) + 1) / 2
Since we are assuming that 1 + 2 + 3 + ...... + k = k(k+1) / 2, we can replace those values, so that we get

(k(k + 1) / 2) + (k + 1) = (k + 1)(k + 2) / 2.

By proving both sides of the equation equal to eachother (either by multiplying both sides out or just manipulating one side algebraically), we can prove that if the statement is true for n = k, it is true for n = k + 1. Since we know it is true for n = 1, it must be true for n = 2, n = 3, n = 4, etc.