I post a problem today and its solution on Thursday.
Comments are fine, though if you don't want to get a hint, don't read them.
Find the coefficient of x100 in the Taylor series for the rational function which has
numerator 1
and denominator
x41 - x40 - x36 + x35 -x31 + x30 + x26 - x25- x16 + x15 + x11 - x10 + x6 - x5 -x+1
For better readability see my pdf file with the problem in it here
Is there a clever way to do the problem? If the way to do it was to actually do the Taylor series then
1) I wouldn't post it
2) I probably could not do it (or it would take too long to bother) though maybe there are freely available programs that could.
So yes, there is a clever solution. At least I think it's clever.
Do you mean at x = 0?
ReplyDeleteYes, taylor series at 0
ReplyDeleteObviously partial fractions is one way. In this instance a slicker way is to factor out 1-x and notice the other factor has only powers of x^5. So you need the coefficient of x^100 in the reciprocal of that other factor. Replace x^5 by y and you need the coefficient of y^20 in 1/((1-y)*(1-y^2)*(1-y^5)), or equivalently the number of ways to make $20 with 1,2 and 5 dollar bills, which is easy enough to calculate by hand and is 29.
ReplyDeleteThat IS what I had in mind, though either you or I has made an error, please respond since if it was me I need to fix my Thursday post.
ReplyDeleteI thought I had making 100 dollar with 1,2,5,10,25 (I was thinking of change of a dollar with pennies, nickels, dimes, and quarters.)
Please check your work and get back to me either by email or by comments.
Is this of any use? (-1 + x)^5 * (1 + x + x^2 + x^3 + x^4)^3 * (1 + 2 x^5 + 2 x^10 + 2 x^15 + 2 x^20 + x^25))
DeleteThis comment has been removed by the author.
DeleteI did make an error (the 1-x factor is in the denominator, not the numerator) so indeed you need to make change with 1,5, 10 and 25 cents (though not 2, I think) and the answer is an order of magnitude higher than what I wrote.
ReplyDeletethe 2 was a typo, YES its 1,5,10,25.
DeleteThere is a recent paper by A. Bostan and R. Mori that provides a fast algorithm for this task, and more generally is able to compute any coefficient of the Taylor expansion of any rational function, in quasi-optimal time: "A Simple and Fast Algorithm for Computing the N-th Term of a Linearly Recurrent Sequence." with a short version at SOSA'21. (cf https://specfun.inria.fr/bostan/BoMo20.pdf)
ReplyDeleteThe main, simple and elegant idea to compute the N-th term of F = P/Q is as follows:
1. Write F = P(X)Q(-X)/Q(X)Q(-X)
2. Compute V s.t. Q(X)Q(-X) = V(X²)
3. Compute U_o, U_e s.t. P(X)Q(-X) = U_e(X²) + X U_o(X²)
4. Recursively compute the N/2-th term of either U_e/V or U_o/V, depending on the parity of N
This provides a divide-and-conquer algorithm that runs very fast (see details in the paper).
Let f(x) denote the expression. It is clear that
ReplyDeletef(x) = (1-x)(1-x^5)(1-x^10)(1-x^25)
Then,
1/f(x) = 1/((1-x)(1-x^5)(1-x^10)(1-x^25))
= (1+x+x^2+...)(1+x^5+x^10+...)(1+x^10+x^20+...)(1+x^25+x^50+...)
We are interested in the coeff of x^100. Let us choose x^k1 from first term, x^(5*k2) from second,
x^(10*k3) from third and x^(25*k4) from the fourth. So we get
x^100 = x^(k1 + 5*k2 + 10*k3 + 25*k4)
100 = k1 + 5*k2 + 10*k3 + 25*k4
The number of non-negative integer solutions to this above equation determines the coeff of x^100.
Taking (mod 5) on both sides, we see that k1 = 5*k0 some non-negative integer k0.
Therefore,
100 = 5*k0 + 5*k2 + 10*k3 + 25*k4
which implies
20 = k0 + k2 + 2*k3 + 5*k4
where k0,k2 in {0,1,...,20}, k3 in {0,1,2,...,10} and k4 in {0,1,2,3,4}
If k4 = 0, then for each k3 we have 20-2*k3 choices for pairs (k0, k2)
==> 21 + 19 + 17 + ... + 1 = 121 choices
If k4 = 1, then for each k3 we have 15-2*k3 choices for pairs (k0, k2)
==> 16 + 14 + ... + 0 = 72 choices
If k4 = 2, then for each k3 we have 10-2*k3 choices for pairs (k0, k2)
==> 11 + 9 + ... + 1 = 36 choices
If k4 = 3, then for each k3 we have 5-2*k3 choices for pairs (k0, k2)
==> 6 + 4 + 2 = 12 choices
If k4 = 4, then (k0, k2, k3) = (0,0,0)
==> 1 choice
Total = 121 + 72 + 36 + 12+ 1 = 242
Therefore coeff of x^100 is 242.
that is the solution I had in mind.
DeleteI will be posting on Thursday.
Curious- did you use a program to factor or did you do it by hand?
I think this would be a much harder problem to do by hand.
I think you can factor it out by hand by looking at pairs of terms. Since there are even terms that come in pairs in the initial expression, you can get the x-1 factor out naturally as:
Deletep(x) = (x_41 - x_40) - (x_36 - x^35) - (x_31 - x^30) ... - (x - 1)
= x^40(x - 1) - x^35(x - 1) - .... - (x - 1)
= (x - 1)(x^40 - x^35 - x^30 + x^25 - x^15 + x^10 + x^5 - 1)
And if you repeat the same process with the new expression, pairing of terms and factoring out the largest power per pair, you will get the (x^5 - 1), (x^10 - 1), and (x^25 - 1) factors out too.