A set identity and a divisibility proof by induction¶

Math I: Calculus · Week 1 test, open question · 7 points · Lecture 1

Problem¶

Let $A$ and $B$ be sets with $A\subseteq B\text{.}$ Prove that

$B=A\cup(B\setminus A)\quad\text{and}\quad A\cap(B\setminus A)=\varnothing.$

[3 points]
Prove by mathematical induction that $3^{2n}-1$ is divisible by $8$ for every positive integer $n\text{.}$ [4 points]

What you need¶

Subset: two sets are equal exactly when each is a subset of the other.
Union, intersection and difference set: what it means for an element to belong to each.
Empty set and disjoint sets.
Mathematical induction, the induction axiom of the natural numbers: a base case and an inductive step.

Plan¶

For part 1, prove the equality by double inclusion: take an element of the left side and show it is in the right side, then the reverse. For part 2, the key is to write the $(k+1)$ $1)$ -th expression in terms of the $k$ -th one, so that the induction hypothesis can be used.

Step-by-step solution¶

Try each step yourself before you open it.

Part 1, Step 1 · Show that B is contained in the union

Let $x\in B\text{.}$ Split into two cases.

If $x\in A\text{,}$ then $x\in A\cup(B\setminus A)\text{.}$
If $x\notin A\text{,}$ then $x\in B$ and $x\notin A\text{,}$ so $x\in B\setminus A\subseteq A\cup(B\setminus A)\text{.}$

In both cases $x\in A\cup(B\setminus A)\text{.}$

Part 1, Step 2 · Show that the union is contained in B (with Step 1: 2 points)

$A\subseteq B$ is given, and $B\setminus A\subseteq B$ by the definition of the difference set. A union of two subsets of $B$ is again a subset of $B\text{.}$ Together with Step 1, this proves $B=A\cup(B\setminus A)\text{.}$

This is the only place where the assumption $A\subseteq B$ is used. Without it the identity can fail.

Part 1, Step 3 · Show the intersection is empty (1 point)

Suppose some $x$ lies in $A\cap(B\setminus A)\text{.}$ Then $x\in A\text{,}$ and also $x\in B\setminus A\text{,}$ which means $x\notin A\text{.}$ That is a contradiction, so no such $x$ exists and $A\cap(B\setminus A)=\varnothing\text{.}$

Part 2, Step 1 · Base case (1 point)

For $n=1\text{,}$ $3^{2}-1=8\text{,}$ which is divisible by $8\text{.}$

Part 2, Step 2 · State the induction hypothesis precisely (1 point)

Assume that for some positive integer $k\text{,}$ $3^{2k}-1$ is divisible by $8\text{.}$ Write this as an equation:

3^{2k}-1=8m\quad\text{for some integer }m.

Turning "divisible by 8" into an equation is what makes the next step a calculation instead of a sentence.

Part 2, Step 3 · Inductive step (2 points)

Rewrite the next case so that the hypothesis appears:

\begin{aligned} 3^{2(k+1)}-1&=9\cdot3^{2k}-1\\ &=9(3^{2k}-1)+8\\ &=9\cdot8m+8\\ &=8(9m+1). \end{aligned}

Since $9m+1$ is an integer, $3^{2(k+1)}-1$ is divisible by $8\text{.}$ By induction the statement holds for every positive integer $n\text{.}$

Where marks are lost¶

Proving only one inclusion in part 1. Equality of sets needs both directions.
Checking a few values of $n$ instead of proving the step. Examples like $n=2,3$ are not a proof.
Assuming what you want to prove. The hypothesis is about a fixed $k\text{;}$ the step must derive the statement for $k+1\text{.}$
Leaving "divisible by 8" as words. Without $3^{2k}-1=8m$ it is hard to show the factor $8$ in the next case.

Try next¶

Limit of a sequence from the definition: the next week's test, on sequences and bounds.

Symbols: element of, intersection, subset, union