Results 1 to 2 of 2

Math Help - Strong Induction Problem

  1. #1
    Junior Member
    Joined
    Oct 2008
    From
    Dallas, TX
    Posts
    71

    Strong Induction Problem

    Use strong induction to show that every positive integer n can be written as a sum of distinct powers of two, that is, as a sum of a subset of the integers 2^0=1, 2^1=2, 2^2=4, ...

    I know for the inductive step I should seperately consider the case where k + 1 is even and where it is odd, so when it is even (k + 2) / 2 is an integer. Where would I proceed from here?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by aaronrj View Post
    Use strong induction to show that every positive integer n can be written as a sum of distinct powers of two, that is, as a sum of a subset of the integers 2^0=1, 2^1=2, 2^2=4, ...

    I know for the inductive step I should seperately consider the case where k + 1 is even and where it is odd, so when it is even (k + 2) / 2 is an integer. Where would I proceed from here?
    Say that k<n can be written as exponents of two. Now if n is even then set k=\tfrac{n}{2} which is a sum of exponents of two. Multiply through both sides by 2 and you have that 2k = n is a sum of exponents of two. And if n is odd then set k=\tfrac{n-1}{2} which is a sum of exponents of two. Multiply through both sides by 2 and add 1 to get 2k+1=n is a sum of exponents of two.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] strong induction problem involving power set
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 8th 2011, 01:32 AM
  2. [SOLVED] some problem in strong induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 6th 2011, 07:05 PM
  3. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 12:36 AM
  4. Strong induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 26th 2010, 01:10 PM
  5. Strong Induction Problem using Summations
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 3rd 2009, 09:12 AM

Search Tags


/mathhelpforum @mathhelpforum