Greatest Integer Function Proof?

Let us start by defining f(n) to be the infinite sum above. I.e., we have:

f(n) = [k=1, ∞]∑⌊(n+2^(k-1)) / 2^k⌋

We wish to show that for every positive integer n, f(n) = n. First, let us simplify the expression for f(n):

f(n) = [k=1, ∞]∑⌊n/2^k + 1/2⌋

This gives us:

f(n+1) - f(n) = [k=1, ∞]∑(⌊(n+1)/2^k + 1/2⌋ - ⌊n/2^k + 1/2⌋)

Let us examine the individual terms in the sum. We consider three cases:

--------------------------

Case 1: 2^k | (n+1)

In this case, we have that (n+1)/2^k is an integer, and as (n+1)/2^k + 1 is clearly greater than (n+1)/2^k + 1/2, (n+1)/2^k is the largest integer less than or equal to (n+1)/2^k + 1/2 -- i.e. ⌊(n+1)/2^k + 1/2⌋ = (n+1)/2^k.

Now, since k≥1, we know that 1/2^k ≤ 1/2, so n/2^k = (n+1)/2^k - 1/2^k ≥ (n+1)/2^k - 1/2, so n/2^k + 1/2 ≥ (n+1)/2^k. But as (n+1)/2^k + 1 is clearly greater than n/2^k + 1/2, it follows that (n+1)/2^k is the largest integer less than or equal to n/2^k + 1/2 as well.

So ⌊n/2^k + 1/2⌋ = (n+1)/2^k = ⌊(n+1)/2^k + 1/2⌋, so ⌊(n+1)/2^k + 1/2⌋ - ⌊n/2^k + 1/2⌋ = 0

------------------------

Case 2: 2^k ∤ (n+1), but 2^(k-1) | (n+1)

Since 2^(k-1) | (n+1), we have that (n+1)/2^(k-1) is an integer. However, since 2^k ∤ (n+1), (n+1)/2^(k-1) is an odd integer, so (n+1)/2^(k-1) + 1 is an even integer, which makes (n+1)/2^k + 1/2 = ((n+1)/2^(k-1) + 1)/2 an integer. So ⌊(n+1)/2^k + 1/2⌋ = (n+1)/2^k + 1/2

Now, since k≥1, we know that 1/2^k ≤ 1/2, so n/2^k = (n+1)/2^k - 1/2^k ≥ (n+1)/2^k - 1/2, so n/2^k + 1/2 ≥ (n+1)/2^k > (n+1)/2^k - 1/2. Now, since (n+1)/2^k + 1/2 is an integer, it follows that ((n+1)/2^k + 1/2) - 1 = (n+1)/2^k - 1/2 is an integer less than n/2^k + 1/2. However, (n+1)/2^k + 1/2 > n/2^k + 1/2, it follows that (n+1)/2^k - 1/2 is also the largest integer less than or equal to n/2^k + 1/2. Thus, ⌊n/2^k + 1/2⌋ = (n+1)/2^k - 1/2

From this it follows that ⌊(n+1)/2^k + 1/2⌋ - ⌊n/2^k + 1/2⌋ = ((n+1)/2^k + 1/2) - ((n+1)/2^k - 1/2) = 1.

----------------------

Case 3: 2^(k-1) ∤ (n+1)

Let K = ⌊n/2^k + 1/2⌋. By the definition of the floor function, K+1 > n/2^k + 1/2. Suppose that K+1 ≤ (n+1)/2^k + 1/2. Then we have:

n/2^k + 1/2 < K+1 ≤ (n+1)/2^k + 1/2

Multiplying by 2^k:

n + 2^(k-1) < 2^k(K+1) ≤ (n+1) + 2^(k-1)

Subtracting 2^(k-1):

n < 2^k(K+1) - 2^(k-1) ≤ n+1

Now, since k≥1, k-1≥0, so 2^(k-1) is an integer. Since K is an integer, it follows that 2^k(K+1) is an integer, so 2^k(K+1) - 2^(k-1). But there are no integers strictly between n and n+1, so this inequality means that:

2^k(K+1) - 2^(k-1) = n+1

Now, clearly 2^(k-1) | 2^k(K+1) - 2^(k-1), so it follows from this equality that 2^(k-1) | n+1. However, we assumed that 2^(k-1) ∤ (n+1), so this is a contradiction. Therefore, our initial supposition, that K+1 ≤ (n+1)/2^k + 1/2, is false, and we must have K+1 > (n+1)/2^k + 1/2.

Since by the definition of K, K ≤ n/2^k + 1/2 < (n+1)/2^k + 1/2 < K+1, it follows that K is the largest integer less than (n+1)/2^k + 1/2, so ⌊(n+1)/2^k + 1/2⌋ = K = ⌊n/2^k + 1/2⌋, so ⌊(n+1)/2^k + 1/2⌋ - ⌊n/2^k + 1/2⌋ = 0

------------------------

Now, it is easy to see that the three cases considered above are mutually exclusive and collectively exhaustive. Further, for every natural number n, there is exactly one k such that 2^(k-1) | (n+1) but 2^k does not (just choose the smallest k such that 2^k does not divide n+1). This means that the sum:

f(n+1) - f(n) = [k=1, ∞]∑(⌊(n+1)/2^k + 1/2⌋ - ⌊n/2^k + 1/2⌋)

Has exactly one term which is 1, and all of the other terms are zero. Thus, for all natural numbers n, f(n+1) - f(n) = 1.

Now, we merely observe that f(1) = 1 (easily shown), and note that if f(n) = n, then f(n+1) = f(n) + (f(n+1) - f(n)) = n + 1, so by induction, it follows that for all n, f(n) = n. Q.E.D.

