# Can the coefficients of a given term in this family of power series have a common divisor?

Let $g_m(b)$ be the coefficient of $x^m$ the power series

$$\dfrac{1}{1-x-bx^2}$$

(When $b=1$, this is just the generating function of Fibonacci numbers.) Of course, $g_m(b)$ depends on both $m$ and $b$. Now fix $m$, and let $b$ run from 1 to $\infty$. Can the $g_m(b)$'s have a non-trivial common divisor for some $m$?

It seems reasonable to believe this cannot happen, but I don't see how to prove it. The relation among the $g_m(b)$'s for a fixed $b$ is simple. But for a fixed $m$, I don't see how to relate the $g_m(b)$'s.

-

No. Note that $g_m$ has constant term $1$. If all values of $g_m(b)$ have a common divisor $d$, then $d | g_m(d)$, but $g_m(d) \equiv g_m(0) = 1 \bmod d$.

Initially I wanted to resolve this problem using the following lemma, which is unnecessary. But I thought I would keep it here in case anyone was interested.

Lemma: Let $f(x)$ be a polynomial which attains integer values when $x$ is an integer. If $d$ is an integer such that $d | f(x)$ for all positive integers $x$, then $d | f(x)$ for all integers $x$.

Proof. We need to observe the following facts about the finite difference operator $\Delta f(x) = f(x + 1) - f(x)$.

1. $d | f(x)$ for all positive integers $x$ if and only if $d | f(1)$ and $d | \Delta f(x)$ for all positive integers $x$.

2. $d | f(x)$ for all integers $x$ if and only if $d | f(1)$ and $d | \Delta f(x)$ for all integers $x$.

3. If $f$ is a polynomial, then $\Delta f$ is a polynomial of degree $\deg f - 1$.

It follows that $d | f(x)$ for all positive integers $x$ if and only if

$$d | f(1), \Delta f(1), \Delta^2 f(1), ... \Delta^{\deg f} f(1)$$

and $d | \Delta^{\deg f+1} f(x)$ for all positive integers $x$. But $\Delta^{\deg f+1} f$ is identically zero, hence $d | \Delta^{\deg f+1} f(x)$ for all integers $x$, hence $d | f(x)$ for all integers $x$.

Incidentally, these polynomials are closely related to the Chebyshev polynomials of the second kind.

-
Proof 1 seems not valid. Fix $p$, then every element of $\mathbb{F}_p$ is a root of $x^p-x$. Your argument only shows that a prime common divisor cannot be larger than the degree of $f$. – h__ Aug 25 '12 at 2:04
@hyh: you are right. Actually I made the argument much more complicated than necessary. – Qiaochu Yuan Aug 25 '12 at 2:08
I actually should have asked a different question to avoid your counter-example in the question: is it possible for some $m$ there is a prime $p$ which divides $g_m(b)$ for all $b$ that's coprime to $p$? i.e. is it possible for $x^{p−1}−1$ to divide $g_m(x)$ mod $p$? – h__ Aug 25 '12 at 7:13