Manuel Kauers Report on ISSAC Poster

What happened so far…

• Recall: Discrete l’Hospital Let (a_{n}), (b_{n}) be sequences, b_{n} → ∞ as n → ∞ where (b_{n}) is eventually monotonous. Then,

lim_{n→∞} \frac{a_{n}}{b_{n}} = \frac{Δa_{n}}{Δb_{n}}

if the right hand side exists.

• Application: Limits of sequences involving sums

• Examples: (from the first talk, last semester)

lim_{n→∞} \frac{∑_{k=1}^{n} k!}{n!} = 1,  lim_{n→∞} ^{\begin{matrix}∑_{k=1}^{n} & \binom{2k}{k} \\ ( & {2n \atop n} & ) \end{matrix}} = \frac{4}{3},  lim_{n→∞} \frac{1}{\sqrt{n!}} ∑_{k=1}^{n} \sqrt{k!} = 1,  lim_{n→∞} n · 2^{−n} ∑_{k=1}^{n} \frac{2^{k}}{k} = 2,  etc.

• But isn’t this too easy?

Manuel Kauers Report on ISSAC Poster

What about more interesting inputs?

• Do we find lim_{n→∞} \frac{n H_{2n} ∑_{k=1}^{n} \frac{2^{k}}{k}}{H_{n} 2^{n}} = 2?

• For humans, this is still very simple:

lim_{n→∞} \frac{n H_{2n} ∑_{k=1}^{n} \frac{2^{k}}{k}}{H_{n} 2^{n}} = ( lim_{n→∞} \begin{matrix}H & 2n \\ H & n \end{matrix}) · ( lim_{n→∞} \frac{∑_{k=1}^{n} \frac{2^{k}}{k}}{2^{n}/n} ) =^{l’H} ( lim_{n→∞} \frac{4n + 3}{4n + 2}) · ( lim_{n→∞} \frac{2n}{n − 1}) = 2.

• Can a machine do that?

• (Suppose we can automatically detect monotonicity and going to infinity.)

Manuel Kauers Report on ISSAC Poster

What about more interesting inputs? II

• Let’s see

lim_{n→∞} \frac{n H_{2n} ∑_{k=1}^{n} \frac{2^{k}}{k}}{H_{n} 2^{n}} =^{l’H} lim_{n→∞} \frac{(\frac{3}{2} + 2n^{2} H_{2n} +3n H_{2n} + H_{2n} +2n^{2} + \frac{7}{2}n) ∑_{k=1}^{n} \frac{2^{k}}{k} + (4n^{2} + 6n + 2)2^{n} H_{2n} +(4n + 3)2^{n}}{(2n^{2} + 3n + 1) H_{n} 2^{n} + (4n + 1)2^{n}}
= lim_{n→∞} \frac{p_{1}(n) H_{2n} ∑_{k=1}^{n} \frac{2^{k}}{k} + p_{2}(n) ∑_{k=1}^{n} \frac{2^{k}}{k} + p_{3}(n) H_{2n} 2^{n} + p_{4}(n)2^{n}}{p_{5}(n) H_{n} 2^{n} + p_{6}(n)2^{n}}  for some p_{i} with deg p_{i} ≤ 2
=^{l’H} lim_{n→∞} \frac{p_{1}(n) H_{2n} ∑_{k=1}^{n} \frac{2^{k}}{k} + p_{2}(n) ∑_{k=1}^{n} \frac{2^{k}}{k} + p_{3}(n) H_{2n} 2^{n} + p_{4}(n)2^{n}}{p_{5}(n) H_{n} 2^{n} + p_{6}(n)2^{n}}  for some p_{i} with deg p_{i} ≤ 5
=^{l’H} lim_{n→∞} \frac{p_{1}(n) H_{2n} ∑_{k=1}^{n} \frac{2^{k}}{k} + p_{2}(n) ∑_{k=1}^{n} \frac{2^{k}}{k} + p_{3}(n) H_{2n} 2^{n} + p_{4}(n)2^{n}}{p_{5}(n) H_{n} 2^{n} + p_{6}(n)2^{n}}  for some p_{i} with deg p_{i} ≤ 8
=^{l’H} lim_{n→∞} \frac{p_{1}(n) H_{2n} ∑_{k=1}^{n} \frac{2^{k}}{k} + p_{2}(n) ∑_{k=1}^{n} \frac{2^{k}}{k} + p_{3}(n) H_{2n} 2^{n} + p_{4}(n)2^{n}}{p_{5}(n) H_{n} 2^{n} + p_{6}(n)2^{n}}  for some p_{i} with deg p_{i} ≤ 11

