1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Math induction - I think i totally missed the point of it.

  1. Jun 29, 2012 #1
    1. The problem statement, all variables and given/known data

    "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[itex]^{0}[/itex] = 1, 2[itex]^{1}[/itex] = 2, 2[itex]^{2}[/itex]= 4, and so on. [Hint: for the inductive step, separately consider the case where k+1 is even and where it is odd. When it is even, note that (k+1)/2 is an integer.]

    2. Relevant equations

    Assume P(k) and show that P(k)--->P(k+1)

    3. The attempt at a solution

    P(n): every integer n[itex]\geq[/itex]1 can be written as a sum of distinct powers of 2.

    Basis step: clearly P(1) = 1 = 2[itex]^{0}[/itex]
    1 = 1

    Inductive Step: Assume for some k[itex]\in[/itex]N that k can be written as distinct powers of 2. Show that k+1 can be written as distinct powers of 2.

    Case 1: k+1 is even:
    Clearly if k = 2[itex]^{j}[/itex] by the inductive hypothesis, then k+1 = 2[itex]^{j}[/itex] + 2[itex]^{0}[/itex]

    I dont even see why I need a case 2. Apparently I have proven this by a direct proof even though I was trying to do induction.

    I just don't know how to properly set up induction word problems. I have an easier time when the conjecture is given numerically. How can I write an equation for "n can be written as the sum of powers of 2" without making a bunch of new variables, like n = 2[itex]^{j}[/itex] + 2[itex]^{m}[/itex] + 2[itex]^{p}[/itex] + ...?
    Last edited: Jun 29, 2012
  2. jcsd
  3. Jun 29, 2012 #2
    What are you doing here? That doesn't seem to make much sense...

    So if you have k even, then by induction there exists a representation
    [tex] k = 2^a + 2^b + 2^c + ... [/tex]
    where a, b, c, ... > 0. Then the unique representation for k+1 is just
    [tex] k+1 = 2^0 + k [/tex]

    Then you need to work out what happens when k is odd.
  4. Jun 29, 2012 #3
    sorry, that was my first time fooling around with the superscripts. It's fixed now.
  5. Jun 29, 2012 #4
    Yea those were messed up but your reasoning is still a bit incomplete
  6. Jun 29, 2012 #5
    Ok, so this is what I have so far.

    Case 1: k is even

    So k = 2[itex]^{a}[/itex] + 2[itex]^{b}[/itex] + 2[itex]^{c}[/itex] + ....

    a, b, c, ...[itex]\geq[/itex]0

    Then k + 1 = k + 2[itex]^{0}[/itex]
    k + 1 = k + 1

    Case 2: k is odd

    So k = 2[itex]^{0}[/itex] + 2[itex]^{a}[/itex] + 2[itex]^{b}[/itex] + 2[itex]^{c}[/itex] +...

    Where a, b, c, ...[itex]\geq[/itex]0

    So k+1 = 2[itex]^{0}[/itex] + 2[itex]^{0}[/itex] + 2[itex]^{a}[/itex] + 2[itex]^{b}[/itex] + 2[itex]^{c}[/itex]

    k + 1 = 2[itex]^{0}[/itex](1+1) + 2[itex]^{a}[/itex] + 2[itex]^{b}[/itex] + 2[itex]^{c}[/itex]

    k+1 = k + 2????
  7. Jun 29, 2012 #6
    don't worry about even or odd, instead think of it as for for k=1....n-1 we have k=[itex]\sum_{i=0}^{m}2^{f_i(k)}, f_i(x)=0,1[/itex] let [itex] n-1=\sum_{i=0}^{m}2^{f_i(n-1)}[/itex], then [itex] 2*(n-1)=\sum_{i=0}^{m}2^{f_i(n-1)+1}[/itex]
    from there add 2 to both sides, and divide by 2 (made possible since 2n is guaranteed even).
  8. Jun 29, 2012 #7
    No, you want to show that you can write k+1 = 2^a + 2^b + 2^c + ..., not that k+1=k+1 (that is obvious)

    That's a very cute way of doing it
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook