Results 1 to 1 of 1

Math Help - induction inequality

  1. #1
    Member
    Joined
    Mar 2009
    Posts
    90

    induction inequality

    <br />
(\forall n)(n \geq n_0) \wedge n^2 \leq 2^{n - k}, k \in \mathbb{N}<br />

    Identify the smallest n_0 in relation to k so that the proposition can be proved using mathematical induction (over n).

    Fiddling around with the numbers n_0 \geq 4 is a least condition for the inequality, but how can I find out the relationship between k and n for all n?

    Just as a beginning:
    hypothesis:
     <br />
n^2 \leq 2^{n - k} <br />
    re-write the hypothesis:
    <br />
n \leq 2^{\frac{1}{2}(n - k)} <br />
    for (n - 1):
    <br />
(n - 1)^2 \leq 2^{n - 1 - k} <br />
    <br />
n^2 - 2n + 1 \leq 2^{n - 1 - k} <br />

    but from this we see that:
    <br />
n^2 < n^2 - 2n + 1 \wedge 2^{n - k - 1} < 2^{n - k}<br />

    Is it possible to conclude that:
    <br />
2^{n - k} - 2^{n - k - 1} \leq 2n - 1<br />
    <br />
= 2^{n - k - 1} \leq 2n -1<br />
    which is just nonsense. I think? Can someone please help?!
    Last edited by bmp05; February 3rd 2010 at 10:13 AM. Reason: added a few more lines
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Induction Inequality
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 17th 2011, 02:47 PM
  2. [SOLVED] Induction Inequality
    Posted in the Algebra Forum
    Replies: 4
    Last Post: October 30th 2010, 05:44 AM
  3. induction inequality
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 26th 2008, 09:46 AM
  4. Induction Inequality
    Posted in the Algebra Forum
    Replies: 3
    Last Post: September 10th 2008, 09:21 PM
  5. Induction with inequality
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 30th 2008, 09:42 PM

Search Tags


/mathhelpforum @mathhelpforum