Let $$ P_m(x):=\begin{cases}4x+1\quad&\ \text{if}\ m=1,\\ 0\quad&\ \text{if}\ m=2,\\ 8x^m+(x+1)^{m3}(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). $$

3$\begingroup$ Can you say a few things about what led you to this question? $\endgroup$– Liviu NicolaescuCommented Aug 18, 2020 at 12:23

4$\begingroup$ I need to reduce the sum $\sum_{k=0}^n(4k+1)^{2l+1}A_k$, where $A_k$ are usually some hypergeometric terms. I have found the closed forms of $\sum_{k=0}^nP_n(k)A_k$. Now I want to find another form of the sum $\sum_{k=0}^n(4k+1)^{2l+1}A_k$ by establishing the identity as stated in the question. $\endgroup$– C. WANGCommented Aug 18, 2020 at 12:57
1 Answer
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 2adic 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)^{m3} \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^{m2}$, that is, one less factor of 2 than the greedy one.
So, for $m\geq 3$ define $Q_m(y):=4^{m2} P_m(y/4)$ and we compute that
$$ Q_m(y) = \frac 1 2 y^m + (y+4)^{m3}\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 2adic 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^{m3} + \frac {(y+2)^3} 2 (y+4)^{m3}, $$ 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 $n3$ given by $$ S(y) :=\sum_{m=3}^n b_m^{(n)} y^{m3}. $$
It is convenient (to "increase the symmetry") to write $S(y)=T(y1)$ 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 {(z1)^3} 2 T(z2) + \frac {(z+1)^3} 2 T(z+2) + R(z1). $$
Since $T$ is a polynomial of degree at most $n3$, we have that $z^nR(z1)$ is equal to a linear combination of terms of the form $$ F_m(z) = \frac {(z1)^3} 2 (z2)^{m3} + \frac {(z+1)^3} 2 (z+2)^{m3} $$ 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^nR(z1) = \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^nR(z1)$. However, $n$ is odd by assumption (in the question) and $R(z1)$ has degree at most 2 by construction. Therefore $z^nR(z1)$ 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^nR(z1)$ is an odd polynomial function.
Since $z^n$ itself is odd, we get that $R(z1)$ 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^{m2}b_m^{(n)}$ for all $m\geq 3$.


$\begingroup$ Thanks for sharing the problem! As for explicit formulae, maybe I was too optimistic. The reformuation symmetrizes the problem but I don't have ideas that are better than writing down the recursion. Maybe some expert in binomial sums may help in recognize known recursions? Another idea is to write the coefficients b_m^n for, say, n=7 and put these numbers into OEIS. If you're lucky you may get something $\endgroup$ Commented Aug 19, 2020 at 7:51