4
$\begingroup$

I am trying to understand the book A = B which has many much more complicated expressions which are Gosper-summable but then on p. 102 he states $\binom{n}{k}$ for fixed $n$ as a function of $k$ is not Gosper-summable. How can this be? Can someone show why it is not Gosper-summable?

$\endgroup$

2 Answers 2

7
$\begingroup$

Gosper's algorithm can only find a formula for $$ S(k) = \sum_{i=0}^k \binom ni $$ if it turns out that $S(k)$ is itself a hypergeometric term: if $\frac{S(k+1)}{S(k)}$ is a rational function of $k$.

However, for $k \ge n$, $\frac{S(k+1)}{S(k)} = \frac{2^n}{2^n} = 1$, so if it were a rational function, it would be equal to $1$ everywhere (aside possibly from places it's not defined). That's not what it does. Therefore it's not a rational function, $S(k)$ is not a hypergeometric term, and a series with partial sums $S(k)$ is not Gosper-summable.

In general, whenever we have a series with only finitely many nonzero terms (as we do here), it can only be Gosper-summable if the infinite sum over all terms is $0$. In that case, we can't carry out the argument above, because we can't say "our rational function is equal to $\frac{0}{0} = 1$ at infinitely many points".

$\endgroup$
7
  • $\begingroup$ Why is it not possible to assume only the values of k>-1,k<n for integer k ? For example k mod n. I am not too good at theoretical math but i guess that would not be a valid field? and/or it has divisors of zero which would be a problem? Anyway back to the normal field I suppose 1/k! is also not gosper summable ? $\endgroup$
    – user158293
    Sep 19, 2021 at 19:56
  • $\begingroup$ When you say for the same reason can be more specific. In this case we don't have only a finite number of non 0 terms. Or is it the case that the sum over all terms to inf be 0 ? It doesn''t seem that should be the case as it seems would be much too restrictive. $\endgroup$
    – user158293
    Sep 19, 2021 at 20:34
  • $\begingroup$ @userMisha_LAVROV For some reason my last comment disappeared . When you say for the same reason could you be more specific. For example in the case of 1/k! it is not the case that only a finite numbers of terms is non 0. Or would you say the problem is the infinite singularity at k=0 ? $\endgroup$
    – user158293
    Sep 19, 2021 at 20:48
  • $\begingroup$ Sorry, my previous comment was just nonsense. I'd have to think more about what's going on with $1/k!$. $\endgroup$ Sep 19, 2021 at 21:01
  • $\begingroup$ I suppose you could argue that $\frac{S(k+1)}{S(k)} = \frac{e + O(1/(k+1)!)}{e + O(1/k!)}$ approaches $1$ much more quickly than a rational function ever could. $\endgroup$ Sep 19, 2021 at 21:06
1
$\begingroup$

I try an alternate proof and write the sum as $\sum_{n=0}^m \binom {p}{n}$ for $m,p$ arbitrary large positive integers $p\!>\!m$. Per the book A=B denote the summand by $t_n=\binom{p}{n}$ and $r(n)=\frac{t_{n+1}}{t_n}=\frac{p-n}{n+1}$ here. On p75 eq.(5.2.3) is stated assume can write $$r(n)=\frac{a(n)c(n\!+\!1)}{b(n)c(n)}$$ where $a,b,c$ polynomials in n and $ gcd(a(n),b(n\!+\!h))\!=\!1$ for all integers $h\!>\!-1$ and I find $a\!=\!p\!-\!n,b\!=\!n\!+\!1,c\!=\!1$ as the lowest order or only? possibility. Anyway it goes on... and per p76 it requires a finite polynomial solution x to $$a(n)x(n\!+\!1)-b(n\!-\!1)x(n)\!=\!c(n)$$ which in this case is $$(p-n)x(n\!+\!1)-nx(n)\!=\!1$$ and if such a polynomial $x(n)$ cannot be found then Gosper's method fails. Though I can't prove it rigorously it seems in this case such a polynomial does not exist for the only possibilities would be $x=cst$ which obviously does not satisfy or else of order >zero in which case the coeff. of the highest order term on lhs would have to be 0 which is not the case either so conclude Gosper's method fails so $\sum_{n=0}^m \binom {p}{n}$ is not Gosper summable ? For more detail the book is on the internet and can be found by searching 'book A=B' eg on google. By the way per Gosper's basic method it must satisfy 1st order recurrence. It seems to me for most practical applications the cases where Gosper's method works are very limited.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .