# Homework Help: Find the coefficient of the 1996th term of a product

1. Jan 9, 2017

### QuietMind

1. The problem statement, all variables and given/known data
Let $\prod_{n=0}^{1996} (1 + nx^{3^n}) = 1 + a_1 x^{k_1} + a_2 x^{k_2} + ... + a_m x^{k^m}$ ,
where $a_1, a_2, ..., a_m$ are nonzero and $k_1 < k_2 < ... < k_m$. Find $a_{1996}$.
From Art and Craft of Problem Solving, originally from Turkey, 1996
2. Relevant equations
N/A

3. The attempt at a solution
I think I have a solution, but I'm having difficulty explaining myself. I would like to get an evaluation of this thought process:

I think it is relevant that powers of 3 cannot add up to equal another power of 3 and $\sum_{k=1}^{n-1} 3^k < 3^n$. This means that when the product is expanded out completely, no two terms will have the same power of x, so no simplification of terms will be possible. Because it is a binomial, this means that the number of terms when expanding out the first k products (ie expand $\prod_{n=1}^{k} (1 + nx^{3^n})$)is equal to twice the number of terms when expanding out the first k-1 products.

We don't need to completely compute out the 1996 factors, as we are essentially being asked to describe the 1996th smallest term (if we compute out all the factors we will have many more than that). These smaller terms would be obtained by taking the $nx^{k^n}$ contribution from some or all of the "smaller" terms and taking the 1 from the "larger" terms.(Because of the properties of the powers of 3 that I stated above, we don't need to consider the factors that contribute too large a power of 3, because the inclusion of their x contribution would instantly push us over the 1996th smallest term. This cutoff happens at n=11) We want to find what sum of powers of 2 would yield 1996, which is $2^{10} + 2^9 + 2^8 + 2^7 + 2^6 + 2^3 + 2^2 = 1996$.
This tells us that the 10th, 9th, 8th, 7th, 6th, 3rd and 2nd factors contribute their $nx^{3^n}$ term, while the other factors contribute their 1 (so are essentially ignored). The coefficient is then $10*9*8*7*6*3*2 = 181440$.

Does this seem correct, or can I clarify any steps that are not sufficiently explained? I'm still in the process of learning how to write thorough proofs.

Edit: LaTeX formatting

Last edited: Jan 9, 2017
2. Jan 9, 2017

### haruspex

Looks right to me. Well done.
Some of you superscripts/subscripts are a little awry.

3. Jan 9, 2017

### QuietMind

Thank you! I revised the formatting for anyone who happens to come across this later.

4. Jan 9, 2017

### haruspex

I still see a exponents km and kn that should be km and kn.