# Find the sum in this given question very interesting and analytical

Poll closed Aug 11, 2011.

40.0%

60.0%

0 vote(s)
0.0%
4. ### Maybe

0 vote(s)
0.0%
1. Jul 22, 2011

### Vishalrox

Find the sum of : [2$^{}0$/3] + [2$^{}1$/3] + [2$^{}2$/3] + [2$^{}3$/3] + [2$^{}4$/3] + .... + [2$^{}2008$/3]

where [] is the greatest integer function symbol.....

if the question is not clear here is the question..

Find the sum of : [(2^0)/3] + [(2^1)/3] + [(2^2)/3] + [(2^3)/3] + ..... [(2^2008)/3]

Last edited: Jul 22, 2011
2. Jul 22, 2011

### Anamitra

When we divide a number by 3 there are three options:
1. It is exactly divisible
2. Remainder=1
3. Remainder=2
Exact divisibility does not apply to powers of two
Now,
$${2}^{2n}{=}{4}^{n}{=}{(}3+1{)}^{n}$$
When the above quantity is divided by 3 the remainder is one[We get this from binomial expansion]
Therefore
$${2}^{2n}{=}{3k}{+}{1}$$

$${[}\frac{{2}^{2n}}{3}{]}{=}{k}$$

$${k}{=}\frac{{2}^{2n}{-}{1}}{3}$$

Again,

$${2}^{2n+1}{=}{2}{[}{4}^{n}{]}{=}{2}{(}3+1{)}^{n}$$
When the above quantity is divided by 3 the remainder is 2[We get this from binomial expansion]
Therefore
$${2}^{2n+1}{=}{2}{*}{3k}{+}{2}$$

$${[}\frac{{2}^{2n+1}}{3}{]}{=}{2}{*}{k}$$
$${2k}{=}\frac{{2}^{2n+1}{-}{2}}{3}$$
For the above series terms in the first two terms cannot be expanded in the form [3+1]^2n
We write the values directly—>0 +0
Third term=[{2^(2*1)}/3]=1
Fourth term=[{2^(2*1+1)}/3]=2
Fifth term=[{2^(2*2)}/3]
Sixth term=[{2^(2*2+1)}/3]
The value of n remains the same in a pairwise manner as shown above.
From the third term onwards we take to different series
1. $$\Sigma\frac{{2}^{2n}{-}{1}}{3}$$
Summation running from 1 to 1004
2. $$\Sigma\frac{{2}^{2n+1}{-}{2}}{3}$$
Summation running from 1 to 1003

Sum=$$\frac{4}{9}{[}{4}^{1004}{-}{1}{]}{+}\frac{8}{9}{[}{4}^{1003}{-}{1}{]}{-}{1004}$$

Last edited: Jul 22, 2011
3. Jul 23, 2011

### Vishalrox

Nice method....but i just expanded a few terms and i observed the oddth and eventh terms....the oddth term = (previous term * 2)+1....while eventh term = previous term*2...and there are 2009 terms total....the difference between the consecutive oddth terms incremented in GP....1,5,21,85....in the same way for eventh terms too...so consolidating all these....

sum(2^(2n) / 3 - (1/3) + 2^(2n + 1) / 3 - 2/3 , n = 0 , n = 1004) - (2^(2008) / 3 - (1/3))

sum((1/3) * 4^(n) - (1/3) + (2/3) * 4^(n) - (2/3) , n = 0 , n = 1004) - (2^2008 / 3 - (1/3))

(1/3) * sum(4^n + 2 * (4^n - 1) , n = 0 , n = 1004) + 1/3 - (1/3) * 2^(2008) =>

(1/3) * (sum(4^n + 2 * 4^n , n = 0 , n = 1004) - 1 * 1005) + (1/3) - (1/3) * 2^(2008) =>

(1/3) * (3 * sum(4^n , n = 0 , n = 1004) - 1005) + (1/3) - (1/3) * 2^(2008) =>

sum(4^n , n = 0 , n = 1004) - 1005 + (1/3) * (1 - 2^(2008)) =>

(4^(1005) - 1) / 3 + (1/3) * (1 - 4^(1004)) =>

(4 * 4^(1004)) / 3 - (1/3) + (1/3) - 4^(1004) =>

(4/3) * 4^(1004) - 4^(1004) =>

(1/3) * 4^(1004)

So which answer is correct ??????

4. Jul 23, 2011

### Anamitra

Hello Vishal!

So far as your result is concerned the value is not integral.

$$\frac{1}{3}{*}{4}^{1004}$$

