Let
$$
P\_m(x):=\begin{cases}4x+1\quad&\ \text{if}\ m=1,\\
0\quad&\ \text{if}\ m=2,\\
8x^m+(x+1)^{m-3}(2x+1)^3\quad&\ \text{if}\ m\geq3.\end{cases}
$$
How to prove that for any positive odd integer $n$, there exist integers $a\_1^{(n)},a\_2^{(n)},\ldots,a\_n^{(n)}$ such that
$$
(4x+1)^n=\sum\_{k=1}^n a\_k^{(n)}P\_k(x).
$$



Write $(4x+1)^n$ as the linear combination of certain polynomials
I enjoyed very much this question! My solution contains two ideas, each of which addresses one of two distinct subproblems:


1. show that the coefficients $a\_m^{(n)}$ are **integers**;
2. show that the coefficients $a\_m^{(n)}$ **exist**.


The subproblem (1) is not completely obvious because the polynomials $P\_m$ are not monic.
However we are lucky here! The simple idea here is to renormalize the variable as $x=y/4$ and clear the denominators appropriately, noticing that there is a fortunate 2-adic coincidence that makes this approach work.


The subproblem (2) is not obvious and quite annoying because $P\_0=P\_2=0$. In other words, there is no nonzero $P\_m$ of degree $0$ and $2$, so a priori the linear elimination may leave us with a remainder of degree at most 2. The idea to go here is more hidden (and nicer!). It starts by essentially rewriting the problem as
$$
(4x+1)^n = 8x^3 A(x) + (2x+1)^3 A(x+1)
$$
and finding some hidden symmetry. It may even be the case that this observation may be useful to find the coefficients $a\_m^{(n)}$ explicitly.




---


So, let's start the proof. After the change of variable $x=y/4$ the polynomial $(4x+1)^n$ becomes $(y+1)^n$, which has integer coefficients in the variable $y$.


Instead the polynomials $P\_m(x)$ for $m\geq 3$ become:


$$
P\_m(y/4) = \frac 8 {4^m} y ^m + \left(\frac{y+4} 4 \right)^{m-3} \left(\frac{y+2} 2 \right)^3.
$$


Now it is tempting to multiply over by $4^m/8$ to clear all the denominators, but instead we will multiply by $4^{m-2}$, that is, one less factor of 2 than the greedy one.


So, for $m\geq 3$ define $Q\_m(y):=4^{m-2} P\_m(y/4)$ and we compute that


$$ 
Q\_m(y) = \frac 1 2 y^m + (y+4)^{m-3}\frac{(y+2)^3} 2
$$


Now, you should note, expanding the binomials and the products, that all the terms $y^k$ with $k<m$ get multiplied by some positive power of 2 or 4, before being divided by the second 2 at denominator. Therefore they are all integers.
Moreover the leading coefficient of $Q\_m$ (the one multiplying $y^m$) is equal to $1/2 + 1/2=1$ (here is the fortunate 2-adic coincidence). Summing up, we have:


**Lemma 1** *For all $m\geq 3$ we have that $Q\_m(y)$ is a monic polynomial in $y$ with integer coefficients and degree $m$.*


We conclude the following:


**Corollary 1** *For all $n$ there exist (unique!) integers $b\_m^{(n)}$ such that*


$$
(y+1)^n = \sum\_{m=3}^n b\_m^{(n)} Q\_m(y) + R(y)
$$


*for some polynomial $R(y)$ with integer coefficients of degree at most 2.*


Note that up to now we did not use any information on the given polynomial $(y+1)^n$. Note also that if only we could prove that $R(y)$ is a multiple of $P\_1(y/4)=y+1$ , which we ignored so far, that would finish the proof.


To prove this, I came up with the following argument. First note that
$$
Q\_m(y) = \frac {y^3} 2 y^{m-3} + \frac {(y+2)^3} 2 (y+4)^{m-3},
$$
so the linear combination of $Q\_m$ can be written as
$$
\sum\_{m=3}^n b\_m^{(n)} Q\_m(y) = \frac {y^3} 2 S(y) + \frac {(y+2)^3} 2 S(y+4),
$$
where $S$ is the polynomial of degree at most $n-3$ given by
$$
S(y) :=\sum\_{m=3}^n b\_m^{(n)} y^{m-3}.
$$


It is convenient (to "increase the symmetry") to write $S(y)=T(y-1)$ for some other polynomial $T$ of the same degree. Then we will again change variable $z=y+1$, so the polynomial equation in Corollary 1 reads as follows:


$$
z^n = \frac {(z-1)^3} 2 T(z-2) + \frac {(z+1)^3} 2 T(z+2) + R(z-1). 
$$


Since $T$ is a polynomial of degree at most $n-3$, we have that $z^n-R(z-1)$ is equal to a linear combination of terms of the form
$$
F\_m(z) = \frac {(z-1)^3} 2 (z-2)^{m-3} + \frac {(z+1)^3} 2 (z+2)^{m-3} 
$$
for $3\leq m\leq n$.


We now exploit the symmetry! We note that $F\_m(z)$ is a monic polynomial (with integer coefficients, but we don't need it here) of degree $m$ which satisfy the odd/even equation:
$$
F\_m(-z) = (-1)^m F\_m(z).
$$
Therefore, $F\_m(z)$ either has only monomials of odd degree, or only monomials of even degree.
Write
$$
z^n-R(z-1) = \sum\_{m=3}^n c\_m^{(n)} F\_m(z). 
$$
We are going to prove that $c\_m^{(n)}=0$ for all even $m$. Suppose the contrary, and let $M$ be the largest even number $3\leq M\leq n$ such that $c\_M^{(n)}\neq 0$. By what we said before (each $F\_m$ is monic of degree $m$ and odd/even) we see that only $c\_m^{(n)}F\_m(z)$ with $m=M$ contributes a nonzero multiple of the monomial $z^M$. Therefore $c\_M^{(n)}z^M$ appears as the unique monomial of degree $M$ in the power expansion of the polynomial $z^n-R(z-1)$. However, $n$ is *odd* by assumption (in the question) and $R(z-1)$ has degree at most 2 by construction.
Therefore $z^n-R(z-1)$ does not contain any term of degree $M$; that's a contradiction. This shows that only $F\_m$ with odd $m$ appear in the expansion in display above. Summing up:


**Lemma 2** *Let $R$ be as in Lemma 1. Then $z^n-R(z-1)$ is an odd polynomial function.*


Since $z^n$ itself is odd, we get that $R(z-1)$ is odd. Since $R$ is a polynomial of degree at most 2, it can be odd only if it is a scalar multiple of the linear monomial $z$. We conclude


**Corollary 2** *$R(y)=b\_1^{(n)} (y+1)$ for some scalar $b\_1^{(n)}$. (a fortiori, $b\_1^{(n)}\in\mathbb Z$)*




---


From Corollary 1 and Corollary 2 we get the wanted solution, with $a\_1^{(n)}=b\_1^{(n)}$ and $a\_m^{(n)}= 4^{m-2}b\_m^{(n)}$ for all $m\geq 3$.


