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