Math Is Fun Forum

Lolligirl

Member

From: 2014 A.D.

Registered: 2014-08-27

Posts: 3

Website

Finish 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 2^n, we must show that n^5≤ 2^n for n ≥ N, and find what N is.
Base Case: n = 23.
23^5 ≤ 2^23 = 6436343 ≤ 8388608. Base case proven. (This is not true for any n less than 23 since 22^5 = 5153632 and 2^22 = 4194304, and 5153632 is not less than 4194304.)

Inductive Hypothesis: Assume for some k ≥ 23 that k^5 ≤ 2^k.

Inductive Step: (k+1)^5 ≤ 2^(k+1)
(k+1)^5= k^5 + 5k^4 + 10k^3 + 10k^2 + 5k + 1
...

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

Last edited by Lolligirl (2014-08-27 13:44:55)

Olinguito

Member

Registered: 2014-08-12

Posts: 649

Re: Finish this mathematical induction problem

Where did you your teacher get the problem from? This is a really tough one for beginners!

So we suspect

.

It seems that we must first show that

for

. If we can do that then the induction hypothesis would imply

[list=*]
[*]

[/*]
[/list]

So the problem is to prove

for

. If it also involves induction, it’s going to be a messy job. I don’t think this is really a question to set as an exercise for students just starting to learn induction.

Last edited by Olinguito (2014-08-27 22:17:10)

---

Bassaricyon neblina

Lolligirl

Member

From: 2014 A.D.

Registered: 2014-08-27

Posts: 3

Website

Re: Finish this mathematical induction problem

Is it that complex? Wow! There was a similar problem to this done, except with taking the Cartesian product three times instead of four, and it seemed not crazt complex:

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"!