On 7/4/07, Dan Gildea <gildea at pobox.com> wrote:
> Rational Expansion Theorem for Distinct Roots
> Graham, Knuth, Patashnik, "Concrete Math" 2nd ed, p 340
>
> If R(z) = P(z)/Q(z), where Q(z) = q0*(1-r_1*z)*...*(1-r_l*z) and the
> numbers (r_1 ... r_l) are distinct, and if P(z) is a polynomial of degree less
> than l, then
> [z^n]R(z) = a_1*r_1^n + ... + a_l*r_l^n, where a_k = -r_k*P(1/r_k)/Q'(1/r_k)
>
> The code is here:
> https://sourceforge.net/tracker/?func=detail&atid=304933&aid=1722156&group_id=4933
Dan, thanks a lot for working on this problem.
I appreciate your help.
I have merged the code you posted into my cvs sandbox.
It appears that the results are the same as what you noted.
I assume that you have verified the results are correct;
I did not do so. The new code does not cause any existing
test suite example to fail.
However, some new cases which correspond to your example
problems fail in the test suite. This is probably a bug in the
code to run the test suite. Maybe Barton or Stavros can
consider this. I've appended some relevant test output.
Robert
PS. Here are the test cases for the new examples:
/* PROBLEM 14 */
powerseries((1)/((1-2*x)*(1-3*x)), x, 0);
'sum((3^(i1+1)-2*2^i1)*x^i1,i1,0,inf);
/* PROBLEM 15 */
powerseries((1)/(1-x-x^2), x, 0);
-'sum((-2*(sqrt(5)-1)^(-i2-1)*2^i2/sqrt(5)
-2*(sqrt(5)+1)^(-i2-1)*(-2)^i2/sqrt(5))
*x^i2,i2,0,inf);
/* PROBLEM 16 */
powerseries((1+x)/(1-2*x^2), x, 0);
'sum((-(1/sqrt(2)-1)*2^(i3/2)*(-1)^i3/2
-(-1/sqrt(2)-1)*2^(i3/2)/2)
*x^i3,i3,0,inf);
/* PROBLEM 17 */
powerseries((1+x)/(1-x)^2, x, 0);
'sum(2*(i4+1)*x^i4-x^i4,i4,0,inf);
/* PROBLEM 18 */
powerseries((1+x^3)/(1-x-x^2), x, 0);
-2*x
*'sum((-2*(sqrt(5)-1)^(-i5-1)*2^i5/sqrt(5)
-2*(sqrt(5)+1)^(-i5-1)*(-2)^i5/sqrt(5))
*x^i5,i5,0,inf)
-x+1;
/* PROBLEM 19 */
powerseries((1)/((1-2*x)*(x)), x, 0);
('sum(2^i6*x^i6,i6,0,inf))/x;
/* PROBLEM 20 */
powerseries((1+x+x^2)/((1-2*x)*(1+x)^2), x, 0);
'sum(7*2^i7*x^i7/9+(i7+1)*(-1)^i7*x^i7/3-(-1)^i7*x^i7/9,i7,0,inf);
/* PROBLEM 21 */
powerseries((1-x^2)/(1-4*x^2+x^4), x, 0);
'sum((-(-sqrt(3)-1)*(sqrt(3)+2)^(-i8-1)/(2*(sqrt(3)+2)-4)
-(2-sqrt(3))^(-i8-1)*(sqrt(3)-1)/(2*(2-sqrt(3))-4))
*x^(2*i8),i8,0,inf);
Here is the content of tests/rtest16.ERR after running:
batch("tests/rtest16.mac", test);
Note that the claimed "Expected result" is actually different from
the expected result as stated in the test script.
/* Problem 14 */
powerseries(1/((1-2*x)*(1-3*x)),x,0);
/* Erroneous Result?:
'sum((3^(i1+1)-2*2^i1)*x^i1,i1,0,inf) */
/* Expected result: */
'sum((3^(1+i1)-2*2^i1)*x^i1,i1,0,inf);
/* Problem 16 */
powerseries((x+1)/(1-2*x^2),x,0);
/* Erroneous Result?:
'sum((-(1/sqrt(2)-1)*2^(i3/2)*(-1)^i3/2
-(-1/sqrt(2)-1)*2^(i3/2)/2)
*x^i3,i3,0,inf) */
/* Expected result: */
'sum(((-(1/sqrt(2)-1)*2^(i3/2)*(-1)^i3)/2
-((-1)/sqrt(2)-1)*2^(i3/2)/2)
*x^i3,i3,0,inf);
/* Problem 21 */
powerseries((1-x^2)/(x^4-4*x^2+1),x,0);
/* Erroneous Result?:
'sum((-(-sqrt(3)-1)*(sqrt(3)+2)^(-i8-1)/(2*(sqrt(3)+2)-4)
-(2-sqrt(3))^(-i8-1)*(sqrt(3)-1)/(2*(2-sqrt(3))-4))
*x^(2*i8),i8,0,inf) */
/* Expected result: */
'sum(((-(-1-sqrt(3))*(2+sqrt(3))^(-1-i8))/(2*(2+sqrt(3))-4)
-(2-sqrt(3))^(-1-i8)*(sqrt(3)-1)/(2*(2-sqrt(3))-4))
*x^(2*i8),i8,0,inf);