Lab: Proofs by Contradiction and Induction

Instructions:

For each section, you must turn in one “fix this proof” and one “on your own” proof. If you have extra time you should do more problems.

Proof By Induction

What is wrong or missing with this proof? Identify the issue(s) and fix the proof.

Induction Issue 1:

Goal: Prove that $\forall n\in\mathbb{N}:n^n\geq n!$

Base case: n=1: $1^1=1=1!$

Inductive Hypothesis: $k^k\geq k!$

Goal: $(k+1)^{k+1}\geq k!$

$(k+1)^{k+1}\geq k^k$ which by the inductive hypothesis means that it is greater than or equal to k!, so we are done.

Induction Issue 2:

Goal: If m is an odd integer $4^m+5^m$ is evenly divisible by 9

Base case: m=1, $4+5=9$ is evenly divisible by 9

Inductive Hypothesis: $4^k+5^k$ is evenly divisible by 9

Goal: $4^{k+1}+5^{k+1}$ is evenly divisible by 9

$4^{k+1}+5^{k+1}=9^{k+1}=9\times 9^k=9\times(4^k+5^k)$ we know that $4^k+5^k$ is evenly divisible by 9, so 9 times that number is still divisible by 9.

Prove the following statements are true

Goal: $n^3-n$ is evenly divisible by 6 $\forall n\in\mathbb{N}$

Goal: $2^{n+2}+3^{2n+1}$ is evenly divisible by 7 $\forall n\in\mathbb{N}$

Goal: $1+2+4+…2^{n-1}=2^n-1$

Goal: You have $3^n$ coins and a balance. One of the coins is heavier than the others. Show that you can find the heavier coin in n uses of the balance.

Goal: Same as above except the non standard coin can be heavier or lighter. Show that this can be done in n+1 uses of the balance.

Goal: $4^n-1\vert3\forall n\in\mathbb{N}$

Goal: Given a $2^n\times 2^n$ chessboard with a single piece missing, show that you can fill the chessboard entirely with L shaped pieces (a 2x2 square with one piece removed).

Goal: Any integer can be written as a product of prime factors

Proof By Contradiction

What is wrong or missing with this proof? Identify the issue(s) and fix the proof.

Contradiction Issue 1:

Goal: There is no smallest Positive Rational Number

For the sake of contradiction, assume that there is a smallest Positive Rational Number k. Then because k is a rational number, it can be written as $\frac{m}{n}$ for some integers m and n. Since m is an integer, m-1 is a smaller integer. Since m-1 is smaller than m, $k_2=\frac{m-1}{n}$ is smaller than $\frac{m}{n}$. We also know that since m-1 and n are integers, $k_2$ is a rational number. Therefore we have $k_2=\frac{m-1}{n}$ < $\frac{m}{n}=k$ which is a contradiction.

Contradiction Issue 2:

Goal: an irrational number raised to an irrational number can be rational.

For the sake of contradiction, assume that an irrational number raised to itself must be rational. $\pi^{\pi}=\pi^2$. This means that $\pi^2$ is a rational number which is a contradiction.

Prove the following statements are true

Goal: Given 25 graduate students and 25 professors sitting around a circular table, prove that there is always a person sitting between two professors (prof-person-prof)

Goal: In a party with finite people, there must be two people who have the same number of friends. Notes:

• People are not friends with themselves
• Friendship is mutual
• Everyone has at least one friend (Is this required?)

Goal: Any integer can be uniquely written as a product of prime factors (order independent)

Goal: $\sqrt{n}$ is either an integer or irrational if $n\in\mathbb{N}$ (i.e. not a non-integer rational number)

Goal: There are infinite primes