# 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).$$

• Can you say a few things about what led you to this question? Commented Aug 18, 2020 at 12:23
• 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. Commented Aug 18, 2020 at 12:57

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

• Thanks for your nice solution！ Commented Aug 19, 2020 at 0:03
• 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 Commented Aug 19, 2020 at 7:51