2
$\begingroup$

Suppose $X_1, X_2$ and $X_3$ are all non-negative integers. So for this linear integer equation:

$X_1 - 2X_2 + X_3 = 10$

Please note that the coefficient for $X_2$ is negative (i.e. $-2$).

What is the generating function for it?

  • 0
    Your question only talks about $3$ terms $X_1$, $X_2$, and $X_3$. In my answer, I've extrapolated this to mean any three consecutive terms in a sequence, but it is not clear from your question that this is the proper thing to do. Would you please clarify the question?2012-12-11

3 Answers 3

1

It is not clear what is asked for. But let $a_n$ be the number of solutions of $X_1-2X_2+X_3=10$ with $T_2=n$. If the problem is about $a_n$, an answer can be calculated.

We are solving $X_1+X_3=2n+10$. The number $a_n$ of ordered pairs $(X_1,X_3)$ with $X_1+X_3=2n+10$ is $2n+11$. Let $f(t)=\sum_0^\infty (2n+11)t^n$. An explicit closed-form formula for this can be written down.

Or else use the recurrence $a_{n+1}=a_n+2$, with initial condition $a_0=11$ to write down the generating function.

  • 0
    This is helpful Andre. However how do we deal with the general case? A general linera Diophantine question in the form of X_1+2X_2+X3=10 with restriction such as 1<=X_1<=3, 0<=X<2<=2 will be solved by having the generating function as g(x) = (x+x^2+x^3)(1+x^2)(1+x+x^2+...) and then figure out the 10th coefficient, however how do we handle the case when it is -2x_2?2012-12-11
1

It seems as if the question is asking for the generating function for a sequence which satisfies $ X_n-2X_{n-1}+X_{n-2}=10\tag{1} $ This is simply $S^2X_n=10\Rightarrow S^3X_n=0$, which has a quadratic function of $n$ as a solution. Since $S^2(an^2+bn+c)=2a$, we get that $2a=10$. That is, for appropriate $b$ and $c$, $ X_n=5n^2+bn+c\tag{2} $ Generating Function

Define $ f(t)=\sum_{n=0}^\infty X_nt^n\tag{3} $ Multiply $(1)$ by $t^n$ and sum: $ \sum_{n=2}^\infty(X_n-2X_{n-1}+X_{n-2})t^n=\sum_{n=2}^\infty10t^n\tag{4} $ which is equivalent to $ (f(t)-X_1t-X_0)-2t(f(t)-X_0)+t^2f(t)=\frac{10t^2}{1-t}\tag{5} $ After algebraic manipulation, $(5)$ becomes $ f(t)=\frac{10t^2}{(1-t)^3}+\frac{(X_1-X_0)t}{(1-t)^2}+\frac{X_0}{1-t}\tag{6} $

0

The question is not well posed. But it seems to me the most natural interpretation would be that it is asking for a generating function for the number of triples $(X_1,X_2,X_3)\in\Bbb N^3$ that satisfy the equation; that would explain why OP stresses the negative coefficient that is not usually found in such problems. And the answer is that there is a good reason for negative coefficients usually being absent, they tend to make the number of solutions infinite, and they certainly do in this example (for instance $(n,n,n+10)$ is a solution for every $n$). So I would answer, there is no gerating function, because none of the numbers it should generate are defined in the first place.