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$

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.