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.