Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
    
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$. –  hyh 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$? –  hyh Aug 25 '12 at 7:13
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.