2003 Expansion

When the following expression is expanded, what will be the coefficient of x^{2003}?
\left [\left (1+x\right )\left (1+2x^3\right )\left (1+4x^9\right )\left (1+8x^{27}\right )\left (1+16x^{81}\right )\left (1+32x^{243}\right )\left (1+64x^{729}\right )\right ]^2
Source: mathcontest.olemiss.edu 7/7/2008

SOLUTION

 STEP 1 Product of two factors: \left (1+x\right )^2\left (1+2x^3\right )^2
\left (1+x\right )^2=1+2x+x^2
\left (1+2x^3\right )^2=1+4x^3+4x^6
\left (1+x\right )^2\left (1+2x^3\right )^2=\left (1+2x+x^2\right )\left (1+4x^3+4x^6\right )
=\left (1+4x^3+4x^6\right )+\left (2+8x^4+8x^7\right )+\left (x^2+4x^5+4x^8\right )
=1+2x+x^2+4x^3+8x^4+4x^5+4x^6+8x^7+4x^8.

Let a_0,a_1,a_2,\cdots,a_8 be the 9 coefficients, then we have
a_0=1; a_1=2; a_2=1; a_3=4; a_4=8; a_5=4; a_6=4; a_7=8; a_8=4.
Let A=1. The coefficients follow the pattern
A  2A  A  4A  8A  4A  4A 8A  4A.

 STEP 2 Product of three factors: \left (1+x\right )^2\left (1+2x^3\right )^2\left (1+4x^9\right )^2
\left (1+4x^9\right )^2=\mathbf{1}+\mathbf{8}x^9+\mathbf{16}x^{18}.

The product \left (1+x\right )^2\left (1+2x^3\right )^2\left (1+4x^9\right )^2 is expanded as follows:
=\left (\mathbf{1}+\mathbf{8}x^9+\mathbf{16}x^{18}\right )\left (1+2x+x^2+4x^3+8x^4+4x^5+4x^6+8x^7+4x^8\right )
\mathbf{1}\left (1+2x+x^2+4x^3+8x^4+4x^5+4x^6+8x^7+4x^8\right )+\mathbf{8}\left (1+2x+x^2+4x^3+8x^4+4x^5+4x^6+8x^7+4x^8\right )+\mathbf{16} \left (1+2x+x^2+4x^3+8x^4+4x^5+4x^6+8x^7+4x^8\right )
=1+2x+x^2+4x^3+8x^4+4x^5+4x^6+8x^7+4x^8
+8x^9+16x^{10}+8x^{11}+32x^{12}+64x^{13}+32x^{14}+32x^{15}+64x^{16}+32x^{17}
+16x^{18}+32x^{19}+16x^{20}+64x^{21}+128x^{22}+64x^{23}+64x^{24}+128x^{25}+64x^{26}.

The 27 coefficients follow the pattern
a_0\to a_8=1\;2\;1\;4\;8\;4\;4\;8\;4=\mathbf{1}\left (1\;2\;1\;4\;8\;4\;4\;8\;4\right )=1\left (a_0\to a_8\right )
a_9\to a_{17}=8\;16\;8\;32\;64\;32\;32\;64\;32=\mathbf{8}\left (1\;2\;1\;4\;8\;4\;4\;8\;4\right )=8 \left (a_0\to a_8\right )
a_{18}\to a_{26}=16\;32\;16\;64\;128\;64\;64\;128\;64=\mathbf{16}\left (1\;2\;1\;4\;8\;4\;4\;8\;4\right )=16 \left (a_0\to a_8\right )

STEP 3 Product of four factors: \left (1+x\right )^2\left (1+2x^3\right )^2\left (1+4x^{9}\right )^2\left (1+8x^{27}\right )^2
\left (1+8x^{27}\right )^2=\mathbf{1}+\mathbf{16}x^{27}+\mathbf{64}x^{54}

The product \left (1+x\right )^2\left (1+2x^3\right )^2\left (1+4x^9\right )^2\left (1+8x^{27}\right )^2 generates 81 coefficients and is too long to expand here. So, we will represent them in 3 groups of 27 each as follows:
a_0\to a_{26}=\mathbf{1}\left (a_0\to a_{26}\right )
a_{27}\to a_{53}=\mathbf{16}\left (a_0\to a_{26}\right )
a_{54}\to a_{80}=\mathbf{64}\left (a_0\to a_{26}\right )
 

STEP 4 Try solving a simpler problem: What is the value of a_{35}?
Since a_{35} belongs to the group a_{27}\to a_{53}=\mathbf{16}\left (a_0\to a_{26}\right ), we write
a_{35}=\mathbf{16}\left (a_{x}\right ) where a_{x} is the coefficient in a_0\to a_{26} that corresponds to a_{35}.
Given that a_{27} corresponds to a_0, x=35-27=8.
Thus, a_{35}=16\left (a_8\right )=16\left (4\right )=64.