I don't know the answer, but I'll share a bit.

We can't do much with the rounding-down symbols, so we'll have to find away to eliminate them. Or maybe induction can work also.

I would try induction.

[ (n + 2) / 2 ] + [ (n + 3) / 4 ] + ... = n + 1

Subtract by 1 and set it equal to n.

[ (n + 2) / 2 ] + [ (n + 3) / 4 ] + ... - 1 =

[ (n + 1) / 2 ] + [ (n + 2) / 4 ] + ... = n

So now we can prove that their difference is 0.

-----

Something to know:

[ (n + k) / m ]

If n is less than k, the terms after that will equal 0.

-----

EDIT:

[ (n + 1) / 2 + 1/2 ] + ... + [ (n + 2^k) / 2^(k + 1) + 1/2 ] - 1 = [ (n + 1) / 2 ] + ... + [ (n + 2^k / 2^(k + 1) ]

2^(k + 1) > n > 2^k and part of the set of integers.

We must prove: We must prove that only one will round down to be an integer greater than one of it's coinciding terms.

This means this:

[ (n + k) / m + 1/2 ] = [ (n + k) / m ] + 1

Each term can be written as:

n / 2^p + 1/2

The next few terms would be:

n / 2^(p + 1) + 1/2, n / 2^(p + 2) + 1/2, n / 2^(p + 2) + 1/2, ...

If x + 1/2 ≤ n / 2^p < x + 1

Adding by 1/2 will bring it to the next integer.

Anything after this will be...

x/2 + 1/4 ≤ n / 2^(p + 1) < x/2 + 1/2

Therefore you cannot go up after the 2^p denominator term...

2x + 1 ≤ n / 2^(p - 1) < 2x + 2

Doesn't round up.

Therefore this is proved. Hopefully you understood what I meant.

Here's my approach.

Let n = 2^k + d

where 0 ≤ d < 2^k

i.e. n is somewhere in [2^k, 2*2^k)

Let S = ∑{i=1,∞} [ {n+2^(i-1)} / 2^i ]

= ∑{i=1,∞} [ n/2^i + 1/2]

It can be shown that for i > k+1, the term inside the [ ] < 1, so terms above i = k+1 can be dropped.

S = ∑{i=1,k+1} [ n/2^i + 1/2]

We must prove that S = ∑{i=1,k+1} [ n/2^i + 1/2] = n ...(1)

Writing n = 2^k + d

S = ∑{i=1,k+1} [ 2^(k-i) + d/2^i + 1/2]

For i = 1 to k, 2^(k-i) is an integer,

while for i = k+1, 2^(k-i) = 1/2

So we can write

S = ∑{i=1,k} [ 2^(k-i) + d/2^i + 1/2] + [1 + d/2^(k+1)]

The last term is clearly 1, since d/2^(k+1) < 1, and in the first term, we can take the 2^(k-i) out of the [ ]

S = 1 + ∑{i=1,k} 2^(k-i) + ∑{i=1,k} [ d/2^i + 1/2 ]

= 2^k + ∑{i=1,k} [ d/2^i + 1/2 ]

after simplification

Now we are left to show that

∑{i=1,k} [ d/2^i + 1/2 ] = d ...(2)

which is now a reduction of eqn (1) since

d < 2^k, while n < 2^(k+1)

We can continue reducing until we get to

∑{i=1,1} [ 1/2^i + 1/2 ] = 1

or ∑{i=1,1} [ 0/2^i + 1/2 ] = 0

Once we verify that the identify holds for n = 0 and 1, we can use this reduction process in reverse and use the principles of induction to get our result.

Essentially any n can be written as a summation of powers of 2, with the last term being 1 or 0.

n = a0 + ∑{i=1,k} a(i) * 2^i

where a(i) = 0 or 1

Using our reduction formula, we can keep taking all the powers of 2 out until we get

S(n) = S(a0) + ∑{i=1,k} a(i) * 2^i

Since S(0) = 0 and S(1) = 1, it follows that

S(n) = n

[(n+1) / 2] + [(n+2) / 4] + [(n+4) / 8] + [(n+8) / 16] + ... = n.

More explicitly,

f(n)=sum([(n+2^(j-1))/2^j], j=1..[ln(n)/ln(2)]+1)=n

Induction Proof: Clearly true for n=2^0.

Now assume true for all n<2^k for some k>=0.

Let n=2^k+a for 0<=a<2^k. Then

f(n)=f(2^k+a)=sum([(2^k+a+2^(j-1))/2^j], j=1..[ln(2^k+a)/ln(2)]+1)

=sum([2^k/2^j+(a+2^(j-1))/2^j], j=1..[ln(2^k+a)/ln(2)]+1)

=sum([2^(k-j)+(a+2^(j-1))/2^j], j=1..[ln(2^k+a)/ln(2)]+1)

=sum(2^(k-j)+[(a+2^(j-1))/2^j], j=1..[ln(2^k+a)/ln(2)]+1)

=sum(2^(k-j), j=1..[ln(2^k+a)/ln(2)]+1)

+sum([(a+2^(j-1))/2^j], j=1..[ln(2^k+a)/ln(2)]+1)

=sum(2^(k-j), j=1..[ln(2^k+a)/ln(2)]+1)

+f(a)

=sum(2^(k-j), j=1..[ln(2^k+a)/ln(2)]+1)+a

=sum(2^(k-j), j=1..(k+1))+a

=2^k+a

=n

QED

Writing n in base 2:

n= a+2b+4c+8d+....., then

[(n+1)/2] = a+ b + 2c+4d+......

[(n+1)/4]= b+ c + 2d+.......

[(n+1)/8]= c + d +.....

..................................................... and so on,

from which the equality is apparent.