7
$\begingroup$

Very possibly this has been asked before, but as I couldn't find it:

Let $(a_n)_{n\in\mathbb N}$ be a sequence, and $$\sum_{n= 0}^\infty a_n $$ an infinite sum.

I'm looking for general methods of transforming this sum into a telescoping sum, i.e. finding a solution to the recurrence formula $$a_n= r(n) - r(n-1) $$

This can be seen as an inhomogenous recurrence equation: $$r(n)= r(n-1)+a_n $$

One failed attempt would be this:

Using the methods of discrete math, we can show that the generating function of $r(n)$ has the closed form: $$ \sum_{i=0}^\infty r(i)x^i = \frac{r(0) - \sum_{n=d}^\infty a_n x^n}{1-x}$$

However, to make use of this, we would first need to find a closed form for $$ \sum_{n=d}^\infty a_n x^n$$ However, if we find a closed form for that, we might as well find a closed form for $$\sum_{n=0}^\infty a_n x^n$$ , substitute $x=1$ and be done with it.

TL, DR: In this form, my approach either is missing something, or plain pointless. What are other possible ways of going about solving this recurrence equation, or other general ways to transform sums into telescopic-sum-form?

$\endgroup$
  • $\begingroup$ Do you mean $x=1$ instead of $x=0$? $x=0$ is a pretty boring substitution there. $\endgroup$ – Yakk Jun 14 at 19:28
  • $\begingroup$ @Yakk You're of cause correct $\endgroup$ – Sudix Jun 14 at 20:13
4
$\begingroup$

In general, there is no suitable technique for all cases. Some series don't exactly have telescoping components that are easy to track. One example of types of series that may have a telescoping component are hypergeometric series, whre we wish to sum anything of the form

$$\sum_{k=0}^n\frac{(a_1)_k...(a_p)_k}{(b_1)_k...(b_q)_k}$$

where the notation $(a)_k$ denotes the ascending factorial function. Hypergeometric functions are any functions that can be written in such a fashion, along with the term $x^k/k!$ and the upper limit is taken as infinite. Finding the telescoping series for these requires the use of Gosper's Algorithm, or its modified version Zielberger's Algorithm. Here is an example of how to use Gosper's algorithm.

Suppose that we want a closed form for the sum

$$S_m=\sum_{k=0}^m(-1)^k\binom{n}{k}$$

where $m\leq n$. To evaluate

$$S_m=\sum_{k=0}^ma_k$$

we notice that $S_m-S_{m-1}=a_m$. This, the sum $S_m$ is a sort of antiderivative of the discrete sum. As such, $S_m$ is sometimes called the indefinite sum of $a_k$. Without going into detail, we wish to write the ratio of the terms such that

$$\frac{a_{k+1}}{a_k}=\frac{p_{k+1}}{p_k}\frac{q_k}{r_k}$$

for some polynomials $p_k,q_k$, and $r_k$. One condition that we must enforce (for complicated reasons) is that if $(k+\alpha)$ divides $q_k$ and $(k+\beta)$ divides $r_k$, then $\alpha-\beta-1$ cannot be a positive integer. This is always possible by multiplying appropriate terms to the polynomial $p_k$ until this is true. For our problem, we have

$$\frac{a_{k+1}}{a_k}=\frac{(-1)^{k+1}\binom{n}{k+1}}{(-1)^k\binom{n}{k}}=\frac{k-n}{k+1}$$

Here, $p_k=1$, $q_k=k-n$, and $r_k=k+1$, which satisfy our hypotheses. Gosper's Algorithm states that if a hypergeometric telescoping term exists, then it must take the form

$$S_{k-1}=\frac{r_{k-1}a_ks_k}{p_k}$$

for some polynomial $s_k$ (again, the reasoning is complicated). The polynomial $s_k$ is the solution to

$$p_k=q_ks_{k+1}-r_{k-1}s_k$$

Throwing in our equations, we have

$$1=(k-n)s_{k+1}-ks_k$$

If we assign $s_k=-1/n$, which is a polynomial in $k$ of degree $0$, then this satisfies the polynomial condition. Thus, we have

$$S_{k-1}=(-1)^{k+1}\frac{k\binom{n}{k}}{n}=(-1)^{k+1}\binom{n-1}{k-1},\;\;\;\;S_k-S_{k-1}=a_k$$