• Continuation seems hopeless :-(

RISC-Linz 2003 Combinatorics Seminar Manuel Kauers Report on ISSAC Poster

Limits of Rational Functions

• How do we see that

lim_{n→∞} \frac{n^{3} + 2n^{2} − n + 5}{2n^{3} − 7n^{2} + n + 1} = \frac{1}{2} ?

• There are dominant terms – the others don’t contribute asymptotically:

lim_{n→∞} \frac{n^{3} + 2n^{2} − n + 5}{2n^{3} − 7n^{2} + n + 1} = lim_{n→∞} \frac{n^{3}}{2n^{3}} = lim_{n→∞} \frac{1}{2} = \frac{1}{2}.

• Idea: Extend this technique to the multivariate case

• Define dominant terms domT(·) such that

lim_{n→∞} \frac{a_{n}}{b_{n}} = lim_{n→∞} \frac{domT(a_{n})}{domT(b_{n})}

and domT(X) is “simpler” than X.

RISC-Linz 2003 Combinatorics Seminar

Manuel Kauers Report on ISSAC Poster

Dominant Terms

• Definition Let (a_{n}), (b_{n}) be sequences, and define

(a_{n}) ≺ (b_{n}) :⟺ lim_{n→∞} \frac{a_{n}}{b_{n}} = 0.

Say: (b_{n}) grows faster than (a_{n}).

• Definition

domT(a_{n}^{(1)} + a_{n}^{(2)} + ⋯ + a_{n}^{(r)}) = max_{i=1}^{r} a_{n}^{(i)}

where max is taken with respect to ≺.

• Example domT(n + H_{n} +n^{2} + 1) = n^{2} because

lim_{n→∞} n/ H_{n} = ∞ ⟹ n ≻ H_{n}
lim_{n→∞} n/n^{2} = 0 ⟹ n^{2} ≻ n
lim_{n→∞} n^{2}/1 = ∞ ⟹ n^{2} ≻ 1.

Dominant Terms II

• ≺ is not a strict order.

• What if max_{i} a_{n}^{(i)} doesn’t exist?

• A more general Definition

domT(a_{n} + b_{n}) := \{ \begin{matrix}a_{n} & if lim_{n→∞} b_{n}/a_{n} = 0 \\ b_{n} & if lim_{n→∞} a_{n}/b_{n} = 0 \\ (1 + \frac{1}{α})a_{n} & if lim_{n→∞} a_{n}/b_{n} = α ∉ \{0, −1, ±∞\} \\ FAIL & otherwise \end{matrix}

Recursive for a_{n}^{(1)} + a_{n}^{(2)} + ⋯ + a_{n}^{(r)}

• It’s clear that this definition also serves our purpose.

Towards an Algorithm

• INPUT: a_{n}

• OUTPUT: lim_{n→∞} a_{n}, or FAIL.

• check special cases

if a_{n} = p_{n}/q_{n} then p_{n} := domT(p_{n}) p_{n} := domT(q_{n}) if q_{n} → ∞ then

α := lim_{n→∞} \frac{Δp_{n}}{Δq_{n}}

else

α := lim_{n→∞} p_{n}/lim_{n→∞} q_{n}

fi return α

fi return FAIL

Towards an Algorithm – FAQ

• In l’Hospital: How to decide monotonicity? — By restriction of admissible functions

• How to decide a_{n} → ∞ ?

— By applying a bag of tricks

• If there are several ways to write a_{n} = p_{n}/q_{n} ? — Try them all, until one works

• Will this terminate?

— No, use breadth first search!

• This has exponential complexity!

— So what!

• Do you have implemented all that stuff? — Yes, in MAPLE

Manuel Kauers Report on ISSAC Poster

What about more interesting inputs? III

• Problem lim_{n→∞} \frac{n H_{2n} ∑_{k=1}^{n} \frac{2^{k}}{k}}{H_{n} 2^{n}} revisited.

• Step 1: l’Hospital because H_{n} 2^{n} → ∞ (n → ∞).

\frac{(\frac{3}{2} + 2n^{2} H_{2n} +3n H_{2n} + H_{2n} +2n^{2} + \frac{7}{2}n) ∑_{k=1}^{n} \frac{2^{k}}{k} + (4n^{2} + 6n + 2)2^{n} H_{2n} +(4n + 3)2^{n}}{(2n^{2} + 3n + 1) H_{n} 2^{n} + (4n + 1)2^{n}}

• Step 2: Reduction to dominant terms; cancellation

\frac{4 n^{2} 2^{n} H_{2n}}{2 n^{2} 2^{n} H_{n}} = \frac{2 H_{2n}}{H_{n}}

• Step 3: Recursion: l’Hospital because H_{n} → ∞ (n → ∞)

\frac{4n + 3}{2n + 1}

• Step 4: Reduction to dominant terms; cancellation

\frac{4n}{2n} = 2

RISC-Linz 2003 Combinatorics Seminar Manuel Kauers Report on ISSAC Poster

Examples Gallery

• lim_{n→∞} \frac{∑_{k=1}^{n} (3^{k} ∑_{i=1}^{k} \frac{H_{i}}{i})}{3^{n} H_{n}^{2}} = \frac{3}{4}  • lim_{n→∞} \frac{H_{n} ∑_{k=1}^{n} \frac{2^{k}}{k}}{n ∑_{k=1}^{n} \frac{2^{k} H_{k}}{k^{2}}} = 1  • lim_{n→∞} \frac{n^{3}( ∑_{k=1}^{n} \frac{2^{k}}{k^{2}})^{2}}{2^{n} ∑_{k=1}^{n} \frac{2^{k}}{k}} = 2
• lim_{n→∞} \frac{∑_{k=1}^{n} \binom{2k}{k}2^{k}}{\binom{2n}{n}2^{n}} = \frac{8}{7}  • lim_{n→∞} \frac{H_{n}^{2} ∑_{k=1}^{n} \frac{H_{k}}{k}}{n} = 0  • lim_{n→∞} H_{n}^{2}^{∑_{k=1}^{n} \frac{H_{k}}{k}} = \frac{1}{2}
• lim_{n→∞} \frac{∑_{k=1}^{n} \frac{k H_{k}}{k^{2}+1}}{n + H_{2n}^{2}} = 0  • lim_{n→∞} \frac{n! ∑_{k=1}^{n} \frac{2^{k}}{k}}{2^{n} ∑_{k=1}^{n} \frac{k!^{2}}{2^{k}}} = 0  • lim_{n→∞} ^{\begin{matrix}∑_{k=1}^{n} & \binom{3k}{k} & \binom{5k}{k} \\ \binom{3n}{n} & \binom{5n}{n} \end{matrix}} = \frac{84375}{83351}
• lim_{n→∞} \begin{aligned}& ∑_{k=1}^{n} & \frac{2^{k}}{k^{2}} & \binom{2k}{k} \\ ( & ∑_{k=1}^{n} & \frac{2^{k}}{k^{2}} & ) & ∑_{k=1}^{n} & \binom{2k}{k} \end{aligned} = \frac{3}{7}  • lim_{n→∞} \frac{∑_{k=1}^{2n} \frac{2^{k}k!}{k^{2}}}{( ∑_{k=1}^{n} \frac{4^{k}}{k^{2}}) ∑_{k=1}^{2n} k!} = \frac{3}{16}  • lim_{n→∞} \begin{matrix}∑_{k=1}^{n} & \binom{2k}{k} & \binom{3k}{k} \\ ( & ∑_{k=1}^{n} & \binom{2k}{k} & ) & ∑_{k=1}^{n} & \binom{3k}{k} \end{matrix} = \frac{69}{104}
• lim_{n→∞} ^{\begin{matrix}∑_{k=1}^{n} & \binom{2k}{k} & 2 \\ \binom{2n}{n} & 2 \end{matrix}} = \frac{16}{15}  • lim_{n→∞} H_{n}^{3}^{∑_{k=1}^{2n} \frac{H_{k}^{2}}{k}} = \frac{1}{3}  • lim_{n→∞} \frac{∑_{k=1}^{n} (k^{2} ∑_{i=1}^{k} \frac{2^{i}}{i})}{2^{n}n} = 4

RISC-Linz 2003 Combinatorics Seminar

Manuel Kauers Report on ISSAC Poster

“Counterexamples” Gallery

• ∑_{k=1}^{n} \frac{1}{k^{2}}  –  not of the form p_{n}/q_{n}
• 5/ ∑_{k=1}^{n} \frac{1}{k^{2}}  –  q_{n} ↛ ∞
• \frac{n ∑_{k=1}^{n} \frac{H_{k}}{k}}{H_{n}}  –  does not terminate:

lim_{n→∞} \frac{n ∑_{k=1}^{n} \frac{H_{k}}{k}}{H_{n}} =^{l’H} lim_{n→∞} (n ∑_{k=1}^{n} \frac{H_{k}}{k} + ∑_{k=1}^{n} \frac{H_{k}}{k} + n H_{n} + H_{n} +1)

What is the dominant term?

What now?

• Short term:

– Some hacking to improve the implementation – Perhaps AI-techniques for searchtree organisation – Comprehensive procedure for a_{n} → ∞

– Extended input class

• Medium- and Longterm: – Find more systematic approaches…

– Collect interesting examples