## 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$.