An important rule when dealing with hypergeometric terms is if a factorial ever becomes negative, we simply regard it as $0$. Our final answer is

$$\sum_{k=0}^m(-1)^k\binom{n}{k}=S_m-S_{-1}=(-1)^{m}\binom{n-1}{m}$$

Plenty of other hypergeometric sums and series can be established, such as $k!$, $1/(k^2-1)$, etc. More generally, however, we can't always use this, but we can find recursion relations between similar series. For example, Let's consider the sum

$$S=\sum_{k=0}^n\binom{n}{k}^2$$

Gosper's Algorithm will yield no polynomial $s_k$ that we need. Instead, we seek to use Gosper's Algorithm on the modified sum

$$S=b_0\sum_{k=0}^n\binom{n}{k}^2+b_1\sum_{k=0}^{n+1}\binom{n+1}{k}^2$$

for some coefficients $b_n$ to be specified later. Applying the term ratio gives

$$\frac{a_{k+1}}{a_k}=\frac{b_0\binom{n}{k+1}^2+b_1\binom{n+1}{k+1}^2}{b_0\binom{n}{k}^2+b_1\binom{n+1}{k}^2}=\frac{b_0(k-n)^2+b_1(n+1)^2}{b_0(k-n-1)^2+b_1(n+1)^2}\frac{(k-n-1)^2}{(k+1)^2}$$

We assign $p_k=b_0(k-n-1)^2+b_1(n+1)^2$, $q_k=(k-n-1)^2$, and $r_k=(k+1)^2$. The polynomial $s_k$ satisfies

$$b_0(k-n-1)^2+b_1(n+1)^2=(k-n-1)^2s_{k+1}-k^2s_k$$

Without going into detail, the quantity $s_k=2k-3(n+1)$ satisfies the equation with $b_0=-2(2n+1)$ and $b_1=n+1$. We now have

$$S_{k-1}=\frac{k^2(-2(2n+1)\binom{n}{k}^2+(n+1)\binom{n+1}{k}^2)(2k-3(n+1))}{-2(2n+1)(k-n-1)^2+(n+1)^3}$$

We then have partial sums of

$$-2(2n+1)\sum_{k=0}^m\binom{n}{k}^2+(n+1)\sum_{k=0}^m\binom{n+1}{k}^2=\frac{(m+1)^2(-2(2n+1)\binom{n}{m+1}^2+(n+1)\binom{n+1}{m+1}^2)(2(m+1)-3(n+1))}{-2(2n+1)(m-n)^2+(n+1)^3}$$

Letting $m$ be large enough such that the factorial terms vanish, we have that the indefinite sum vanishes, and

$$\sum_{k=0}^{n+1}\binom{n+1}{k}^2=\frac{2(2n+1)}{n+1}\sum_{k=0}^n\binom{n}{k}^2$$

This yields a recursion relation for the sum in question. For $n=0$, the sum is $1$. Using the recursion, we get the next sums are $2,6,20,$ etc. These are precisely the central binomial coefficiants, so we finally have

$$\sum_{k=0}^n\binom{n}{k}^2=\binom{2n}{n}$$.

This algorithm may be employed many times over on many different sums, where the sums may also be infinite.

$\endgroup$
11
$\begingroup$

You are essentially asking for a general method to sum any finite or infinite series (or indefinite sum). Correct? There is no such method. For certain special families of series, there do exist methods. For instance, summing of polynomial sequences, that is, $\sum_n n^k$ using Bernoulli numbers. An important special case similar to telescoping series is using Wilf–Zeilberger pairs which requires a computer algorithm.

$\endgroup$
  • $\begingroup$ Well, a general method of cause would have its limits, i.e. lead in particular cases to uncomputable functions or simply fail. Both would be acceptable outcomes though. $\endgroup$ – Sudix Jun 14 at 3:29
  • $\begingroup$ If you could list the families of functions for which methods are known (or you know well enough), and the general method, it'd help me a lot! $\endgroup$ – Sudix Jun 14 at 3:31
3
$\begingroup$

You are looking for $$ a(n) = r(n) - r(n - 1) $$ or, what is more standardly adopted $$ a(n) = s(n + 1) - s(n) = \Delta s(n) $$

Then $s(n)$ is called the Antidelta or Indefinite Sum of $a(n)$, and same as for integrals some functions have a closed form for the Antidelta, and some don't.

You can find more details in the indicated link.

$\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.