Ex. 12 p. 342. 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, 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.

Respuesta :

Answer:

Step-by-step explanation:

In this problem we have:

The statement [tex]P(n)[/tex]: Every positive integer [tex]n[/tex] can be written as a sum of distinct powers of two.  

We need to prove two steps:

1.Base Case : Prove that the statement [tex]P(n)[/tex] holds when [tex]n = 1[/tex].  

Induction Hypothesis : Assume that for all positive integers less than or equal to [tex]n[/tex], the statement holds.

2. Inductive Step :  Prove, using the Induction hypothesis, that must [tex]P(n + 1)[/tex] be true.

Proof:

1.Base case: Since [tex]1=2^0[/tex] then the statement [tex]P(1)[/tex] holds.

2.Inductive Step:

Fix  a positive integer [tex]n[/tex]   and suppose that  [tex] P(k)[/tex] holds for all [tex]k \leq n[/tex].  

Case 1: [tex]n+1[/tex] is even, then [tex]\frac{n+1}{2}[/tex] is an integer and we have that  [tex]{ {{1+1<n+1\leq n+n} }[/tex], then   [tex]1< \frac{n+1}{2}\leq n[/tex]. Since  [tex]\frac{n+1}{2}\leq n[/tex],  by the inductive hypothesis, there exists  [tex]\alpha _1, \alpha _2,... ,\alpha _j[/tex]  such that [tex]\frac{n+1}{2}= 2^{\alpha _1} + 2^{\alpha _2}+ ... + 2^{\alpha _j}[/tex]  and  [tex]a_r\neq a_s[/tex] for every [tex]r,s[/tex]∈[tex]\{1,2,...,j\}[/tex].  Then

[tex]n+1=2(\frac{n+1}{2})=2( 2^{\alpha _1} + 2^{\alpha _2}+ ... + 2^{\alpha _j})= 2^{\alpha _1+1} + 2^{\alpha _2+1}+ ... + 2^{\alpha _n+1.}[/tex]

All elements of the  set [tex]\{\alpha _1 + 1, \alpha _2 + 1, ..., \alpha _j + 1\}[/tex] are distinct. Suppose that there exists  [tex]r,s[/tex]∈[tex]\{1,2,...,j\}[/tex] such that   [tex]\alpha _r + 1= \alpha _s + 1[/tex] , then subtracting 1 from both sides of this equation, we get [tex]\alpha _r=\alpha _s[/tex] , this is a contradiction because we are assuming that all the powers [tex]\alpha _1, \alpha _2,... ,\alpha _j[/tex] are distinct. Therefore the statement holds when [tex]n+1[/tex] is even.

Case 2: [tex]n+1[/tex] is odd.

In this case [tex]n[/tex] is even, by the inductive hypothesis we know that [tex]n=2^{\alpha _1} + 2^{\alpha _2}+ ... + 2^{\alpha _j}[/tex], then [tex]n+1=2^{\alpha _1} + 2^{\alpha _2}+ ... + 2^{\alpha _j}+2^{0}[/tex]. Since [tex]\alpha _1, \alpha _2,... ,\alpha _j[/tex] are  all distinct, we only need to prove that 0 ∉ [tex]\{\alpha_1, \alpha_ 2 , ...,\alpha_ j \}[/tex].

If there exists    [tex]r[/tex]∈[tex]\{1,2,...,j\}[/tex]  such that [tex]\alpha _r=0[/tex], then [tex]n=2^{\alpha _1} + 2^{\alpha _2}+ ... + 2^{\alpha _{r-1}}+2^{0} + 2^{\alpha _{r+1}}+...+2^{\alpha _j}\\=2(2^{\alpha _1-1} + 2^{\alpha _2-1}+ ... + 2^{\alpha _{r-1}-1} + 2^{\alpha _{r+1}-1}+...+2^{\alpha _j-1})+1[/tex]

but this  is a contradiction because [tex]n[/tex] is even, therefore [tex]\{\alpha_1, \alpha_ 2 , ...,\alpha_ j,0 \}[/tex] are distinct powers and  the statement holds when [tex]n+1[/tex] is odd. Therefore, the statement that every positive integer [tex]n[/tex] can be written as a sum of distinct powers of two holds for all positive integer.