So, I'm doing some studying for an exam coming up in a math class I'm taking. One sample problem given to us by the instructor to study was:
Prove by induction for any two sets $A$ and $B$ that $|A\cup B|=|A - B| + |B - A| + |A\cap B|$.
The only issue is, I'm not entirely sure how to start with this, even on the basis step. Where would I start for here?
Well, first off I assume that your sets are not "any" sets but assumed to be finite... Still this question is not that nice as it is easy to prove without induction, so using induction here would be kind of forced. However, you might learn something from it: So what do we need for an induction? First we need something to do induction on. There are multiple candidates here:
We can of course also nest them into each other, e.g. we do an induction over $|B|$. In the induction step, so if $|B|$ is fixed, we do an induction over $|A|$ and in that induction we do an induction over $|A \cap B|$, where here both $|A|$ and $|B|$ are fixed.
Doing it like this you will at least train how to write inductions, even though there is no interesting math underneath it as the claim can be proven by a simple Venn diagram.