# Find all the values of a so that $3^{ \lfloor \frac{n-1}{2} \rfloor }\mid P_n{(a^3)}$ given the definition of $P_n$

Consider the polynomial $$P_n{(x)} = \binom{n}{2}+\binom{n}{5}x + \cdots \binom{n}{3k+2}x^{k}$$, where $$n \ge 2$$, $$k= \lfloor \frac{n-2}{3} \rfloor$$,

$$(1)$$ Show that $$P_{n+3}{(x)}=3P_{n+2}{(x)}-3P_{n+1}{(x)}+(x+1)P_n{(x)}$$,

$$(2)$$ Find all integers $$a$$ such that $$3^{ \lfloor \frac{n-1}{2} \rfloor } \mid P_n{(a^3)}$$.

The first question is easy. Notice the following transformation:

With $$\binom{n-1}{k}= \frac{(n-1)!}{k!(n-k-1)!}$$ and $$\binom{n-2}{k}= \frac{(n-2)!}{k!(n-k-2)!}$$, we have $$\binom{n-1}{k}-\binom{n-2}{k}=\binom{n-2}{k-1}$$.

The second question is harder, one may need to use the result from the first part.

I have attempted up to $$n=10$$, and for all of them, $$a \equiv 2$$ (mod 3) is sufficient. However the case $$n=11$$ was too large to test.

I wonder if $$a$$ should satisfy any other condition.

Any help is appreciated.

• I upvoted; interesting problem, good work shown, nicely presented. I'm too lazy to attack it myself; it sounds like (and this might easily be wrong) the answer is something like $a$ will satisfy the condition $\Leftrightarrow a \equiv 2 \pmod{3}.$ Assuming that that conjecture (or something like it) is correct, you have already done most of the initial legwork. As a preliminary step, you would also want to manually check that small values of $a$ that are not $\equiv 2 \pmod{3}$ don't satisfy the requirement (unclear: you may have already done this). ...see next comment Aug 15, 2020 at 7:01
• You normally have two choices re proving your conjecture: (1) induction or (2) [elegant] algebraic manipulation. I would invest 30 minutes re (1), then [if needed], 30-60 minutes re (2), then if needed 30-60 more minutes re (1). If then still no joy, edit your query with something like Addendum - method 1 and Addendum - method 2 and show all of your induction/algebraic attempts in the addendums. At this point, there is a good chance that someone at mathSE will either get you over the top or question whether your conjecture is accurate. Aug 15, 2020 at 7:05

Actually, $$a \equiv 2 \pmod{3}$$ is both sufficient and necessary. You have $$2^3 \equiv 5^3 \equiv 8^3 \equiv 8 \pmod{9}$$, so $$a \equiv 2 \pmod{3} \implies a^3 \equiv 8 \pmod{9}$$. You can also see this by having $$a = 3i + 2$$ so $$a^3 = (3i + 2)^3 = 27i^3 + 54i^2 + 36i + 8 = 9(3i^3 + 6i^2 + 4i) + 8$$. This means with $$x = a^3$$, for some integer $$k$$, we have

$$x + 1 = a^3 + 1 = 9k \tag{1}\label{eq1A}$$

Next, use strong induction to show, for all $$n \ge 2$$ that

$$P_{n}(a^3) = 3^{\lfloor(n-1)/2\rfloor}y_n \tag{2}\label{eq2A}$$

for some integers $$y_n$$. Note $$P_2(x) = \binom{2}{2} = 1 = 3^0(1)$$, $$P_3(x) = \binom{3}{2} = 3 = 3^1(1)$$ and $$P_4(x) = \binom{4}{2} = 6 = 3^1(2)$$, so \eqref{eq2A} holds for all of these base cases. Next, assume \eqref{eq2A} holds for all $$2 \le n \le m$$ for some $$m \ge 4$$. With $$n = m + 1$$, we have from \eqref{eq1A}, \eqref{eq2A} and your part ($$1$$) recursion

$$P_{m+1}(a^3) = 3\left(3^{\lfloor(m-1)/2\rfloor}y_{m}\right) - 3\left(3^{\lfloor(m-2)/2\rfloor}y_{m-1}\right) + 9k\left(3^{\lfloor(m-3)/2\rfloor}y_{m-2}\right) \tag{3}\label{eq3A}$$

First, consider the case where $$m + 1$$ is even, so $$m$$ is odd. Then \eqref{eq3A} becomes

\begin{aligned} P_{m+1}(a^3) & = 3\left(3^{(m-1)/2}y_{m}\right) - 3\left(3^{(m-3)/2}y_{m-1}\right) + 9k\left(3^{(m-3)/2}y_{m-2}\right) \\ & = 3^{(m+1)/2}y_{m} - 3^{(m-1)/2}y_{m-1} + k\left(3^{(m+1)/2}y_{m-2}\right) \\ & = 3^{(m-1)/2}\left(3y_{m} - y_{m-1} + 3ky_{m-2}\right) \\ & = 3^{(m-1)/2}y_{m+1} \end{aligned}\tag{4}\label{eq4A}

Since $$\left\lfloor\frac{(m+1)-1}{2}\right\rfloor = \frac{m-1}{2}$$, this shows \eqref{eq2A} holds. Next, consider the case where $$m + 1$$ is odd, so $$m$$ is even. Then \eqref{eq3A} becomes

\begin{aligned} P_{m+1}(a^3) & = 3\left(3^{(m-2)/2}y_{m}\right) - 3\left(3^{(m-2)/2}y_{m-1}\right) + 9k\left(3^{(m-4)/2}y_{m-2}\right) \\ & = 3^{m/2}y_{m} - 3^{m/2}y_{m-1} + k\left(3^{m/2}y_{m-2}\right) \\ & = 3^{m/2}\left(y_{m} - y_{m-1} + ky_{m-2}\right) \\ & = 3^{m/2}y_{m+1} \end{aligned}\tag{5}\label{eq5A}

Since $$\left\lfloor\frac{(m+1)-1}{2}\right\rfloor = \frac{m}{2}$$, this shows \eqref{eq2A} holds in this case as well. As both even & odd cases have been handled, this shows that \eqref{eq2A} holds in all cases, which means that

$$3^{\lfloor(n-1)/2\rfloor} \mid P_n(a^3) \tag{6}\label{eq6A}$$

Note \eqref{eq6A} means $$3^2 = 9 \mid P_5(a^3)$$. For $$a \equiv 0 \pmod{3} \implies a^3 \equiv 0 \pmod{9}$$, so we get

\begin{aligned} P_5(a^3) & \equiv 3(6) - 3(3) + (1)(1) \pmod{9} \\ & \equiv 1 \pmod{9} \end{aligned}\tag{7}\label{eq7A}

For $$a \equiv 1 \pmod{3}$$, we have $$a^3 \equiv 1 \pmod{9} \implies x + 1 = a^3 + 1 \equiv 2 \pmod{3}$$. Since the first $$2$$ terms in the first line of \eqref{eq7A} are multiples of $$3$$, this shows that $$P_5(a^3) \equiv 2 \pmod{3}$$.

This confirms that only $$a \equiv 2 \pmod{3}$$ works.