Lab: Introduction to Proofs

Today’s lab will give you a chance to practice with the various types of proofs that we will work with throughout this semester. Some of these proofs will be review, some will be new, as with Lab 0, the goal of this lab is to determine where everyone is at.

For each proof:

Have you worked with proofs like this before?
Attempt to prove the theorem
Write up both your proof and the proof at the end of class

If you finish early, I have many more proofs that I can have you work through for practice.

Direct Proofs

Theorem: Given 2 rational numbers A and B, their sum $A+B$ is rational.
(bonus). Theorem: Given 2 rational numbers A and B, their product $A\times B$ is rational.

Proof by Contradiction

Theorem: Given a rational number A and an irrational number B, their product $A\times B$ is irrational.
(bonus). Theorem: Given a rational number A and an irrational number B, their sum $A+B$ is irrational.

Proof by Contrapositive

Theorem: Let $x^2(y^2-2y)$ be odd. Then x and y are both odd integers.
(bonus) Theorem: Let $x,y\in\mathbb{N}$$. If $xy$ is not divisible by 7, then neither x nor y is divisible by 7.

Proof by Induction

Find a closed form solution for the termial ($\sum_{i=0}^n i$) in terms of n. Prove that your solution is correct via induction.
(bonus) Find a closed form solution for $\sum_{i=0}^n 2i+1$ in terms of n. Prove that your solution is correct via induction.

Proof by Exhaustion

Theorem: Let $n\in\mathbb{N}$$. If the remainder of $n\div3=2$, n is not square.

Hint: You might want to think about the contrapositive

(bonus). If x is odd, then $x\equiv1mod4$ or $x\equiv3mod4$

Proof by Construction

Theorem: Given 5 L shaped tiles ($2\times2$ square missing 1 piece). Prove that you can fit all 5 pieces on a $4\times4$ grid.
(bonus) Prove that given the same 5 L shaped tiles, you can fit them on a $4\times4$ grid with one cell removed, regardless of where the hole is.

Hint: How many solutions do you need to construct (symmetry)?

Proof by Combinatorics (counting)

How many ways are there to arrange the letters A, B, and C if we must use all 3 letters once
(bonus). How many ways are there to create a password of length 5 if we can only use the letters A, B, and C, but repeats are allowed?

(dis)Proof by Counterexample

Theorem: Let $n\in\mathbb{N}$ if n can be written as a difference of squares ($x^2-y^^2$ for $x,y\in\mathbb{N}$, then n is divisible by 4.
(bonus) Theorem: All two dimensional maps can be colored with 3 distinct colors such that no two territories with the same color are touching.

Note, some problems were adapted and taken from Harvard. Please don’t open this website until after you have submitted your work.