Induction series : Something is not right

Algebra Level 4

Prove that any positive integer n n can be written as distinct powers of 2 2 .

  1. Base case: 1 = 2 0 , 2 = 2 1 , 3 = 2 0 + 2 1 , . . . . . , 7 = 2 2 + 2 1 + 2 0 1 = 2^{0}, 2 = 2^{1}, 3=2^{0}+2^{1},.....,7=2^{2}+2^{1}+2^{0}
  2. We assume that statement holds true for positive integers 1 , 2 , 3 , . . . . . . . . . n 1,2,3,.........n
  3. For n + 1 n+1 , let n + 1 = 2 k + a n+1=2^{k}+a , where 0 < a < n + 1 0<a<n+1
  4. Let a = 2 x 1 + 2 x 2 + 2 x 3 + . . . . . . . + 2 x m a=2^{x_{1}}+2^{x_{2}}+2^{x_{3}}+.......+2^{x_{m}} , with x 1 , x 2 , . . . . . x m x_{1},x_{2},.....x_{m} all being distinct whole numbers.
  5. Because n + 1 = 2 k + 2 x 1 + 2 x 2 + 2 x 3 + . . . . . + 2 x m n+1=2^{k}+2^{x_{1}}+2^{x_{2}}+2^{x_{3}}+.....+2^{x_{m}} , we can conclude that n + 1 n+1 can also be the sum of distinct powers of 2.
  6. Hence all positive integers can be represented as distinct powers of 2.

Between which steps am I missing something? If the missing step is between 1 and 2, input as 12.


The answer is 34.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

You should see that I have forgotten to put 2 k > a 2^{k}>a .

Because if not, 2 k 2^{k} might be one of a = 2 x 1 + 2 x 2 + 2 x 3 + . . . . . . + 2 x m a=2^{x_{1}}+2^{x_{2}}+2^{x_{3}}+......+2^{x_{m}} , which contradicts with our statement n + 1 n+1 can be a sum of distinct powers of 2 2 .

In future, you might want to make questions with only a small finite set of answers multiple choice. Multiple choice means only 1 guess, whereas a numerical answer gives 3 guesses. In the problem above, the answer was going to be either 12, 23, 34, 45 or 56. I guessed it wouldn't be the answer that you had chosen to illustrate in the problem, and also felt it was unlikely to be 56 as it is the last one, so worked my way through 23,34,45 and got it right

Stephen Mellor - 3 years, 2 months ago

Log in to reply

Noted, but given that MCQs offer only one chance, I'd rather stick to short questioning.

Bryan Lee Shi Yang - 3 years, 2 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...