3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$ Aug 15, 2020 at 7:01
  • $\begingroup$ 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. $\endgroup$ Aug 15, 2020 at 7:05

1 Answer 1

2
$\begingroup$

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{equation}\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}\end{equation}\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{equation}\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}\end{equation}\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{equation}\begin{aligned} P_5(a^3) & \equiv 3(6) - 3(3) + (1)(1) \pmod{9} \\ & \equiv 1 \pmod{9} \end{aligned}\end{equation}\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.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .