Recitation 8: Proof by Induction

Part 1: Practice with Induction

Prove the following statements using mathematical induction.

Prove that for every positive integer .
- What do you need to prove in the basis step?
- What do you need to prove in the inductive step?
- Complete the inductive step.
Prove that for every positive integer n.
- What do you need to prove in the basis step?
- What do you need to prove in the inductive step?
- Complete the inductive step.
Prove that $2^n>n^2$ for every positive n that is greater than 4.
Prove that $n^5-n$ is divisible by 5 for every positive integer n.
Prove that $1*2+2*3+3*4+...+n*(n+1)=\frac{(n)(n+1)(n+2)}{3}$ for every positive integer n.
Find a formula for $\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+...+\frac{1}{2^n}$ and prove it.
Consider the sequence: $1+2+4+8+16+...$ What is the sum of the first n elements? Prove this.

Proofs for the first five theorems (pdf format).

Proofs for the first five theorems (html format, harder to read).

Part 2: Extra Practice and Strong Induction

Prove that $|\mathcal{P}(A)| = 2^{|A|}$ for any set $A$ .

For which positive integers are the following propositional functions true?

$P(1)$ is true. For all positive integers $n$ , $P(n) \to P(n+1)$ .
$P(1)$ is true. For all positive integers $n$ , $P(n) \to P(n+2)$ .
$P(1)$ and $P(2)$ are true. For all positive integers $n$ , $P(n) \to P(n+2)$ .
$P(0)$ and $P(1)$ are true. For all positive integers $n$ , $P(n)$ and $P(n+1)$ imply $P(n+2)$ .
$P(0)$ is true. For all positive integers $n$ , $P(0) \land P(1) \land ... \land P(n-2) \land P(n - 1) \to P(n)$ .

What is wrong with the following proof?

Theorem: It is possible to form postage of three cents or more using just three cent and four cent stamps.

Proof:

Basis step: We can form postage of three cents with a single three cent stamp and postage of four cents using a single four cent stamp.

Inductive step: Assume that we can form postage of $j$ cents for all nonnegative integers $j$ with $j \leq k$ using just three cent and four cent stamps. We can then form postage of $k + 1$ cents by replacing one three cent stamp with a four cent stamp or by replacing two four cent stamps by three three cent stamps.

Prove the following using strong induction:

Any amount of change over seven cents can be made out of three cent and four cent coins.
Any positive integer $n$ can be written as a sum of distinct powers of two. For example, $4 = 2^2$ and $19 = 2^0 + 2^1 + 2^4$ .