Sum of a Series

Date: 10/26/96 at 15:18:7
From: Jae Jang
Subject: Problem

Compute the sum of the coefficients of the expansion of (x+0.5)^100 
for which the exponent is divisible by three.

Date: 11/08/96 at 16:07:10
From: Doctor Yiu
Subject: Re: Problem

Dear Jae,

The easiest way to solve this problem is NOT to find this sum all by
itself, but rather to find it along with two other numbers.

Let's try to write down the expansion of (x+0.5)^100.  Instead of 
writing it in the natural order, let's write:

(x+0.5)^n = constant term + the sum of terms of x^3, x^6, x^9, etc 
up to x^99 PLUS the sum of terms of x, x^4, x^7, etc up to x^100
PLUS the sum of terms of x^2, x^5, x^8, etc up to x^98.

All together, there are 101 terms.  In the above expression, we 
collect these terms into THREE classes:

(1)  Those with exponents divisible by 3.  Let's call the SUM of the 
COEFFICIENTS of these terms A.

(2)  Those with exponents of the form 3k+1.  Let's call the SUM of the
COEFFICIENTS of these terms B. 

(3)  Those with exponents of the form 3k+2.  Let's call the SUM of the
COEFFICIENTS of these terms C.

If you substitute 1 for x, then all powers of x are equal to 1 and: 

A + B + C = 1.5^100 = 3^100/2^100

This is a LINEAR equation in THREE unknowns (A, B, C).  Now we want to 
make two more SUITABLE substitutions to construct two MORE linear 
equations in A, B, and C. 

The class (1) of terms are those that look like: 1, x^3, x^6, x^9, up 
to x^99.  If you want to make a substitution to COLLECT the 
COEFFICIENTS of these terms together, you need: 

1 = x^3 = x^6 = x^9 = . . . = x^99. 

The substitution x=1 above does this precisely.  BUT, besides x=1, ANY 
number x satisfying x^3 = 1 will do.  Such an x is called a "cube root 
of unity."  If you are already familar with this term, then you 
prodeed by considering u and v to be the two COMPLEX cube roots of 
unity and recall the following useful properties:

(i)  u^3 = 1 and v^3 = 1

(ii)  u = (-1+Sqrt(-3))/2  and  v = (-1-Sqrt(-3))/2

(iii)  u^2 = v  and  v^2 = u

(iv)  1 + u + v = 0

If you are not familiar with the term "cube root of unity," here is 
some background info:

If x^3 = 1, then x^3 - 1 = 0.  Factoring, we have (x-1)(x^2+x+1) = 0.  
This means x=1, OR, by the quadratic formula: 

x = (-1+ or - Sqrt(-3))/2  = -0.5 + or - Sqrt(-3)/2.

There are two such numbers, and they are complex numbers.  I shall 
call them u (corresponding to the plus sign) and v (corresponding to 
the minus sign).  Note that u = (-1+Sqrt(-3))/2 and 
v = (-1-Sqrt(-3))/2, which satisfies u^3 = 1 and v^3 = 1.

Also, u + 0.5 = Sqrt(-3)/2 and v + 0.5 = -Sqrt(-3)/2.

These two numbers u and v have several interesting and useful 
properties, which can be verified directly, that I listed under (i), 
(ii), (iii), and (iv) above.

If you make the substitution x = u, then 

(i)  All the terms in class (1) have u^3 = u^6 = etc = u^99 = 1.  
The sum of these terms is equal to A.

(ii)  All the terms in class (2) have u = u^4 = u^7 = etc = u^100.  
The sum of these terms is B times u.

(iii)  All the terms in class (3) have u^2 = u^5 = etc = u^98.  
The sum of these terms is C times u^2.  Since u^2 = v, we write this 
as C times v.

Now, u + 0.5 = Sqrt(-3)/2.  This means that:

A + Bu + Cv = (Sqrt(-3)/2)^100 = (-3)^50/2^100 = 3^50/2^100. 

If you make the substitution x = v, then 

  (i)  All the terms in class (1) have v^3 = v^6 = etc = v^99 = 1.  
The sum of these terms is again equal to A.

 (ii)  All the terms in class (2) have v = v^4 = v^7 = etc = v^100.  
The sum of these terms is B times v.

(iii)  All the terms in class (3) have v^2 = v^5 = etc = v^98.  The 
sum of these terms is C times v^2.  Since v^2 = u, we write this as C 
times u.

Now, v + 0.5 = -Sqrt(-3)/2. This means that:

A + Bv + Cu = (-Sqrt(-3)/2)^100 = 3^50/2^100 again. 

Let's make a summary:

A + B  + C  = 3^100/2^100
A + Bu + Cv = 3^50/2^100
A + Bv + Cu = 3^50/2^100

Of course, you can solve for A, B, C, by systematic elimination.  
However, property (iv) listed above above helps to get the value of A 
immediately.  Namely, if you add up these three equations, you get:

3A = (3^100+3^50+3^50)/2^100 = (3^100 + 2 times 3^50)/2^100.

Dividing by 3, we finally obtain:

A = (3^99 + 2 times 3^49)/2^100.

This is a precise expression.  To get a rough idea of how big this
number is, note that the second term (2 times 3^49/2^100) is 
negligibly small.  This means that A is approximately: 

3^99/2^100  or 1.3552 times 10^17.

-Doctor Yiu,  The Math Forum
 Check out our web site!