Results 1 to 4 of 4
Like Tree5Thanks
  • 2 Post By Deveno
  • 1 Post By Lolligirl
  • 2 Post By Deveno

Math Help - Finishing this mathematical induction problem

  1. #1
    Newbie Lolligirl's Avatar
    Joined
    Aug 2014
    From
    2014 A.D.
    Posts
    4
    Thanks
    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!
    Last edited by Lolligirl; August 27th 2014 at 06:32 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    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.
    Thanks from Lolligirl and topsquark
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie Lolligirl's Avatar
    Joined
    Aug 2014
    From
    2014 A.D.
    Posts
    4
    Thanks
    1

    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?
    Last edited by Lolligirl; August 28th 2014 at 06:46 AM.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: Finishing this mathematical induction problem

    Quote Originally Posted by Lolligirl View Post
    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.
    Thanks from Lolligirl and topsquark
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Help with mathematical induction problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 30th 2012, 02:12 PM
  2. Mathematical Induction Problem.
    Posted in the Differential Geometry Forum
    Replies: 14
    Last Post: June 9th 2010, 12:22 PM
  3. Mathematical Induction Problem
    Posted in the Calculus Forum
    Replies: 2
    Last Post: September 15th 2009, 06:38 PM
  4. mathematical induction problem
    Posted in the Algebra Forum
    Replies: 4
    Last Post: February 24th 2009, 07:06 PM
  5. mathematical induction problem no.2
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: January 12th 2008, 08:45 PM

Search Tags


/mathhelpforum @mathhelpforum