Quick tip: Do you prefer typeset output?

If you are using the show(...) command a lot, you might want to try out switching to typeset output.

Challenge

• Find an identity $\sum_k a_{n,k} = b_n$ with hypergeometric terms $a_{n,k}$ (in both $n$ and $k$) and $b_n$ such that $F(n,k) = a_{n,k}/b_n$ does not have a WZ mate.

Loading the packages

• You need to first download the wz.py file from our website and make it available to Sage by, for instance, copying it into the directory containing the Sage notebook.

• The ore_algebra package is already installed on the SageMathCloud, but needs to otherwise be installed. See http://arxiv.org/abs/1306.4263v1 for more information, including examples, on this package.

When running commands from these below, you will usually see several DeprecationWarning's pop up in red font. To get rid of these, you can run the command again.

Celine's method

Examples from class

Example: $\displaystyle\sum_k \binom{n}{k}$.

Example: $\displaystyle\sum_k k\binom{n}{k}$.

Recall that the sum actually equals $n 2^{n-1}$. Let's see a few ways to check that.

Before we continue... note the following very common cause of unexpected trouble: n is no longer the variable it used to be.

(When writing for n in [0..5], n was assigned numerical values.)

Exercise

• Find a recursion for the sum $\displaystyle A_n = \sum_k k^2\binom{n}{k}$.

• Prove that $A_n = 2^{n-2}n(n+1)$.

• What about the sums $\displaystyle A_n = \sum_k k^a\binom{n}{k}$ for $a>2$?

No recursion found if we only allow order 1 for the shift operators.

Increasing either of the orders, we do find recurrences.

Which of these two should we prefer?

Note that we want a recursion for the sum of least possible order (from the answer, we know that there is one of order 1, but Celine's method is not guaranteed to find the one of least order). Therefore, we should increase the order in $S_k$ before increasing the order in $S_n$. In this example, we succeeded and actually found a first-order recursion for the sum.

From there, we can derive the formula $2^{n-2}n(n+1)$ ourselves.

This is again a first order operator, so we can immediately express the sum as a hypergeometric term.

Here is a less inspired way to find the solution. Just to expose some more advanced possibilities...

Can you figure out what is going on?

WZ method

Example: $\displaystyle\sum_k \binom{n}{k} = 2^n$.

Why is it fully expected that we don't find a WZ mate for $F(n,k)=\binom{n}{k}$?

Example: $\displaystyle\sum_k k\binom{n}{k} = n 2^{n-1}$.

Example: $\displaystyle\sum_k \binom{n}{k}x^k = (1+x)^{n}$.

This example illustrates that we can work with symbolic parameters.

Exercise

• Give a WZ proof of $\displaystyle \sum_k \binom{n}{k}^2 = \binom{2n}{n}$.

• Give a WZ proof of $\displaystyle \sum_k k^2\binom{n}{k} = n(n+1) 2^{n-2}$.

• What about the sums $\displaystyle A_n = \sum_k k^a\binom{n}{k}$ for $a>2$?

Gosper's algorithm

Example: sums of powers

Recall what this means: if $f(n)=n$, then $g(n)=n(n-1)/2$ is a discrete antiderivate, that is, $f(n) = g(n+1)-g(n)$.

In particular, $\displaystyle \sum_{k=0}^{n-1} f(k) = g(n)-g(0)$.

Exercise

• Does $f(n)=n!$ have a hypergeometric term discrete antiderivative? What about $f(n)=n \cdot n!$?

• Evaluate the sum $\displaystyle\sum_{n=0}^{N} \frac{1}{(n+1)4^{2n}} \binom{2n}{n}^2$.

• Discover the geometric sum.

• Determine $\displaystyle\sum_{n=0}^{N} \binom{n}{k}$.

• Compute a WZ pair for $F(n,k) = \binom{n}{k}/2^n$ directly by using Gosper's algorithm.

Simplifying symbolic expressions is not yet one of Sage's strong points...

Let's check that we get the same answer as from WZ:

Why are the rational functions slightly different?

Ore Algebra Basics

Working with derivative operators

Finding power series solutions to differential equations

Just one example of the things we can do. Explore more yourself by going through the properties of operators.

Find all solutions to the Bessel differential equation

This is the Bessel $J_0$ function. Let's compare with the builtin function.

One of the inconsistencies... the following should work, too, but doesn't simplify yet.

The Bessel function is the unique analytic solution the second-order differential equation. Here is the second solution.

Check out the Frobenius method if you are interested in learning how to find all these solutions.

We made x a variable in a polynomial ring over Q. Let's revert it to a symbolic variable before confusing ourselves later on.

Working with shift operators

Playing with the Fibonacci recurrence

Depending on the initial values, we get Fibonacci or Lucas numbers

Guessing recurrences

With only a few values, you can try to guess a recurrence.

Of course, we could have done that by hand, too.

But the guessing works for any sequence, as soon as you have a way to compute sufficiently many terms.

Exercise

• In different ways, obtain an operator which annihilates $a_n=n!$.

• Find an operator which annihilates the square of the Fibonacci numbers.

• Find an operator which annihilates both $a_n=n!$ and the Fibonacci numbers.

Let's find a recurrence for squares of Fibonacci numbers by guessing.

(This is actually a perfectly rigorous way of finding the recurrence, because we know from class that there has to be a recurrence of order 3 with constant coefficients.)

Here is an advanced alternative:

Conversion between shift and derivative operators

From a recurrence to a differential equation (for the ogf)

From a differential equation to a recurrence

Zeilberger's algorithm

Given a hypergeometric term $F(n,k)$, Zeilberger's algorithm determines an operator $P(n,N)$ such that $$P(n,N) \cdot F(n,k) = G(n,k+1)-G(n,k)$$ for some $G(n,k)$.

This computation can be certified with a rational function $R(n,k)$ such that $G(n,k)=R(n,k)F(n,k)$.

Exercise

• Find a recursion for $\displaystyle A_n = \sum_{k=0}^n \binom{n}{k}^4$.

• Prove that $$\sum_k \binom{2 k}{k} \binom{2 n - 2 k}{n - k} \binom{n + k}{n - k} \binom{n

• k}{k} = \sum_k \binom{n}{k}^4.$$

It only remains to check at least two initial values (note that the leading coefficient in the recurrence doesn't vanish for $n\ge0$).