Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#26 2015-06-22 07:59:43

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Write a positive integer as the sum of powers of 2

400 points


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#27 2015-06-23 03:38:54

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

Re: Write a positive integer as the sum of powers of 2

Here is the proof of the conjecture:

4hA4XtzJZc-image.jpg


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#28 2015-06-23 03:43:42

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Write a positive integer as the sum of powers of 2

I had that answer way before him and ole Calvin has made a good point.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#29 2015-06-23 04:03:39

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

Re: Write a positive integer as the sum of powers of 2

You did not have the proof. You did not even attempt it.


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#30 2015-06-23 04:15:42

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Write a positive integer as the sum of powers of 2

The first question is a computation and is interesting.

Proofs:

https://www.youtube.com/watch?v=ZBAijg5Betw


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#31 2015-06-23 04:33:15

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

Re: Write a positive integer as the sum of powers of 2

Kaboobly Doo!


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#32 2015-06-23 04:35:21

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Write a positive integer as the sum of powers of 2

I agree, proofs are kaboobly doo. Anyway, that guys proof needs a bit of work.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#33 2015-06-23 05:16:09

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

Re: Write a positive integer as the sum of powers of 2

I did not say proofs are Kaboobly Doo


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#34 2015-06-23 06:37:00

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Write a positive integer as the sum of powers of 2

You should have. Soon that form of math will be extinct.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#35 2015-06-24 02:47:53

phanthanhtom
Member
Registered: 2012-06-22
Posts: 290

Re: Write a positive integer as the sum of powers of 2

Agnishom, I don't understand this part:

"By the inductive hypothesis, this is the number of k such that n - 2^k = 2^j - 1 for some j, i.e. the number of ways to write n = 2^k + 2^j - 1."

Can you please?

Offline

#36 2015-06-24 03:23:50

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

Re: Write a positive integer as the sum of powers of 2

We are using strong induction here.

First we show that it is true for some of the beginning values by computation.

Then, we assume that for some value n, all of the preceeding values show the proposed property.

We now need to show that n also shows the same property, to complete the induction.

Note that f(n) = f(n-2^0) + f(n-2^1) + ... + f(n-2^k) + ...

We're interested in if any of these are odd. By the induction hypothesis, if there is such a term, it should be of the form 2^j - 1. This is because we've chosen to accept that only the output of such numbers are odd.

So, n - 2^k = 2^j - 1


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#37 2015-06-24 18:02:04

phanthanhtom
Member
Registered: 2012-06-22
Posts: 290

Re: Write a positive integer as the sum of powers of 2

Also Agnishom, I think he only proved "if f(n) is odd, n is of the form 2^k - 1". Not the other way around.

Offline

#38 2015-06-24 20:43:08

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

Re: Write a positive integer as the sum of powers of 2

Nope. He proved the other thing too.

When f(n) is not of that form, the odds pair up


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

Board footer

Powered by FluxBB