Results 1 to 6 of 6
Like Tree2Thanks
  • 1 Post By emakarov
  • 1 Post By emakarov

Math Help - Proof by induction, 2^k-1 +1 = k+1

  1. #1
    Newbie
    Joined
    Oct 2013
    From
    Canada
    Posts
    3

    Proof by induction, 2^k-1 +1 = k+1

    Hey I've come across a question which is a little weird to prove by induction.

    This is the function,
    "Let T be a total function from Z+ to R+ such that T is nondecreasing on Z+, such that T(1) =1 and:

    for any positive real number k, T(2k) = T(2k-1)+1"

    I have to prove that for any Natural number T(2k) = k+1 by induction.

    A few questions I had to do with this function was find T(2), T(4) and T(8) (You'll notice they're all powers of 2)

    Example, to find T(2):

    2 = 21So, k = 1
    T(21) = T(21-1) +1 (Second part of equation from the function definition)

    T(21-1) = T(20) = T(1) (The next number is the power before it, + 1)

    Given; T(1) =1
    T(1) + 1 = 2, therefore T(2) = 2

    You use the same method to find:
    T(4) = 3
    T(8) = 5
    You could keep going:
    T(16) = 9
    T(32) = 17
    ...

    Back to my main question, how do I prove that for any Natural number k T(2k) = k + 1
    This is what I have so far:

    Let P(k) be the statement : T(2k) = k + 1
    Let k = 1 (basis step)
    P(1) = T(2) = k +1
    ... show work etc <--- for this part do I have to state somewhere that T(1) is given in order to get T(2)??
    2 = 2
    Therefore P(1) is true because T(2) = 1 + 1
    Let n be an arbitrary element of N (natural numbers) and assume P(n) (inductive step)

    This part is where i'm stuck, we are given several definitions/properties that we are encouraged to use to solve this problem, these are the relevant ones:

    ∀n∈Z+, ∃k∈Z+, 2k−1≤n≤2k

    ∀n∈Z+,
    n
    ∑k = n(n+1)/2
    k=1

    ∀(a,b)∈R+2, log(ab) = log(a)+log(b)
    ∀a∈R+, ∀k∈N, log(ak) = k log(a)
    log(1) = 0
    log is increasing on R+
    ∀a∈R+, log2(a) = log(a)/log(2)

    Any help on the inductive step would be appreciated.

    I also cannot figure out a few other questions with the same function:
    "Show that for any positive integer n we have T(n) <= log2(2n)+1"
    and
    "Show that T(n) is O(log(n))" (Yes that's big O notation for those computer scientists, which really is asking, show that There exists an integer M that you can multiply f(x) such that f(x) <= M*g(x) where f and g are two functions defined on subsets of R)
    Last edited by bulletmagnet1234; October 12th 2013 at 08:14 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785

    Re: Proof by induction, 2^k-1 +1 = k+1

    Quote Originally Posted by bulletmagnet1234 View Post
    T(1) =1 and:

    for any positive real number k, T(2k) = T(2k-1)+1"

    I have to prove that for any Natural number T(2k) = k+1 by induction.
    Quote Originally Posted by bulletmagnet1234 View Post
    T(8) = 5
    How did you find this?

    Quote Originally Posted by bulletmagnet1234 View Post
    You could keep going:
    T(16) = 9
    T(32) = 17
    ...

    Back to my main question, how do I prove that for any Natural number k T(2k) = k + 1
    This is what I have so far:
    It's strange that you are trying to prove something that you determined is false. If T(32) = T(2⁵) = 17, then T(2k) = k+1 can't be true.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2013
    From
    Canada
    Posts
    3

    Re: Proof by induction, 2^k-1 +1 = k+1

    Quote Originally Posted by emakarov View Post
    How did you find this?
    T(1) = 1 is given in the question. That's why it's in quotation marks with the preceding statement, it's a definition.
    T(8) = 5 because when it's T(8), k = 3 (2^3=8) and this is equal to T(2^(k-1))+1" which is 4+1


    Quote Originally Posted by emakarov View Post
    If T(32) = T(2⁵) = 17, then T(2^k) = k+1 can't be true.
    However it is true for T(1) and T(2)

    T(1) = 1 = 0 + 1, k=0
    T(2) = 2 = 1+1, k=1

    I don't know if that somehow helps?
    The next number is the power before it, + 1

    I know there is a solution otherwise my teacher wouldn't have given it to us.
    Are you suggesting there is no algebraic way to manipulate T(2^k) = k + 1 in this problem to prove T(2^n) = n + 1 or T(2^(n+1)) = (n+1) + 1.
    Perhaps I am approaching this problem incorrectly?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785

    Re: Proof by induction, 2^k-1 +1 = k+1

    Quote Originally Posted by bulletmagnet1234 View Post
    T(4) = 3
    Quote Originally Posted by bulletmagnet1234 View Post
    T(8) = 5 because when it's T(8), k = 3 (2^3=8) and this is equal to T(2^(k-1))+1" which is 4+1
    It seems you are computing T(k) as if it were 2^{k-1}+1. Instead, it's T(2^{k-1})+1. If n is a power of 2, then T(n)=T(n/2)+1. You found that T(4) = 3, so T(8) = T(4) + 1 = 4.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2013
    From
    Canada
    Posts
    3

    Re: Proof by induction, 2^k-1 +1 = k+1

    Quote Originally Posted by emakarov View Post
    You found that T(4) = 3, so T(8) = T(4) + 1 = 4.
    I know what you just wrote is correct and what I wrote was wrong, but I don't fully understand why I am wrong or simply how to interpret the function definition.
    (How I know you are right is my colleagues went a similar way to get the answer but I didn't understand it so I tried to do it on my own, a different way, but I can't contact them right now for help)
    Could someone help me understand the question better? And what the function T really is?

    Also if we go through it this way, does that mean we can prove by induction T(2^k) = k + 1 ?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785

    Re: Proof by induction, 2^k-1 +1 = k+1

    Quote Originally Posted by bulletmagnet1234 View Post
    Could someone help me understand the question better? And what the function T really is?
    In computer science parlance, function T is defined recursively, and I believe that recursion is one of the hardest things to grok. In math, such functions are called recurrence relations. You compute their values one by one. To compute the next value, you need the previous one. In a typical recurrence relation F, F(k + 1) depends not only on k, but also (or exclusively) on F(k). (One could say that ultimately F does depend only on k, but to compute F(k + 1) there may not be a simpler way than to compute F(0), ..., F(k) and then use F(k).)

    As an exercise, you could compute F(k) for small values of k when F is defined as follows:

    (1) F(0) = 0, F(k + 1) = F(k) + 1
    (2) F(0) = 1, F(k + 1) = 2F(k)

    In your problem, if we consider the recurrence relation T(2k) = T(2k-1) + 1 for integer k only, it defines T only for powers of 2, i.e., we can use it to compute T(2), T(4), T(8), T(16) and so on. But the idea is the same: we need to actually use T(8) and not just 4 (since 2⁴ = 16) to compute T(16). The recurrence relation says that we need to add 1 to T(8) to get T(16). Similarly, we add 1 to T(4) to get T(8). Since T(4) = 3, T(8) = T(4) + 1 = 3 + 1 = 4, and T(16) = T(8) + 1 = 4 + 1 = 5.

    Quote Originally Posted by bulletmagnet1234 View Post
    Also if we go through it this way, does that mean we can prove by induction T(2^k) = k + 1 ?
    Yes.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by induction
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: December 5th 2010, 11:07 AM
  2. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM
  3. Proof by induction.
    Posted in the Math Topics Forum
    Replies: 8
    Last Post: October 4th 2008, 05:44 AM
  4. Proof by induction
    Posted in the Algebra Forum
    Replies: 4
    Last Post: September 30th 2008, 07:25 AM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 02:20 PM

Search Tags


/mathhelpforum @mathhelpforum