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?

  • 1
    It helps us to know what have you tried. You're apt to get more help if you explain what you know, what you've tried, and/or where you are stuck. Otherwise some people may think you're asking us to do your (home)-work for you.2012-12-10
  • 0
    No this is really not related to any HW. My reading on the linear Diophantine question in this form seeking for non-negative solutions only has the non-negative coefficients, and there is no document/materials treating the negative coefficients. http://www.math.upenn.edu/~wilf/gfologyLinked2.pdf's book doesn't study my case either.2012-12-10
  • 1
    Even if it were homework, we field homework questions as well. Suggestion: why don't you include the text from your comment (immediately above) directly in your post, so we all can better understand what you're looking for, and where the question originates.2012-12-10
  • 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.