MHB Compute $a_{1996}$ for $\prod_{k=1}^{1996} (1+kx^{3^k})$

[anemone]

Let $\displaystyle \prod_{k=1}^{1996} (1+kx^{3^k})=1+a_1x^{n_1}+a_2x^{n_2}+\cdots+a_mx^{n_m}$, where $a_1,\,a_2,\,\cdots$ are nonzero and $n_1<n_2<\cdots<n_m$.

Compute $a_{1996}$.

 

[Nono713]

Note: solution not verified, possible off-by-one error, but it definitely works.

Spoiler

We express $a_n$ as a recurrence by induction on $k$. First consider the base case $k = 1$, which gives us $a_0 = a_1 = 1$. Suppose that for some $k - 1 \in \mathbb{N}$, we have nonzero polynomial coefficients $a_0, a_1, \cdots, a_{n - 1}$ for some $n$, then it follows that:
$$(1 + k x^{3^k}) \sum_{i = 0}^{n - 1} a_i x^{n_i} = \sum_{i = 0}^{n - 1} a_i x^{n_i} + k \sum_{i = 0}^{n - 1} a_i x^{3^k + n_i}$$
We observe that $3^k$ is larger than all exponents $n_i$ which are at most $3^k - 1$, being a sum of powers of $3$ less than $k$, and so the coefficients $a_0$ to $a_{n - 1}$ remain unchanged by the multiplication by $1 + k x^{3^k}$. Furthermore, as a result the polynomial for $k$ must then have $2n$ nonzero terms (twice as many). These two facts together allows us to derive $k$ from $n$ as $k = \lceil \log_2(n + 1) \rceil$ and hence express $a_n$ as a simple recurrence:
$$a_n = k a_{n - 2^{k - 1}} ~ ~ ~ \text{where} ~ k = \lceil \log_2(n + 1) \rceil, a_0 = a_1 = 1$$
So that:
$$a_{1996} = 11 a_{1996 - 1024} = 11 a_{972}$$
$$a_{972} = 10 a_{972 - 512} = 10 a_{460}$$
$$a_{460} = 9 a_{460 - 256} = 9 a_{204}$$
$$a_{204} = 8 a_{204 - 128} = 8 a_{76}$$
$$a_{76} = 7 a_{76 - 64} = 7 a_8$$
$$a_{8} = 4 a_{8 - 8} = 4 a_0$$
And so we conclude that:
$$a_{1996} = 11 \times 10 \times 9 \times 8 \times 7 \times 4 \times a_0 = 221760$$
​

 

[Nono713]

Amended solution:

Spoiler

We express $a_n$ as a recurrence by induction on $k$. First consider the base case $k = 1$, which gives us $a_0 = a_1 = 1$. Suppose that for some $k - 1 \in \mathbb{N}$, we have nonzero polynomial coefficients $a_0, a_1, \cdots, a_{n - 1}$ for some $n$, then it follows that:
$$(1 + k x^{3^k}) \sum_{i = 0}^{n - 1} a_i x^{n_i} = \sum_{i = 0}^{n - 1} a_i x^{n_i} + k \sum_{i = 0}^{n - 1} a_i x^{3^k + n_i}$$
We observe that $3^k$ is larger than all exponents $n_i$ which are at most $3^k - 1$, being a sum of powers of $3$ less than $k$, and so the coefficients $a_0$ to $a_{n - 1}$ remain unchanged by the multiplication by $1 + k x^{3^k}$. Furthermore, as a result the polynomial for $k$ must then have $2n$ nonzero terms (twice as many). These two facts together allows us to derive $k$ from $n$ as $k = \lceil \log_2(n + 1) \rceil$ and hence express $a_n$ as a simple recurrence:
$$a_n = k a_{n - 2^{k - 1}} ~ ~ ~ \text{where} ~ k = \lceil \log_2(n + 1) \rceil, a_0 = a_1 = 1$$
So that:
$$a_{1996} = 11 a_{1996 - 1024} = 11 a_{972}$$
$$a_{972} = 10 a_{972 - 512} = 10 a_{460}$$
$$a_{460} = 9 a_{460 - 256} = 9 a_{204}$$
$$a_{204} = 8 a_{204 - 128} = 8 a_{76}$$
$$a_{76} = 7 a_{76 - 64} = 7 a_{12}$$
$$a_{12} = 4 a_{12 - 8} = 4 a_4$$
$$a_{4} = 3 a_{4 - 4} = 3 a_0$$
And so we conclude that:
$$a_{1996} = 11 \times 10 \times 9 \times 8 \times 7 \times 4 \times 3 \times a_0 = 665280$$
​

 

[anemone]

Amended solution:

Spoiler

We express $a_n$ as a recurrence by induction on $k$. First consider the base case $k = 1$, which gives us $a_0 = a_1 = 1$. Suppose that for some $k - 1 \in \mathbb{N}$, we have nonzero polynomial coefficients $a_0, a_1, \cdots, a_{n - 1}$ for some $n$, then it follows that:
$$(1 + k x^{3^k}) \sum_{i = 0}^{n - 1} a_i x^{n_i} = \sum_{i = 0}^{n - 1} a_i x^{n_i} + k \sum_{i = 0}^{n - 1} a_i x^{3^k + n_i}$$
We observe that $3^k$ is larger than all exponents $n_i$ which are at most $3^k - 1$, being a sum of powers of $3$ less than $k$, and so the coefficients $a_0$ to $a_{n - 1}$ remain unchanged by the multiplication by $1 + k x^{3^k}$. Furthermore, as a result the polynomial for $k$ must then have $2n$ nonzero terms (twice as many). These two facts together allows us to derive $k$ from $n$ as $k = \lceil \log_2(n + 1) \rceil$ and hence express $a_n$ as a simple recurrence:
$$a_n = k a_{n - 2^{k - 1}} ~ ~ ~ \text{where} ~ k = \lceil \log_2(n + 1) \rceil, a_0 = a_1 = 1$$
So that:
$$a_{1996} = 11 a_{1996 - 1024} = 11 a_{972}$$
$$a_{972} = 10 a_{972 - 512} = 10 a_{460}$$
$$a_{460} = 9 a_{460 - 256} = 9 a_{204}$$
$$a_{204} = 8 a_{204 - 128} = 8 a_{76}$$
$$a_{76} = 7 a_{76 - 64} = 7 a_{12}$$
$$a_{12} = 4 a_{12 - 8} = 4 a_4$$
$$a_{4} = 3 a_{4 - 4} = 3 a_0$$
And so we conclude that:
$$a_{1996} = 11 \times 10 \times 9 \times 8 \times 7 \times 4 \times 3 \times a_0 = 665280$$
​

Thanks for participating, Bacterius! Yes, your amended solution is correct and the subtraction error was spotted by Opalg and so I want to thank Opalg because he has helped me numerous times in the past even if he was busy at the time.