number theory of coefficients in an infinite sequence of polynomials

Question

EDIT: equivalent formulation by Hurkyl in comments: if $n$ is odd and $p^\nu \parallel n$ and $n > 2k,$ then $$ p^{(\nu + 2 + 2 k - n)} \; | \; \sum_j \left( \begin{array}{c} n \\ 2j \end{array} \right) \left( \begin{array}{c} j \\ k \end{array} \right), $$ where the sum should be $k \leq j \leq (n-1)/2.$ Evidently one can expand this sum in some useful way...Hope I got this all arranged correctly. For $n-2k=1,$ the binomial coefficient sum is just $n$ itself. Hurkyl already did $n-2k=3,$ the sum is $n(n+1)(n-1)/6,$ so it works, and you only reach equality if the prime under consideration is $3.$ After an initial bunch of errors, I did $n-2k=5,$ the sum is $n(n+1)(n-1)(n+3)(n-3)/120,$ and it also works. This need not be an integer if $n$ is even but not divisible by $8.$ However, I am not at all worried about $n$ even for this problem.

ORIGINAL: Let me post this and then look at related questions. I do suspect that this is all known. If everything I expect is actually true, this gives an answer to Divisors of Pell Equation Solutions which seems to have just been made up as convenient for a contest training problem.

Anyway, take the sequence of polynomials in one variable $$ 1, \; x, \; 2 x^2 - 1, \; 4 x^3 - 3 x, \; 8 x^4 - 8 x^2 + 1, \; 16 x^5 - 20 x^3 + 5 x,$$ $$ 32 x^6 - 48 x^4 + 18 x^2 - 1, \; 64 x^7 - 112 x^5 + 56 x^3 - 7 x, $$ $$128 x^8 - 256 x^6 + 160 x^4 - 32 x^2 + 1, \; 256 x^9 - 576 x^7 + 432 x^5 - 120 x^3 + 9 x, $$ $$ 512 x^{10} - 1280 x^8 + 1120 x^6 - 400 x^4 + 50 x^2 - 1, $$ $$ 1024 x^{11} - 2816 x^9 + 2816 x^7 - 1232 x^5 + 220 x^3 - 11 x, $$ $$ 2048 x^{12} - 6144 x^{10} + 6912 x^8 - 3584 x^6 + 840 x^4 - 72 x^2 + 1,$$ $$ 4096 x^{13} - 13312 x^{11} + 16640 x^9 - 9984 x^7 + 2912 x^5 - 364 x^3 + 13 x, $$ $$ 8192 x^{14} - 28672 x^{12} + 39424 x^{10} - 26880 x^8 + 9408 x^6 - 1568 x^4 + 98 x^2 - 1,$$ $$ 16384 x^{15} - 61440 x^{13} + 92160 x^{11} - 70400 x^9 + 28800 x^7 - 6048 x^5 + 560 x^3 - 15 x, $$ $$ 32768 x^{16} - 131072 x^{14} + 212992 x^{12} - 180224 x^{10} + 84480 x^8 - 21504 x^6 + 2688 x^4 - 128 x^2 + 1, $$ $$ 65536 x^{17} - 278528 x^{15} + 487424 x^{13} - 452608 x^{11} + 239360 x^9 - 71808 x^7 + 11424 x^5 - 816 x^3 + 17 x, \ldots $$ If we call these $f_n,$ we have $f_0 = 1, f_1 = x, f_2 = 2 x^2 - 1,$ and $$ f_{n+2} = 2 x f_{n+1} - f_n. $$ It would not be at all surprising if these had a name. Maybe that is why people are always asking for names of things on MSE, so that they can look up the names online...

Anyway, if $n$ is odd, then the final term is $\pm n x.$ Conjectures are like this: for an odd prime $p,$ if $p^2 | n,$ then $p$ divides the cubic coefficient $a_3.$ If $p^3| n,$ then $p^2$ divides $a_3.$ If $p^4| n,$ then $p^3$ divides $a_3$ and $p$ divides $a_5.$ If $p^5| n,$ then $p^4$ divides $a_3$ and $p^2$ divides $a_5.$ If $p^6| n,$ then $p^5$ divides $a_3$ and $p^3$ divides $a_5$ and $p$ divides $a_7.$

Let's see; Question: Anyone know anything about this?

Answer 1

From Hurkyl's formulation, it appears that, with $n$ odd $j$ odd and $a_j$ the absolute value of the coefficient of $x^j,$ we have $$ a_1 = n, $$ $$ a_3 = \frac{n(n^2-1)}{6}, $$ $$ a_5 = \frac{n(n^2-1)(n^2 - 9)}{120}, $$ $$ a_7 = \frac{n(n^2-1)(n^2 - 9)(n^2 - 25)}{5040}, $$ $$ a_9 = \frac{n(n^2-1)(n^2 - 9)(n^2 - 25)(n^2 - 49)}{362880}, $$ $$ a_{11} = \frac{n(n^2-1)(n^2 - 9)(n^2 - 25)(n^2 - 49)(n^2 - 81)}{39916800}, $$ $$ a_{13} = \frac{n(n^2-1)(n^2 - 9)(n^2 - 25)(n^2 - 49)(n^2 - 81)(n^2 - 121)}{6227020800}, $$ where the denominator in $a_j$ is just $j!$

