Question

Use strong induction to show that every positive integer can be written as a sum of distinct powers of two (i.e., 20 = 1; 21 = 2; 22 =4; 23 = 8; 24 = 16; :).

For example: 19 = 16 + 2 + 1 = 2^4 + 2^1 + 2^0

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.

Answer 1

her pln) m m can be u po s two. con be written as a sum of distinct We show that prno is true for a integert m. is true for all positive Basps step? As 1 = 2 when K+1 " namely " As 1=20. We have that PC) is tive hypothosis Assume for a positive integer K pois is true for all isisk. tive step : We consider two cases, namely when is even and when K+1 is odd. KHI is even, the (RT) is an integer, and by e Inductive hypothe sps, we can express (K+1)/2 by a Sum of distinct powers of two We can then multiply this sum by 2, which simply increases the exponent of each power of two by 1, so this is again two a sum of distinct powers of that is equal to K+1. when K+L sodd, we have that k seven. of By the inductive hypothesis, we can express K as a sum distinct powers of two. is even the Sum However, since K cannot contain

A E thus Sum we of can add distinct 2° to this sum, whic powers of two and equal remains a sum, which two and quals k+I. Thus, in both cases, we - we can express can expl K+t as a sum of distinct powers of two, so when PC is is true or all isisk, we have that PC Kt) is true. Since PCI) is true, true for an positive . induction. this means that the claim is integers , as show by strond