Suppose (an) is a sequence where an is the number of solutions for x1 + x2 + x3 + x4, where all xi are integers, with x1 ≥ 3, 1 ≤ x2 ≤ 5, 0 ≤ x3 ≤ 4, and x4 ≥ 1.

Find a closed form for the generating function of (an).

Well, you can multiply polynomials together:

(x3 + x4 + x5 + . . . )(x + x2 + x3 + x4 + x5)(1 + x + x2 + x3 + x4)(x + x2 + x3 + . . .)

You can also look for a smaller function, like fj say, being the number of solutions for x2 + x3 + x4 and write it as a sum over n.

In the first case, after simplifying, I can't work out how to get to a closed form, but I can find a "closed sum" by making n ≥ 5 (since, obviously there are zero solutions for n ≤ 4).
Does anyone have any suggestions? This isn't homework as such, but it is a tutorial question, and the tute is on Thursday.

Aha! Caffiene sufficiency can be a wonderful thing:

Multiply the polynomials together (these just represent a series for each term xi). You should get:


x^4 \cdot \frac {1} {(1 - x)^2} \cdot \frac {(1 - x^5)^2} {(1 - x)^2}

So, since we know the first five terms of (an) are all zero (are not solutions), the first solution looks like it's x5, but be careful, it's the 6th term in the series.

So the coefficient of x5 in the above formula, is also the coeffient of x in


\frac {1} {(1 - x)^2} \cdot \frac {(1 - x^5)^2} {(1 - x)^2} because of the x4 factor.

Expanding out:


\frac {(1 - 2x^5 + x^{10})} {(1 - x)^4}

. . . which is what we want to know the coefficient of x in. But since the last two terms in the numerator have exponents > 1, we can ignore them and so the coefficient of x in the series is given by


\frac {1} {(1 - x)^4} .

This is just C(4 + 1 -1, 1) = C(4,1) = 4, and indeed a5 (the 6th term in an) has four solutions, the set of tuples: (4,1,0,1), (3,2,0,1), (3,1,1,1), (3,1,0,2). This makes sense because the 5th term (the coefficient of x4) has only one solution, the tuple (3,1,0,1) and there are four ways to increment it.


(mistake corrected, a6 is the 7th term, darn it)

Well, wasn't that fun?

Now this:

Use the same kind of solution for the recurrence relation: a0 = 1, a1 = 3, and an = an-1 + 2an-2 + 2n.

Here, it looks like we need to introduce the general solution f(x) = \sum_{n=0}^\infty a_n x^n , where

anxn = (an-1 + 2an-2 + 2n)xn, and we just distribute the summation.

But this is a curly one, isn't it? Oh yes.

I've been using up too much paper, so in a thoughtful effort to save trees, let's have a crack at it in the modern, paperless medium. (Oh yes, let's).

So we have (since n should be ≥ 2):

f(x)\; =\; \sum_{n=2}^\infty a_n x^n\; =\; \sum_{n=2}^\infty a_{n-1} x^n\; +\; 2 \sum_{n=2}^\infty a_{n-2} x^n\;+\;\sum_{n=2}^\infty 2^nx^n , where a0 = 1, a1 = 3.

And now we can decrement the n in each sum (this is ok as long as n isn't -ve, because that doesn't make mathematical sense):


f(x)\; =\; \sum_{n=1}^\infty a_n x^{n+1}\; +\; 2 \sum_{n=0}^\infty a_n x^{n+2}\;+\;\sum_{n=0}^\infty 2^{n+2}x^{n+2}

...incrementing the indices for a and x correspondingly.

Now extract terms from each sum:


f(x)\; =\; x \sum_{n=1}^\infty a_n x^n\; +\; 2x^2 \sum_{n=0}^\infty a_n x^n\;+\; 2x^2 \sum_{n=0}^\infty 2^nx^n

And rewrite each sum as a function of f(x):


f(x)\; =\; x (f(x) + a_0) +\; 2x^2 (f(x) + a_0 + a_1 x)\; +\; 2x^2 \cdot \frac {1} {(1-2x)}

Therefore


f(x)(1\; -\; x\; -\; 2x^2) \; =\; a_0 x\; +\; a_0 2x^2\; +\; a_1 2x^3\; +\; \frac {2x^2} {(1-2x)}\; =\; x\; +\; 2x^2\; +\; 6x^3\; +\; \frac {2x^2} {(1-2x)}\;

But (1\; -\; x\; -\; 2x^2) \; =\; (1\; +\; x)(1\; -\; 2x) so


f(x)\; =\; \frac {x\; +\; 2x^2\; +\; 6x^3\;} {(1 + x)(1 - 2x)}\; +\; \frac {2x^2} {(1+x)(1-2x)^2}\;

And that's the easy part (unless there's a mistake). Factoring the rhs turns out to be problematic.

