# 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 $A \subseteq B \implies A \cap \bar B = \emptyset$ and $A \cap \bar B = \emptyset \implies A \subseteq B$

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

for the second, use the contrapositive. that is, show that $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 $x$ be a positive, odd integer. then $x = 2n - 1$ for some integer $n \ge 1$

now, $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 $n$.

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

can you continue?

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

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

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

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

then what?

for problem (3):

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

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

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

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

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

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

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

$4n(n + 1)$

now show that we can write this as $8m$ for some integer $m$, given that $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 $A \cap \bar B \ne \emptyset$ and show that implies $A \not \subseteq B$.

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

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

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