STEP 5
Try solving another simpler problem: What is the value of a_{203}?
Since the previous product produces only 81 coefficients a_0\to a_{80}, we need to go further to find the value of a_{203}. We need to find the product of five factors \left (1+x\right )^2\left (1+2x^3\right )^2\left (1+4x^9\right )^2\left (1+x^{27}\right )^2\left (1+16x^{81}\right )^2 which will produce 3\times 81=243 coefficients a_0\to a_{242}.The new factor is
\left (1+16x^{81}\right )^2=\mathbf{1}+\mathbf{32}x^{81}+\mathbf{256}x^{162}
.
Again, we divide the 243 coefficients into 3 groups of 81 each as follows.
a_0\to a_{80}=\mathbf{1}\left (a_0\to a_{80}\right )
a_{81}\to a_{161}=\mathbf{32}\left (a_0\to a_{80}\right )

a_{162}\to a_{242}=\mathbf{256}\left (a_0\to a_{80}\right )

Since a_{203} belongs to the group a_{162}\to a_{242}=\mathbf{256}\left (a_0\to a_{80}\right ), we write
a_{203}=\mathbf{256}\left (a_{y}\right )
where a_{y} is the coefficient in a_0\to a_{80} that corresponds to a_{203}.
Given that a_{162} corresponds to a_0, \: y=203-162=41.
Thus, a_{203}=256\left (a_{41}\right ).

We need to go back to STEP 3 to find the value of a_{41}.
Remember in STEP 3 we found 81 coefficients a_0\to a_{80} arranged as follows:
a_0\to a_{26}=\mathbf{1}\left (a_0\to a_{26}\right )

a_{27}\to a_{53}=\mathbf{16}\left (a_0\to a_{26}\right )

a_{54}\to a_{80}=\mathbf{64}\left (a_0\to a_{26}\right )
Since a_{41} belongs to the group a_{27}\to a_{53}=\mathbf{16}\left (a_0\to a_{26}\right ), we write
a_{41}=\mathbf{16}\left (a_{z}\right )
where a_{z} is the coefficient in a_0\to a_{26} that corresponds to a_{41}.
Given that a_{27} corresponds to a_0,\:z=41-27=14 .
Thus, a_{41}=16\left (a_{14}\right ).
But, how much is a_{14}?
From STEP 2, a_{14}=32.
So, a_{41}=16\left (a_{14}\right )=16\left (32\right )=512.
Finally, a_{203}=256\left (a_{41}\right )=256\left (512\right )=131072.

STEP 6 What is the value of a_{2003}?
Now we are ready to tackle the big problem of finding the value of a_{2003}.
The product of 7 factors generates 3^7=2187 coefficients . The seventh factor is
\left (1+64x^{729}\right )^2=\mathbf{1}+\mathbf{128}x^{729}+\mathbf{4096}x^{1458}.
We arrange a_0\to a_{2186} in 3 groups of 729 each as follows:
a_0\to a_{728}=\mathbf{1}\left (a_0\to a_{728}\right )
a_{729}\to a_{1457}=\mathbf{128}\left (a_0\to a_{728}\right )
a_{1458}\to a_{2186}=\mathbf{4096}\left (a_0\to a_{728}\right )

Since a_{2003} belongs to the third group a_{1458}\to a_{2186}=\mathbf{4096}\left (a_0\to a_{728}\right ) and a_{2003} corresponds to a_{\left (2003-1458\right )}=a_{545} , we write
a_{2003}=\mathbf{4096}\left (a_{545}\right ).

The product of 6 factors generates 3^6=729 coefficients . The sixth factor is
\left (1+32x^{243}\right )^2=\mathbf{1}+\mathbf{64}x^{243}+\mathbf{1024}x^{486}.
We arrange a_0\to a_{728} in 3 groups of 243 each as follows:
a_0\to a_{242}=\mathbf{1}\left (a_0\to a_{242}\right )
a_{243}\to a_{485}=\mathbf{64}\left (a_0\to a_{242}\right )
a_{486}\to a_{728}=\mathbf{1024}\left (a_0\to a_{242}\right )
The above arrangement tells us that a_{545}=\mathbf{1024}\left (a_{\left (545-486\right )}\right )=1024\left (a_{59}\right ).
From STEP 5, we have
a_{54}\to a_{80}=\mathbf{64}\left (a_0\to a_{26}\right )
Thus, a_{59}=64\left (a_5\right ).

Now, we can put everything together one calculation at a time.
a_{59}=64\left (4\right )=256
a_{545}=1024\left (a_{59}\right )=1024\left (256\right )=262144
a_{2003}=4096\left (a_{545}\right )=4096\left (262144\right )=1073741824.

Answer: 1073741824.

Advertisements

About mvtrinh

Retired high school math teacher.
This entry was posted in Problem solving and tagged , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s