Mathematical Equality
 

Prove that

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

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

Re: Mathematical Equality
 

[ 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?

Re: Mathematical Equality
 

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

Re: Mathematical Equality
 

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?

Re: Mathematical Equality
 

N is an arbitrary natural number .

Re: Mathematical Equality
 

It's actually true for natural numbers .

Re: Mathematical Equality
 

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.

Re: Mathematical Equality
 

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

Re: Mathematical Equality
 

[ 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.

Re: Mathematical Equality
 

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?

Re: Mathematical Equality
 

Lets say x is a real number

nearest(x)= x + f

Where f and x are both real numbers but their sum is an integer. For example

nearest(2.32) = 2.32 - .32
nearest(2.45) = 2.45 - .45
nearest(2.62) = 2.62 + .38

f linearly increases with x, forming a ramp of slope 1 spanning from -.5 to .5 over an interval of 1. At that point it becomes discontinuous and starts over again. This is obviously a periodic function and thus is very well described by a fourier series. Going from periodic function to fourier series can be tricky so I cheated, referencing the common 'saw wave' signal which has the exact same form except translated in a few ways. I just modified that function and then derived the rest.

One thing I noted is that technically the saw function in fourier form is defined at .5 as being zero. But if you infinitesimally translate the function to the left the sinusoidal series' still converge to zero.

EDIT: I made a mistake in the first post the sinusoids only converge to zero with respect to i.

Re: Mathematical Equality
 

There are several different proofs.

Clearly the equality holds for 2^M for any integer M.

Each of the functions f(k; x) = [x/2^k] are clearly
nondecreasing and the only change from an integer N to N+1
is in the function f(d; N) where d is the nth bit from the
right in the binary representation that undergoes a
transition from 0 to 1.

Alternatively, you can show that when going from x= N to
N+1, no more than one function f(k; x) increases. Thus,
AT MOST one of the functions is incremented by one. On
the other hand, the equality is true at N = 0 and N = 2^M
for any M, so there MUST BE exactly one function that
increases since the RHS must increase by one for every
integer N less than 2^M.

Re: Mathematical Equality
 

[ QUOTE ]
[ 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.

[/ QUOTE ]

I think there are some nontrivial issues of a) convergence of fourier series here and b) interchanging summation and integration.

most troubling is the fact that the fourier series of this function (to see this it's probably easiest to write it as f(x) = x + {x-1/2}, where { } denotes the greatest integer function) will exhibit the Gibbs Phenomenon.

Re: Mathematical Equality
 

[ QUOTE ]
Alternatively, you can show that when going from x= N to
N+1, no more than one function f(k; x) increases.

[/ QUOTE ]

So how do you prove this?

[ QUOTE ]

Thus,
AT MOST one of the functions is incremented by one.

[/ QUOTE ]

Don't you also need to prove that the maximum increment value is one?

Re: Mathematical Equality
 

The proof that jumps out at me is to prove that it holds for 1, and then use induction: If it holds for n, it holds for 2n and 2n+1. The hardest case is that
[(2n+1)/2]+[(2n+1)/4]+[(2n+1)/8]+...=
[(2n+1)/2]+[n/2]+[n/4]+...=
(n+1)+n by induction.

Re: Mathematical Equality
 

Here is a neat solution .

The number of odd integers not exceeding N is [N/2] whether or not n is even . Or equivalently , the number of integers not divisible by two and not exceeding N is [N/2]

The number of integers not divisible by 4 and not exceeding N but are divisible by 2 is [N/4]. I'll leave why this is true up to the reader .

The number of integers not divisible by 8 and not exceeding N but are divisible by 4 is [N/8] . We repeat this procedure infinitely many times to give us that

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