$$\frac{1}{3}{*}{(}{3+1}{)}^{1004}$$

$$\frac{1}{3}{*}{(}{3k}{+}{1}{)}$$

As for my result:
$${4}^{1003}{-}{1}{=}{3k}$$ -------------- (1)
Again,

$${4}^{1004}{-}{1}{=}{4}{*}{4}^{1003}{-}{1}$$

$${=}{4}{*}{(}{3k}{+}{1}{)}{-}{1}$$

[Equation (1) has been used to get this from the previous step]

$${=}{12k}{+}{3}$$

Therefore,

Sum=
$$\frac{4}{9}{(}{12k}{+}{3}{)}{+}\frac{8}{9}{3k}{-}{1003}{-}\frac{1}{3}$$
$${=}\frac{{72k}{+}{12}}{9}{-}{1003}{-}\frac{1}{3}$$
$${=}{8k}{+}{1}{-}{1003}$$

The above result is integral
[The result in the last line of post #2 has been modified:modification in post #6]

Last edited: Jul 23, 2011
5. Jul 23, 2011

### Vishalrox

ooh...nice...got it...!!

6. Jul 23, 2011

### Anamitra

I think I have a mistake. I am checking.

Corrected Sum=$$\frac{4}{9}{[}{4}^{1004}{-}{1}{]}{+}\frac{8}{9}{[}{4}^{1003}{-}{1}{]}{-}{3010}{/}{3}$$
$${=}\frac{4}{9}{[}{4}^{1004}{-}{1}{]}{+}\frac{8}{9}{[}{4}^{1003}{-}{1}{]}{-}{1003}{-}{1}{/}{3}$$

[I have got 3010/3 by evaluating [1004+2*1003]/3 . You will get this from the summations 1 and 2 in post #2]

Last edited: Jul 23, 2011
7. Jul 23, 2011

### Vishalrox

I think in the first post u hv made a mistake.......wait...am solvin...am gettin a similar but diff answer..!!

8. Jul 23, 2011

### agentredlum

[a/3] is not [1/3][a], and is not [a]/3, so if you people are factoring out 1/3 i think you should reconsider.

Last edited: Jul 23, 2011
9. Jul 24, 2011

### agentredlum

I think i got this one. Compute the first few terms of [2^n/3]

 As Anamitra points out below i confused floor with cieling function, however a slight adjustment fixes the result. THANK YOU ANAMITRA!

0 + 0 + 1 + 2 + 5 + 10 + 21 + 42 + 85 + 170 + 341 + 682 +1365, ...it is clear that this sum has 2009 terms. Group the first 2008 two at a time in order.

(0+0) + (1+2) + (5+10) + (21+42) + (85+170) + (341+682) + ...+ [2^2008/3] it is clear that each sum in parenthesis is 1 less than a power of 4. There are 1004 such sums.

(4^0-1) + (4^1-1) + (4^2-1) + (4^3-1) + (4^4-1) + ...+ (4^1003-1) + [2^2008/3] re-arrange

-1004 + (4^0 + 4^1 + 4^2 + 4^3 + 4^4 + ... + 4^1003) + [2^2008/3]

The sum of consecutive powers of 4, starting at exponent zero up to n is well known, (4^(n+1)-1)/3 i will derive it later.

-1004 + (4^1004-1)/3 + [2^2008/3]

that nasty last expression isn't so nasty if you rewrite it as [4^1004/3] and realise SUBTRACTING 1 from any power of 4 makes it divisible by 3 AND gives the floor of 4^n/3.

-1004 + (4^1004-1)/3 + (4^1004-1)/3 = -1004 + (2(4^1004)-2)/3 = -1004 + (2^2009-2)/3

SUBTRACTING 1 from any even power of 2 makes it divisible by 3 so this gives a whole number

(2^2009 - 2)/3 -1004

DERIVATION:

S = 4^0 + 4^1 + 4^2 + ... + 4^n

multiply by 4

4S = 4^1 + 4^2 + 4^3+ ... + 4^n + 4^(n+1)

subtract

4S - S = 4^(n+1) - 1

S = (4^(n+1) -1)/3

P.S. Thanx to Anamitra for pointing out my confusion, from now on lets just call it the floor function to eliminate confusing 'greatest integer' nonsense.

Last edited: Jul 24, 2011
10. Jul 24, 2011

### Anamitra

Hi Agentredlum, [x] is the greatest integer less than or equal to x. They call it the"floor"

But you have taken the ceiling--> smallest integer greater than or equal to x.

Calculation of terms[GIF]
$${[}\frac{{2}^{1}}{3}{]}{=}{0}$$

$${[}\frac{{2}^{2}}{3}{]}{=}{1}$$

$${[}\frac{{2}^{3}}{3}{]}{=}{2}$$

$${[}\frac{{2}^{4}}{3}{]}{=}{5}$$

$${[}\frac{{2}^{5}}{3}{]}{=}{10}$$

$${[}\frac{{2}^{6}}{3}{]}{=}{21}$$

The series is:
0+0+1+2+5+10+21+42+85.....

The the terms of the ceiling you have got:

1+1+2+3+6+11+22+43+86.....
For the adjustment in the last term you seem to have taken the floor.
I hope the difference is clear now.

Last edited: Jul 24, 2011
11. Jul 24, 2011

### Anamitra

Caculations

$${2}^{2n}{=}{(}{3+1}{)}^{n}{=}{3k+1}$$

$${2}^{2n+1}{=}{2}{(}{3+1}{)}^{n}{=}{6k+2}$$

If [] denotes the ceiling:

$${[}\frac{{2}^{2n}}{3}{]}{+}{[}\frac{{2}^{2n+1}}{3}{]}$$

$${=}{k+1}{+}{2k+1}$$

$${=}{3k+2}$$

$${=}{2}^{2n}{+}{1}$$

[Since $${3k}{=}{2}^{2n}{-}{1}$$ ...From the first step]

For n=0,1,2,3,4...

the formula gives:

2=1+1
5=2+3
17=6+11
65=22+43 etc.

Last edited: Jul 24, 2011
12. Jul 24, 2011

### agentredlum

Please take a look at my edited post #9, i think i fixed the proof.

13. Jul 24, 2011

### agentredlum

LOL By confusing floor with ceiling my technique solved both problems. I guess i made a 'right' mistake. The same question but ceiling instead of floor gives... [2^0/3] + [2^1/3]+ [2^2/3]+ ... + [2^2008/3] = (2^2009 + 1)/3 + 1004

14. Jul 24, 2011

### Anamitra

I have got the same thing in post #6 as you have got finally.

Sum=$$\frac{4}{9}{[}{4}^{1004}{-}{1}{]}{+}\frac{8}{9}{[}{4}^{1003}{-}{1}{]}{-}{3010}{/}{3}$$

$${=}\frac{{4}^{1005}}{9}{+}\frac{{2}{*}{4}^{1004}}{9}{-}{12}{/}{9}{-}{3010}{/}{3}$$

$${=}\frac{{4}^{1004}}{9}{(}{4+2}{)}{-}{12}{/}{9}{-}{1004}{+}{2}{/}{3}$$

$${=}\frac{{2}{*}{4}^{1004}}{3}{-}{2}{/}{3}{-}{1004}$$

$${=}\frac{{2}{*}{4}^{1004}{-}{2}}{3}{-}{1004}$$

$${=}\frac{{2}^{2009}{-}{2}}{3}{-}{1004}$$

But your method is comfortable/easier to work with.The observation you made is quite interesting.But you should always try to establish it in a general manner from theoretical considerations. In this case the general proof is simple enough. You can always follow a technique similar to the one in post #11 or some suitable alternative.

Last edited: Jul 24, 2011
15. Jul 24, 2011

### Anamitra

The summations 1 and 2 in post #2 can enable one to calculate two distinct series[separately] in relation to the floor function.

Similar summations can be developed for the ceiling function also.

One of course could look for other formulas arising out of some interesting pattern in the terms comprising the series.

[One could also think of replacing the divisor 3[in the series of post #1] by some other natural and follow some technique similar to the one shown in post #2 to develop summation formulas.]

Last edited: Jul 24, 2011
16. Jul 24, 2011

### agentredlum

Thank you for your notations and indications. Can you please post a picture? I am using my BRAIN to decode TeX but i would rather use my PINKY. My browser does not decode TeX and sometimes it's hard for me to understand posted formulas. Sorry to put you into too much trouble.

Last edited by a moderator: Sep 25, 2014
17. Jul 24, 2011

### Anamitra

Hello!
I have uploaded a .bmp file for you.

#### Attached Files:

• ###### Abc.bmp
File size:
231.7 KB
Views:
102
18. Jul 25, 2011

### agentredlum

NICE! THANK YOU VERY MUCH!!!

19. Jul 25, 2011

### Mtoag

Hey....gud one...very interesting.

Last edited: Jul 25, 2011