Homework 18

Homework 18

Kayla Holt 26 Oct 2010 16:06

I am haveing trouble on number 3. My base step is: If n= 1, then 1=2⁰. All I can come up with for the Induction Step is: Let k be an element of the natural numbers and assume n_j = 2^j for j less than or equal to k. Is that the correct way to start?

Re: Homework 18

Dana Ernst 27 Oct 2010 23:38

Your base case looks good.

For your inductive step, let $k\in\mathbb{N}$ and assume that $j$ can be written as distinct powers of 2 for all $j\leq k$. You need to show that $k+1$ can be written as a sum of distinct powers of 2.

Re: Homework 18

Dana Ernst 28 Oct 2010 00:34

As an additional hint, consider two possibilities:

1. $2^0$ does not appear in the sum for $k$, or
2. $2^0$ does appear in the sum for $k$.

The first case is "easy." The second case is more difficult and requires a trick. If $2^0$ does appear in the sum for $k$, then $k$ must be odd. Why? In this case, $k+1$ is even. Use the induction hypothesis on $(k+1)/2$. Then multiply both sides by 2.