And so on. My brain is a little fried right now, But the presence of the $n$ factor suggests to me that the prime factoring thing is looking good. Some of the loss due to $j!$ will be offset by the $(n^2 - w^2)$ factors...

Answer 2

Now that I'm awake and have time, I'll collect my comments into an answer.

I can't say I've seen this specific recurrence before, but we can solve the difference equation by various standard means. The second simplest is to already know that, unless there is a redundancy, all solutions to recurrences of this sort are linear combinations of $2$ basis solutions $\alpha^n$; plugging this in gives a quadratic equation we can solve for two possible values $\alpha$. Then we can take a linear combination of these two solutions to satisfy the initial condition.

If you didn't already know this, you could set up a matrix equation

$$ \left( \begin{matrix} f_{n+1} \\ f_{n+2} \end{matrix} \right) = \left(\begin{matrix} 0 & 1 \\ -1 & 2x \end{matrix} \right) \left( \begin{matrix} f_n \\ f_{n+1} \end{matrix} \right) = \ldots = \left(\begin{matrix} 0 & 1 \\ -1 & 2x \end{matrix} \right)^{n+1} \left( \begin{matrix} f_0 \\ f_1 \end{matrix} \right) $$

and diagonalizing the matrix lets us compute its power easily.

The easiest solution is to simply ask wolfram alpha. Ultimately, we get the solution

$$ f_n(x) = \frac{1}{2} \left( \left( x + \sqrt{x^2 - 1} \right)^n + \left( x - \sqrt{x^2 - 1} \right)^n \right) $$

---

Boldly charging forward with hopes we'll get someplace useful, we can expand this using the binomial theorem. To save a bit of work, note that all of the odd powers of $\sqrt{x^2 - 1}$ will cancel out, so we have

$$ \begin{align} f_n(x) &= \sum_i \binom{n}{2i} (x^2 - 1)^i x^{n-2i} \\&= \sum_i \binom{n}{2i} \left(\sum_j \binom{i}{j} x^{2(i-j)} (-1)^{j} \right) x^{n-2i} \\&= \sum_j (-1)^{j}\left( \sum_i \binom{n}{2i} \binom{i}{j} \right) x^{n-2j} \end{align} $$

I don't know how to sum that inner sum, but Mathematica does: simplifying the result gives

$$ \sum_i \binom{2m}{2i} \binom{i}{m-k} = \frac{4^k m}{m+k} \binom{m+k}{2k} $$ $$ \sum_i \binom{2m+1}{2i} \binom{i}{m-k} = \frac{4^k (2m+1)}{2k+1} \binom{m+k}{2k} $$

and so

$$ f_{2m}(x) = \sum_{k=0}^m (-1)^{m-k}\frac{4^k m}{m+k} \binom{m+k}{2k} x^{2k} $$ $$ f_{2m+1}(x) = \sum_{k=0}^m (-1)^{m-k}\frac{4^k (2m+1)}{2k+1} \binom{m+k}{2k} x^{2k+1} $$

---

But Will's formulas seem more appealing; let's rewrite those coefficients:

$$ \begin{align} \frac{4^k m}{m+k} \binom{m+k}{2k} &= \frac{4^k m \cdot (m-k+1) (m-k+2) \cdots (m+k)}{(m+k) (2k)!} \\&= \frac{2m \cdot (2m-2k+2) (2m-2k+4) \cdots (2m+2k)}{(2m+2k)(2k)!} \\&= \frac{n \cdot (n-2k+2) (n-2k+4) \cdots (n+2k)}{(n+2k)(2k)!} \\&= \frac{n \cdot (n-2k+2) (n-2k+4) \cdots (n+2k-2)}{(2k)!} \\&= \frac{1}{(2k)!} \prod_{j=0}^{k-1} \left(n^2-(2j)^2\right) \\ \frac{4^k (2m+1)}{2k+1} \binom{m+k}{2k} &= \frac{4^k (2m+1) \cdot (m-k+1) (m-k+2) \cdots (m+k)}{(2k+1) (2k)!} \\&= \frac{(2m+1) \cdot (2m-2k+2) (2m-2k+4) \cdots (2m+2k)}{(2k+1) (2k)!} \\&= \frac{n \cdot (n-2k+1) (n-2k+3) \cdots (n+2k-1)}{(2k+1)!} \\&= \frac{n}{(2k+1)!} \prod_{j=0}^{k-1}(n^2 - (2j+1)^2) \end{align} $$

Thus, in the even case,

$$ f_n(x) = \sum_{k=0}^{n/2} (-1)^{m-k} \frac{x^{2k}}{(2k)!} \prod_{j=0}^{k-1} \left(n^2-(2j)^2\right) $$

and in the odd case,

$$ f_n(x) = \sum_{k=0}^{(n-1)/2} (-1)^{m-k} \frac{x^{2k+1}}{(2k+1)!} n \prod_{j=0}^{k-1}(n^2 - (2j+1)^2) $$