Hmm, perhaps the cellulose-free approach is as good as caffiene?

You don't try to factor the rhs, just multiply the first term by (1 - 2x)/(1 - 2x) so everything has the same denominator (sounds reasonable). Then multiply the result by (1 + x) to remove that from the denominator.

Then you have a polynomial times 1/(1 - 2x)2, which has a sum over n as C(2 + n - 1,n). So we're away . . .

Well, nearly. More futzing shows it's easier to give the second term the same denominator as the first, then you have

f(x)\; =\; \frac {x\; +\; 2x^2\; +\; 6x^3\;} {(1 + x)(1 - 2x)}\; +\; \frac {2x^2 -4x^3} {(1+x)(1-2x)}\;
Still not that confident about it, but it has no negative coefficients.

Here, I'd like to know if going this way is the only way, and why. These exercises are supposedly about connecting the division theorem (as a kind of algorithm) to its identity, factors in rings and something or other, remainders I guess.

Anyway, after more juggling around with terms, I get f(x)\; =\; \frac {x + 3x^2 + 3x^3 + x^4} {1-2x}

So, think at least, the interesting part, using partial terms of the function in the shall we say, algorithmic phase of the series, is what we're doing this shit for. Like the good Doctor said, there's a few steps to it.

Damn, I shouldn't get that after all (I've just introduced an extra factor rather than making the denominators of both terms the same--what was I thinking?). The only way to do it seems to be the first way.

In that case, I guess I need to pay attention in the tutorial.

I've been using up too much paper, so in a thoughtful effort to save treesF*** trees. If I'm not surrounded by a mound of paper covered in nonsense by the end of the day then something wrong has happened. Sometimes I'll pick up a pile of paper which has been sitting on my desk for ages and think "There must be some blank paper in here somewhere..... no..... no ..... no ..... no..... when the hell did I write this much!?".


Aha! Caffiene sufficiency can be a wonderful thing:Too much is a horrible thing though.

I'll assume since no-one's said otherwise that my first part of the solution is ok.

But I had a quick chat with Dr Stokes and he wasn't sure, when I rattled off the polynomial, that it sounded right.
Bloody hell.

But helpful hint #2 was that the next part of the solution involves partial fractions in three unknowns.

Well I made a mistake after all.


f(x)\; =\; \sum_{n=2}^\infty a_n x^n\; =\; \sum_{n=2}^\infty a_{n-1} x^n\; +\; 2 \sum_{n=2}^\infty a_{n-2} x^n\;+\;\sum_{n=2}^\infty 2^nx^n
This should be:

f(x)\; =\; \sum_{n=0}^\infty a_{n-1} x^n\; +\; 2 \sum_{n=0}^\infty a_{n-2} x^n\;+\;\sum_{n=0}^\infty 2^nx^n\; -\; \sum_{n=0}^\infty a_n x^n\; where a0 = 1, a1 = 3.

Starting again with: an= an-1 + 2an-2 + 2n
=> an - an-1 - 2an-2 = 2n.

So an+2 - an+1 - 2an = 2n+2. For some reason it's a good idea to rearrange it like this and change the indices.

Using the same summation approach, you get: f(x)\; =\; \frac {1} {(1+x)(1-2x)^2} .

So now you use the partial fractions: \frac {1} {(1+x)(1-2x)^2}\; =\; \frac {A} {(1+x)}\; +\; \frac {B} {(1-2x)}\; +\; \frac {C} {(1-2x)^2} .

The "rule" (it's been a while) seems to be that each numerator has to be of lower degree than the denominator.
I guess that means the last term could also be \frac {Cx + D} {(1-2x)^2} .

This will mean the solution is longer, so it may not be helpful (but it should give the same solution as having just C in the numerator).