# Proof by induction: multiplication of two finite sets.

1. Oct 6, 2012

### whyme1010

1. The problem statement, all variables and given/known data

prove by induction that if A and B are finite sets, A with n elements and B with m elements, then AxB has mn elements

2. Relevant equations
AxB is the Cartesian product. AxB={(a,b) such that a is an element of A and b is an element of B}

3. The attempt at a solution
normally, proof by induction involves one variable. here it includes two. I guess I could say that mn=nm and therefore proving it for n+1 is the same thing as proving it for m+1. Then any increase in m or n after that is just the same thing. But somehow I still feel this isn't really justifiable.

2. Oct 6, 2012

### Zondrina

So induction has three steps. Where you assume the case n = 1, the induction assumption and then the proof for the n+1 case.

Case : n = 1 = m

Assume that A and B have one element in each corresponding set. Say A = {(a0,b0)} and B = {(c0,d0)} and go from here.

Last edited: Oct 6, 2012
3. Oct 6, 2012

### whyme1010

yeah, but how do I prove that if it is true for the n+1 case, it is also true for the m+1 case. and what if m+1 and n+1 are occurring at the same time?

I guess what I'm asking is, if I prove it true for the n+1 case (which is pretty easy), then how do I show that this means I can add one element to A and B as desired and the result mn would still be valid.

4. Oct 6, 2012

### Zondrina

That's the beauty of induction. Imagine if you held the amount of elements in B constant the whole time. Would it change your outcome?

Proof by induction, $(n!)^{2} \le (2n)!$. Mar 1, 2017