# Largest coefficient in the power of a polynomial

How do I find the largest coefficient of any power of $$x$$ in an expansion such as $$(1 + 2x + 2x^2)^n$$, as a function of $$n$$?

In the case $$(1+x)^n$$, we know that the central coefficients are the largest, and for $$(1+ax)^n$$ I can take ratios of consecutive terms to find the largest one, but these methods fail in the case mentioned above.

Also, can we find the degree of the term for which this largest coefficient occurs, again as a function of $$n$$?

• For the example you have given try $((1+x)^2+x^2)^n$ from which you can compute the coefficients. – Mark Bennet Dec 30 '18 at 19:42

1. Write

$$\left(\frac{1}{5} + \frac{2x}{5} + \frac{2x^2}{5}\right)^n = \sum_{l=0}^{2n} a_lx^l.$$

1. Let $$x_1,x_2,\ldots, x_n$$ be iids where each $$x_i$$ is 0 with probability $$\frac{1}{5}$$; 1 with probability $$\frac{2}{5}$$; and 2 with probability $$\frac{2}{5}$$. Then for each $$l$$, note the following:

$${\bf{P}}\left[\left(\sum_{i=1}^n x_i \right) = l \right] = a_l$$

1. It turns out that (Chernoff bounds) that the value of $$l$$ that maximizes $$a_l={\bf{P}}\left[\left(\sum_{i=1}^n x_i \right) = l \right]$$ is $$l \approx {\bf{E}}\left[\sum_{i=1}^n x_i \right]$$ which is $$l \approx \frac{6n}{5}$$.

2. So putting the above together, writing $$\left(\frac{1}{5} + \frac{2x}{5} + \frac{2x^2}{5}\right)^n$$ as $$\sum_{l=0}^{2n} a_lx^l$$, the value of $$a_l$$ such that $$a_l$$ is the largest is $$l \approx \frac{6n}{5}$$ and for such $$l$$, the coefficient $$a_l$$ has value $$\theta \left(\frac{1}{\sqrt{n}}\right)$$.

3. So writing

$$(1+2x+2x^2) = \sum_{l=0}^{2n} b_lx^l,$$

the value of $$l$$ that maximzes $$b_l$$ is $$l\approx \frac{6n}{5}$$, and $$b_l$$ has value $$\theta(\frac{5^n}{\sqrt{n}})$$.

For something like $$(1+2x+2x^2)^n$$, you can say that the expected power of $$x$$ for each factor is $$\frac 65$$, so you would expect the maximum to be at $$\frac 65n$$. For $$n=100$$ this would be the $$x^{120}$$ term and it truly is per Alpha. You have to click more terms a bunch to see this. It is basically using the normal approximation to the binomial distribution.

• Thank you for your answer. I went and used Python to plot out the dependence on $n$ of the index of the largest coefficient, and it indeed is linear with the exact coefficient that you calculated. In fact, the pattern holds for other polynomials too. I will try to come up with a formal proof using the central limit theorem. – Sagnik Bhattacharya Dec 31 '18 at 16:16
• For small powers the pattern can be different. $(1+x+x^8)^n$ has an expected power of $3$, but for small powers the maximum coefficient will be about $\frac n2$. As $n$ gets larger the $3n$ will take over. Also there can be missing powers, like if you have $(1+x^3)^n$ will only have powers that are multiples of $3$. – Ross Millikan Dec 31 '18 at 16:55
• It should be $l=7n/5$ (and not $l=6n/5$) though, and I am not sure what you mean by "expected power of $x$"; I would rather the reasoning be fleshed out more. – Mike Dec 31 '18 at 18:49
• My mistake, it should be $l=\frac{6n}{5}$ just as you said. But it still would be nice to see the reasoning fleshed out wrong. – Mike Dec 31 '18 at 18:58
• *fleshed out more – Mike Jan 1 at 0:05