Write $(4x+1)^n$ as the linear combination of certain polynomials 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).
$$
 A: I enjoyed very much this question! My solution contains two ideas, each of which addresses one of two distinct subproblems:

*

*show that the coefficients $a_m^{(n)}$ are integers;

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