Originally Posted by

**Lolligirl** Really? Wow! I was a little able to follow what you did, but I admit I did not understand quite all of it. There was a similar problem to this done, except with taking the Cartesian product three times instead of four:

Question: Prove if S is any finite set with |S| = n, then |SxSxSxS| ≤ |P(S)|, for all n ≥ N, where N is some constant, the minimum value of which you must discover and use as the basis for your proof.

Proof: (This is the same as showing n^4 <= 2^n, for all n ≥ N. We shall show this is true when N=16.)

**Basis**: 16^4 = (2^4)^4 = 2^16 ≤ 2^16. This proves the base case.

**I.H.**: Assume for some K, K ≥ 16, K^4 ≤ 2^K.

**I.S. (K+1)**: (K+1)^4 = K^4 + 4K^3 + 6K^2 + 4K + 1

≤ K^4 + 4K^3 + 6K^3 + 4K^3 + K^3 since K ≥ 1

= K^4 + 15K^3 ≤ K^4 + K^4 since K ≥ 16

≤ 2^K + 2^K by IH

= 2^(K+1)

Thus, (K+1)^4 <= 2^(K+1) and the I.S. is proven.

I have been trying to extend this to adding one more Cartesian product, but wasn't sure exactly how the line

"(K+1)^4 = K^4 + 4K^3 + 6K^2 + 4K + 1"

became

"≤ K^4 + 4K^3 + 6K^3 + 4K^3 + K^3 since K ≥ 1"! Would this be a simpler way of doing it?