Mathematical Equality

[jay_shark]

Prove that

N=[N/2] +[N/4] + [N/8] +...+[N/2^n] +...

where [a/b] is the nearest integer function .

[bluesbassman]

[ QUOTE ]
Prove that

N=[N/2] +[N/4] + [N/8] +...+[N/2^n] +...

where [a/b] is the nearest integer function .

[/ QUOTE ]

For what value is [1/2] defined?

[jay_shark]

[1/2]=1 ; [2.5]=3 etc .

[bluesbassman]

The conjecture is false. Counterexample: Let N = 1.1.

Did you mean to define the domain of the r.h.s. of the equality to be N = any integer?

[jay_shark]

N is an arbitrary natural number .

[jay_shark]

It's actually true for natural numbers .

[holmansf]

If you write N in binary it becomes somewhat clearer how this works. Say

N = 2^n a_n + ... + 2 a_1 + a_0.

Then you can see that for each k:

[N/2^k] = 2^{n-k} a_n + ... + 2 a_{k+1} + a_k + a_{k-1}

Now collect all the terms multiplied by the same a_i in the sum [N/2] +[N/4] + [N/8] +...+[N/2^n] +... to find that this is equal to:

a_0 + a_1 + a_1 + a_2 + a_2 + 2 a_2 + ... + a_n +Sum_{k=0}^{n-1} 2^k a_k = N.

[tarheeljks]

can't you just factor out N so that this summation becomes a geometric series that converges to 1?

[m_the0ry]

[ QUOTE ]
can't you just factor out N so that this summation becomes a geometric series that converges to 1?

[/ QUOTE ]

This brings us back to the hardest part of the problem, which is mathematically defining the 'nearest integer' function. I think it would be hard to rigorously show that you can factor out the numerator for this function considering 1/N does not necessarily equal [N/1]^-1.

I had to use fourier series to define the nearest integer function as follows:

NearestInt = x + 1/pi * sigma(k=1 => infinity)[sin(2*pi*k*x + 2*pi*k)

From that the expansion of this problem becomes

N = sigma(i=1 | infinity){N/(2^i) + 1/pi * sigma(k=1 | infinity)[sin(pi*k*N/(2^(i-1)) + pi*k)}

The sin series converges to zero both with respect to i and k, because the harmonics cancel themselves out as well as each other, so you're left with the real number series

N = sigma(i=1 | infinity){N/2^(i)}

which clearly converges to N.

[tarheeljks]

didn't even read the part about nearest int func, never mind.

could you explain a little more how you used the fourier series to define the func?