# Thread: Finishing this mathematical induction problem

1. ## Finishing this mathematical induction problem

Hello everyone! I started on this mathematical induction problem and I am not sure how to finish it past a certain point. Here it is:

Question: Prove that if S is any finite set with |S| = n, then |S x S x S x S x S| ≤ |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.
Because the Cartesian product grows at the rate of 2n, we must show that n5≤ 2n for n ≥ N, and find what N is.
Base Case: n = 23.
235 ≤ 223= 6436343 ≤ 8388608. Base case proven. (This is not true for any n less than 23 since 225 = 5153632 and 222 = 4194304, and 5153632 is not less than 4194304.)
Inductive Hypothesis: Assume for some k ≥ 23 that k5 ≤ 2k.
Inductive Step: (k+1)5≤ 2k+1
(k+1)5= k5 + 5k4 + 10k3 + 10k2 + 5k + 1
...

I am not sure where to go from here, to be honest. Would anyone care to help? It would be much appreciated!

2. ## Re: Finishing this mathematical induction problem

You need to use your induction hypothesis, that $k^5 \leq 2^k$.

Hence:

$(k+1)^5 \leq 2^k + 5k^4 + 10k^3 + 10k^2 + 5k + 1$

Now IF $5k^4 + 10k^3 + 10k^2 + 5k + 1 \leq 2^{k+1} - 2^k = 2^k$, you're done (do you see why?). You can use the fact that $k > 22$ in said proof.

For example, you might decide:

If $k > 22$, then $k > 10$, so $5k^4 = 5k(k^3) > k(k^3) > 10k^3$. Clearly we also have: $5k^4 > 10k^3 > 10k^2 > 5k > 1$, so that:

$5k^4 + 10k^3 + 10k^2 + 5k + 1 < 25k^4$.

Could we establish by induction that if $k > 22$:

$25k^4 \leq 2^k$?

Base case; $k = 23$:

$25(23^4) = 6,996,025 < 8,388,608 = 2^{23}$.

Assuming $25k^4 < 2^k$:

$25(k+1)^4 = 25(k^4 + 4k^3 + 6k^2 + 4k + 1) \leq 2^k + 100k^3 + 150k^2 + 100k + 25$

Now, IF (and we don't know yet), for $k > 22$ we have $100k^3 + 150k^2 + 100k + 25 < 2^k$, we finish "this proof", and thus finish the proof above.

Again, it is easy to see that if $k > 22$, that $100k^3 > 150k^2 > 100k > 25$, so if we could establish:

when $k > 22$, that $400k^3 < 2^k$, we're home-free.

Base case:

$400(23^3) = 4,866,800 < 8,388,608 = 2^{23}$

You would have to continue this procedure a couple more times.

***********************************

A shorter method would be to find a bound for $(k+1)^5$ "all at once". In other words we might hope that:

$k^5 > 5k^4 + 10k^3 + 10k^2 + 5k + 1$ for any $k > 22$.

We already know that the RHS above is $< 25k^4$, but that's "too large a bound", since 25 > 23. Let's see if we can find "a tighter one". We obviously have:

$5k^4 + 10k^3 + 10k^2 + 5k + 1 < 5k^4 + 10k^3 + 10k^2 + 5k + k = (5k^3 + 10k^2 + 10k + 6)k$, so since $k > 0$, we want:

$k^4 > 5k^3 + 10k^2 + 10k + 6$.

Again, we can replace 6 with $k$, so we have $5k^3 + 10k^2 + 10k + 6 < 5k^3 + 10k^2 + 10k + k = (5k^2 + 10k + 11)k$, so we want:

$k^3 > 5k^2 + 10k + 11$. 11 is still smaller than $k$, so $5k^2 + 10k + 11 < 5k^2 + 10k + k = (5k + 11)k$, and we desire:

$k^2 > 5k + 11$. Now, it is clear that $11 < k$, so $5k + 11 > 6k$, and we want:

$k > 6$. 23 is bigger than 6. Now you finish.

There may be other easier ways than the two I have indicated here.

3. ## Re: Finishing this mathematical induction problem

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?

4. ## Re: Finishing this mathematical induction problem

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?
If $16 \leq k$ (and so also greater than 1), then:

$k^4 + 4k^3 + 6k^2 + 4k + 1 \leq k^4 + 4k^3 + 6k^2(k) + 4k(k) + k \leq k^4 + 4k^3 + 6k^2(k) + 4k(k)(k) + k(k) \leq k^4 + 4k^3 + 6k^2(k) + 4k(k)(k) + k(k)(k)$

$= k^4 + 15k^3 \leq 2k^4 \leq 2(2^k) = 2^{k+1}$.

Yes, it's the same principle. When working with inequalities, we do not need to get the "less than" side into the shape we need, we just have to find something "in the middle" that we can prove is less than the desired bound.