# Thread: Proofs and Mathematical Induction

1. ## Proofs and Mathematical Induction

I 've got these 3 problems.
Any help would be appreciated!
Thanks!

2. Originally Posted by BACONATOR
I 've got these 3 problems.
Any help would be appreciated!
Thanks!
for problem (1)

we need to go both ways. that is, show that $\displaystyle A \subseteq B \implies A \cap \bar B = \emptyset$ and $\displaystyle A \cap \bar B = \emptyset \implies A \subseteq B$

for the first, let $\displaystyle x \in A$. show that this means $\displaystyle A \cap \bar B = \emptyset$

for the second, use the contrapositive. that is, show that $\displaystyle A \not \subseteq B \implies A \cap \bar B \ne \emptyset$

can you continue?

3. Originally Posted by BACONATOR
I 've got these 3 problems.
Any help would be appreciated!
Thanks!
for problem (3)

Let $\displaystyle x$ be a positive, odd integer. then $\displaystyle x = 2n - 1$ for some integer $\displaystyle n \ge 1$

now, $\displaystyle x^2 - 1 = (x + 1)(x - 1) = (2n - 1 + 1)(2n - 1- 1) = 2n(2n - 2) = 4n(n - 1)$. thus, you need to prove the following by induction on $\displaystyle n$.

Let $\displaystyle P(n)$: "$\displaystyle 4n(n - 1)$ is divisible by $\displaystyle 8$" for all $\displaystyle n \in \mathbb{N}, n \ge 1$

can you continue?

4. for (1): note that $\displaystyle x \in A \cap \bar B$ means $\displaystyle x \in A$ and $\displaystyle x \in \bar B$. clearly we cannot have $\displaystyle x \in \bar B$ if $\displaystyle x \in B$. so all you have to do, is show that if $\displaystyle x \in A$ (as i suggested you start with) then $\displaystyle x \in B$... oh, just let me do it.

for the first implication, assume $\displaystyle A \subseteq B$. Then $\displaystyle x \in A \implies x \in B$. Clearly if $\displaystyle x \in B$, then $\displaystyle x \not \in \bar B$. thus, we have that $\displaystyle x \in A$ and $\displaystyle x \not \in \bar B$. It means therefore, that $\displaystyle x$ is not in their intersection. so, $\displaystyle A \cap \bar B = \emptyset$.

for the second implication, you need to show that $\displaystyle A \not \subseteq B \implies A \cap \bar B \ne \emptyset$.

now, if $\displaystyle A \not \subseteq B$, then there exists an $\displaystyle x \in A$ such that $\displaystyle x \not \in B$.

then what?

for problem (3):

Let $\displaystyle P(n)$ be defined as i said.

by induction, we need to prove $\displaystyle P(1)$ is true, then show that if $\displaystyle P(n)$ is true, then $\displaystyle P(n + 1)$ will be true.

Clearly $\displaystyle P(1)$ is true. since when $\displaystyle n = 1$, $\displaystyle 4n(n - 1) = 0$. and, of course, $\displaystyle 0$ is divisible by 8.

Assume $\displaystyle P(n)$ is true for some $\displaystyle n$. we show $\displaystyle P(n + 1)$ is true.

Since $\displaystyle P(n)$ is true, we can write $\displaystyle 4n(n - 1) = 8k$ for some integer $\displaystyle k$.

so, we need to show we can write $\displaystyle P(n + 1)$ in this fashion.

for $\displaystyle P(n + 1)$, we have:

$\displaystyle 4n(n + 1)$

now show that we can write this as $\displaystyle 8m$ for some integer $\displaystyle m$, given that $\displaystyle 4n(n - 1) = 8k$

5. on second thought, i don't like my proof for the first implication in problem (1). there seems to be a problem with it.

instead, do it by the contrapositive. assume $\displaystyle A \cap \bar B \ne \emptyset$ and show that implies $\displaystyle A \not \subseteq B$.

in other words, i want you to prove the equivalent statement that:

$\displaystyle A \not \subseteq B \Longleftrightarrow A \cap \bar B \ne \emptyset$.

you need to be clear on what it means for $\displaystyle A \not \subseteq B$ and $\displaystyle A \cap \bar B \ne \emptyset$