Manuel Kauers Hagenberg, January 8, 2004 RISC-Linz

Analytic Combinatorics

Homework 10

Exercise 41 Using Mallinger’s package, compute a recurrence for the sequence (s(n))_{n=0}^{∞} where

s(n) = ∑_{k=0}^{n} \binom{n}{k}\binom{2k}{k}\frac{(−1)^{k}}{2^{k}}

along the guideline given in the lecture.

Consider y(x) = ∑_{n=0}^{∞} \binom{2k}{k}/2^{k}x^{k} and observe that

⟨x^{n}⟩\frac{1}{1 − x}y(\frac{x}{x − 1}) = \underbrace{∑_{k=0}^{n} \binom{n}{k}(−1)^{k} \underbrace{⟨x^{k}⟩y(x)}_{=:f(k)}}_{=s(n)}

by Euler’s transform. We use Mallinger’s package for converting a recurrence for f(k) into a recurrence for s(n). Because of the close analogy to the presentation in the lecture, we will omit explanatory comments.

In[1]:= << GeneratingFunctions.m GeneratingFunctions Package by Christian Mallinger — \begin{matrix}c \\ ◯ \end{matrix}RISC Linz — V 0.68 (07/17/03)

In[2]:= F [k ] = Binomial[2 ∗ k, k]; In[3]:= f[k + 1]/f[k] − F [k + 1]/F [k] // FullSimplify // Together // Numerator // Simplify

Out[3]= −(1 + 2k)f[k] + (1 + k)f[1 + k]

In[4]:= rec = % == 0; In[5]:= RE2DE[{rec, f[0] == 1, f[1] == 1}, f[k], y[x]]

Out[5]= {−y[x] − (−1 + 2x)y′[x] == 0, y[0] == 1}

In[6]:= ACompose[%, y[x] == x/(x − 1), y[x]]

CanAb::denom : Warning. The input equation will be multiplied by its denominator

Out[6]= {y[x] − (−1 + x^{2})y′[x] == 0, y[0] == 1}

In[7]:= DECauchy[%, y[x] == 1/(1 − x), y[x]]

CanAb::denom : Warning. The input equation will be multiplied by its denominator

Out[7]= {x y[x] + (−1 + x^{2})y′[x] == 0, y[0] == 1}

In[8]:= DE2RE[%, y[x], s[n]]

Out[8]= {(1 + n)s[n] + (−2 − n)s[2 + n] == 0, s[0] == 1, s[1] == 0} This is the expected output.

Exercise 42 Let y(x) ∈ ℂ[[x]] \ {0}. Show: If y′(x)/y(x) is algebraic, then 1/y(x) is D-finite.

See Stanley, Ex. 6.60, p. 247 (Solution on p. 281). [Sorry for being lazy.]

Exercise 43 Show that

a) y_{1}(x) = 1/ cos x and

b) y_{2}(x) = \sqrt{log(1 + x^{2})}

are not D-finite.

Ad a) Put y(x) = cos x. Then y′(x)/y(x) = − tan x is not algebraic, and hence 1/y(x) = 1/ cos x is not D-finite.

Ad b) Suppose otherwise. Then, writing

y(x) = \frac{1}{\sqrt{log(1 + x^{2})}},

we get by the theorem that

\frac{y′(x)}{y(x)} = −\frac{x}{1 + x^{2}} \frac{1}{log(1 + x^{2})}

is algebraic. Then in particular 1/ log(1 + x^{2}) is algebraic, and so there exist polynomials Q_{0}(x), …, Q_{m}(x), Q_{m}(x) ≠ 0 with

∑_{k=0}^{m} \frac{Q_{k}(x)}{log(1 + x^{2})^{k}} = 0.

Clearing denominators gives

∑_{k=0}^{m} Q_{k}(x) log(1 + x^{2})^{m−k} = 0.  (1)

Without loss of generality, we may assume Q_{m}(0) ≠ 0, for otherwise, we can replace (1) by

∑_{k=0}^{m} Q′_{k}(x) log(1 + x^{2})^{m−k} + Q_{k}(x)2x(m − k) log(1 + x^{2})^{m−k−1}

until Q_{m}(0) ≠ 0 which must ultimately happen because Q_{m} ≠ 0. Now,

0 = ∑_{k=0}^{m} Q_{k}(x) log(1 + x^{2})^{m−k} = Q_{m}(x) + \underbrace{log(1 + x^{2})}_{→0} \underbrace{∑_{k=0}^{m−1} Q_{k}(x) log(1 + x^{2})^{m−k−1}}_{continous}

⟶^{x→0} Q_{m}(0)

leads to the desired contradiction.