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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Namaste Dec 10 '12 at 21:49
  • $\begingroup$ 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. math.upenn.edu/~wilf/gfologyLinked2.pdf's book doesn't study my case either. $\endgroup$ – Min Zhu Dec 10 '12 at 22:07
  • 1
    $\begingroup$ 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. $\endgroup$ – Namaste Dec 10 '12 at 22:14
  • $\begingroup$ 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? $\endgroup$ – robjohn Dec 11 '12 at 8:21
1
$\begingroup$

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} $$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user52588 Dec 11 '12 at 5:29
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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