(adsbygoogle = window.adsbygoogle || []).push({}); 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] + ...?

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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.

**Physics Forums | Science Articles, Homework Help, Discussion**