Manuel Kauers Hagenberg, October 24, 2003 RISC-Linz

Analytic Combinatorics

Homework 3

Exercise 4 Solve the reduced recurrence

F (0) = 0, (n + 1)F (n + 1) − (n + 2)F (n) = 2n (n ≥ 0)

by means of generating functions.

Let

a(z) = ∑_{n=0}^{∞}(n + 1)F (n + 1)z^{n},  b(z) = ∑_{n=0}^{∞}(n + 2)F (n)z^{n},  c(z) = ∑_{n=0}^{∞} nz^{n}

and f(z) = ∑_{n=0}^{∞} F (n)z^{n}. We want to write the functional equation

a(z) − b(z) = 2c(z)

in a form which does only depend on z, f(z), f′(z), but not on a, b, c. We will make free usage of F (0) = 0 when fiddeling with indizes.

(1) Consider a(z). We have

a(z) = ∑_{n=0}^{∞}(n + 1)F (n + 1)z^{n} = ∑_{n=1}^{∞}(n + 1)F (n + 1)z^{n} = ∑_{n=0}^{∞} nF (n)z^{n−1}
∫ a(z) dz = ∑_{n=0}^{∞} ∫ nF (n)z^{n−1} dz = ∑_{n=0}^{∞} F (n)z^{n} = f(z),

and therefore a(z) = f′(z).

(2) Consider b(z). We have

b(z) = ∑_{n=0}^{∞}(n + 2)F (n)z^{n} = \frac{1}{z} \underbrace{∑_{n=0}^{∞}(n + 2)F (n)z^{n+1}}_{=:b̃(z)}

∫ b̃(z) dz = ∑_{n=0}^{∞} ∫ (n + 2)F (n)z^{n+1} dz = ∑_{n=0}^{∞} F (n)z^{n+2} = z^{2}f(z)

and therefore b̃(z) = 2xf(z) + z^{2}f′(z), and therefore b(z) = 2f(z) + zf′(z).

(3) Consider c(z). We have

c(z) = ∑_{n=0}^{∞} nz^{n} = z \underbrace{∑_{n=0}^{∞} nz^{n−1}}_{=:c̃(z)}

∫ c̃(z) dz = ∑_{n=0}^{∞} ∫ nz^{n−1} dz = ∑_{n=0}^{∞} z^{n} = \frac{1}{1 − z}

and therefore

c_{0}(z) = \frac{1}{(z − 1)^{2}} ,  c(z) = \frac{z}{(z − 1)^{2}} .

Putting things together, we obtain an ordinary differential equation for f:

a(z) − b(z) = 2c(z)
f′(z) − (2f(z) + zf′(z)) = 2\frac{z}{(z − 1)^{2}}
(z − 1)^{3}f′(z) − 2(z − 1)^{2}f(z) − 2z = 0.

Together with the initial condition f(0) = 0, this is the same equation which was obtained in the lecture from the original recurrence of F, so the rest of works literally as there. We only repeat the final result:

F (n) = −2n + 2 ∑_{k=0}^{n} H_{k}.

Exercise 5 How many slices of Pizza can a person maximally obtain by making n straight cuts with a pizza knife. Call this number L_{n} (n ≥ 0).

First consider some initial values to get a feeling.

n  0  1  2  3  4  5

Pizza

L_{n}  1  2  4  7  11  16

What about general n? Suppose that n lines can cut the plane into L_{n} sections. The (n + 1)st line can have at most n intersections with the lines already there, every intersection point can be associated to a section which is cut into two — except for “the first.” We find that there must be n + 1 new sections, i.e.,

L_{n+1} = L_{n} + (n + 1), L_{0} = 1.

This fits well with the table. This recurrence admits immediately a closed form:

L_{n} = 1 + ∑_{k=1}^{n} k = 1 + \frac{1}{2}n(n + 1) = \frac{1}{2}n^{2} + \frac{1}{2}n + 1.

Exercise 6 n people, labeled 1, …, n, are sitting around a circular table. Starting from person 1, eliminate every second person until only one person survives. Determine the number J(n) of the surviver.

We easily find the initial values of J(n) by actually playing the game.

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ J(n) & 1 & 1 & 3 & 1 & 3 & 5 & 7 & 1 & 3 & 5 & 7 \end{matrix}

No pattern appearent. Consider the general case, and distinguish odd and even numbers.

(1) n = 2k. In the first round, all people with even labels are eliminated. The people 1, 3, …, n − 1 survive. The game proceeds recursively. By relabelling, we find

J(2k) = 2J(k) − 1.

(2) n = 2k + 1. In the first round, all people with even labels are eliminated. But the next eliminated person is 1, because n is odd. The survivers are 3, 5, …, n. The game proceeds recursively on them. By relabelling, we find

J(2k + 1) = 2J(n) + 1.

This looks like a mistake at first glance, because the two formulas cannot be unified, but the initial values fit well with the result. Seeking a closed form solution, we query Sloane with 1, 1, 3, 1, 3, 5, 7, …, we find indeed the Josephus numbers, but we don’t find a closed form. We guess that there is none.

Exercise 7 Use the computer for guessing.

See the solution to Exercise 8 a)

Exercise 8 Apply Methods 1–4 to the recurrence a_{n+1} = 2a_{n} +n (n ≥ 0), a_{0} = 1.

a) Guess and prove Suppose we are only given the initial values of a_{n}:

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ a_{n} & 1 & 2 & 5 & 12 & 27 & 58 & 121 \end{matrix}

(i) Guessing with Mathematica

In[1]:= << "GeneratingFunctions.m"
        Generating Functions Package by Christian Mallinger -- (c)
        RISC Linz - V 0.68 (07/17/03)
In[2]:= GuessRecurrenceEquation[{1,2,5,12,27,58,121}, a[n]]
        Guess::shortin : The input list is too short.
        Guess::shortin : The input list is too short.
Out[2]= FAIL
In[3]:= GuessRecurrenceEquation[{1,2,5,12,27,58,121,248,503,1014,2037,4084}, a[n]]
Out[3]= {{2(1+n)a[n] + (-1-3n)a[1+n] + na[2+n] == 0,
           a[0] == 1, a[1] == 2, a[2] == 5}, ogf}

In readable notation, the guessed recurrence is

a_{n+2} = \frac{3n + 1}{n}a_{n+1} − 2\frac{n + 1}{n}a_{n}, a_{0} = 1, a_{1} = 2, a_{2} = 5.

That’s quite a mess, and the last initial value is superfluous. However, the guessed recurrence is correct. (ii) Guessing with Maple

> with(gfun):
> listtorec([1,2,5,12,27,58,121], a(n));
  [{(2n+6)a(n+3)+(-18-7n)a(2+n)+(12+10n)a(n+1)+(-6-7n)a(n),a(0)=1,a(1)=2,a(2)=5}, ogf]

This guess looks even worse:

a_{n+3} = \frac{7n + 18}{2n + 6}a_{n+2} − \frac{5n + 6}{n + 3}a_{n+1} + \frac{7n + 6}{2n + 6}a_{n}, a_{0} = 1, a_{1} = 2, a_{2} = 5.

Plugging in the “real” recurrence, it turns out that the guess is wrong. We try again with additional initial values

> listtorec([1,2,5,12,27,58,121,248,503,1014,2037,4084], a(n));
  [{(-2n-2)a(n)+(3n+1)a(n+1)-a(2+n)n, a(0)=1,a(1)=2,a(2)=5},ogf]

In standard notation, this is

a_{n+2} = −\frac{3n + 1}{n}a_{n+1} + 2\frac{n + 1}{n}a_{n}, a_{0} = 1, a_{1} = 2, a_{2} = 5.

This is, up to a sign, the same result as we obtained before in Mathematica. It turns out to be correct as well. (iii) Guessing with Sloane Entering the above initial values gives the following output, including the recurrence a_{n+1} = 2a_{n} + n, a_{0} = 1 and the closed form a_{n} = 2^{n} − n.

ID Number: A000325
URL:       http://www.research.att.com/projects/OEIS?Anum=A000325
Sequence:  1,1,2,5,12,27,58,121,248,503,1014,2037,4084,8179,16370,
           32753,65520,131055,262126,524269,1048556,2097131,4194282,
           8388585,16777192,33554407,67108838,134217701,268435428,
           536870883
Name:      2^n - n.
Comments:  Comment from Axel Kohnert (Axel.Kohnert(AT)uni-bayreuth.de): This
              is the number of permutations of degree n with at most one fall; called
              Grassmannian permutations by L. and S.
References Lascoux and Schutzenberger: Schubert polynomials and the Littlewood
              Richardson rule, Letters in Math. Physics 10 (1985) 111-124.
Formula:   a(n+1) = 2*a(n) + n.
           a(n+1) = 2*a(n) + n - 1, a(0) = 1. - Reinhard Zumkeller
              (reinhard.zumkeller(AT)lhsystems.com), Apr 12 2003
           Binomial transform of 1,0,1,1,1,.... The sequence starting
              1,2,5,...has a(n)=1+n+2*sum{k=2..n,binom(n,k)}=2^(n+1)-n-1.
              This is the binomial transform of 1,1,2,2,2,2,....
              a(n)=1+sum{k=2..n, C(n,k)}. - Paul Barry (pbarry(AT)wit.ie), Jun 06
              2003
Maple:     A000325:=proc(n) option remember; if n <=1 then n+1 else
              2*A000325(n-1)+n-1; fi; end;
See also:  Sequence in context: A073778 A033490 A078410 this_sequence A076878
              A083378 A000102
           Adjacent sequences: A000322 A000323 A000324 this_sequence A000326
              A000327 A000328
Keywords:  nonn
Offset:    0
Author(s): Rosario Salamone [ Rosario.Salamone(AT)risc.uni-linz.ac.at ]

b) Imitate analysis The homogenous equation

h_{n+1} = 2h_{n} (n ≥ 0)

does obviously have the solution h_{n} = h_{0}2^{n} for some constant h_{0}. Apply variation of the constant: set a_{n} = c_{n}2^{n} with c_{0} = 1 (follows from the initial condition on a_{n}). Plug this into the original recurrence and obtain

c_{n+1}2^{n+1} = c_{n}2^{n+1} + n
c_{n+1} − c_{n} = \frac{1}{2}n2^{−n}
∑_{k=0}^{n−1}(c_{k+1} − c_{k}) = \frac{1}{2} ∑_{k=0}^{n−1} k2^{−k} = \frac{1}{2}( − 2(\frac{1}{2})^{n}n − 2(\frac{1}{2})^{n} + 2)
c_{n} = c_{0} + \frac{1}{2}( − 2(\frac{1}{2})^{n}n − 2(\frac{1}{2})^{n} + 2)
= 2 − (\frac{1}{2})^{n}n − (\frac{1}{2})^{n}
⟹  a_{n} = (2 − (\frac{1}{2})^{n}n − (\frac{1}{2})^{n})2^{n}
= 2^{n+1} − (n + 1).

c) Generating functions

Put a(z) = ∑_{n=0}^{∞} a_{n}z^{n}. Then

∑_{n=0}^{∞} a_{n+1}z^{n} = ∑_{n=1}^{∞} a_{n}z^{n−1} = \frac{1}{z} ∑_{n=1}^{∞} a_{n}z^{n} = \frac{1}{z}( ∑_{n=0}^{∞} a_{n}z^{n} − 1) = \frac{1}{z}(a(z) − 1),

and we have shown in an earlier Exercise (Ex. 4, page 1) that ∑_{n=0}^{∞} nz^{n} = \frac{z}{(z−1)^{2}} .

The recurrence yields

\frac{1}{z}(a(z) − 1) = 2a(z) + \frac{z}{(z − 1)^{2}}
a(z) = −\frac{2z^{2} − 2z + 1}{2z^{3} − 5z^{2} + 4z − 1} = 2\frac{1}{1 − 2z} − \frac{1}{(z − 1)^{2}}

= 2 ∑_{n=0}^{∞} 2^{n}z^{n} − ∑_{n=0}^{∞}(n + 1)z^{n}.

Comparing coefficients, we obtain a_{n} = 2^{n+1} − (n + 1).

d) Linear recurrences with constant coefficients The given recurrence has to be made homogenous. We apply Δ^{2} to the recurrence, because the homogenous part is a polynomial of degree 1 and one Δ does not suffice to kill it. We obtain

Δ^{2}(a_{n+1} − 2a_{n} − n) = a_{n+3} − 4a_{n+2} + 5a_{n+1} − 2a_{n} = 0.

The polynomial X^{3} − 4X^{2} + 5X − 2 factors into (X − 2)(X − 1)^{2}, so the solution has the form

a_{n} = α2^{n} + β + nγ.

By plugging in three initial values, we can determine α, β, γ from the linear system

(n = 0) 1 = α + β
(n = 1) 2 = α2 + β + γ
(n = 2) 5 = α4 + β + 2γ

The unique solution is (α, β, γ) = (2, −1, −1), and we conclude

a_{n} = 2^{n+1} − (n + 1) (n ∈ ℕ).

Exercise 9 Prove: The sequences f: ℕ → ℂ satisfying the recurrence

α_{r}f(n + r) + α_{r−1}f(n + r − 1) + ⋯ + α_{0}f(n) = 0 (α_{i} ∈ ℂ, α_{r} ≠ 0)

are precisely the linear combinations of the sequences

{c_{1}^{n}}_{n}, {nc_{1}^{n}}_{n}, {n(n − 1)c_{1}^{n}}_{n}, …, {n(n − 1) … (n − i_{1} + 1)c_{1}^{n}}_{n}
{c_{2}^{n}}_{n}, {nc_{2}^{n}}_{n}, {n(n − 1)c_{2}^{n}}_{n}, …, {n(n − 1) … (n − i_{1} + 1)c_{2}^{n}}_{n}
⋮
{c_{k}^{n}}_{n}, {nc_{k}^{n}}_{n}, {n(n − 1)c_{k}^{n}}_{n}, …, {n(n − 1) … (n − i_{k} + 1)c_{k}^{n}}_{n}

with c_{1}, …, c_{k} ∈ ℂ, i_{1}, …, i_{k} ∈ ℕ such that

p(X) := α_{r}X^{r} + α_{r−1}X^{r−1} + ⋯ + α_{0} = α_{r}(X − c_{1})^{i_{1}}(X − c_{2})^{i_{2}} ⋯ (X − c_{k})^{i_{k}}.

First show that the listed sequences are indeed solutions. For f(n) = c^{n}, we have

α_{r}f(n + r) + ⋯ + α_{0}f(n) = 0
⟺  α_{r}c^{n+r} + ⋯ + α_{0}c^{n} = 0
⟺  c^{n}p(c) = 0.

This is indeed true when c is a root of p. Now consider f(n) = nc^{n} for a double root c of p. Note that as c is a double root, it is also a root of p′, the derivative of p. We compute:

α_{r}f(n + r) + ⋯ + α_{0}f(n) = 0
⟺  α_{r}(n + r)c^{n+r} + ⋯ + α_{0}nc^{n} = 0
⟺ (α_{r}rc^{r−1} + ⋯ + α_{1})c^{n+1} + (α_{r}c^{r} + ⋯ + α_{0})nc^{n} = 0
⟺  p′(c)c^{n+1} + p(c)nc^{n} = 0

The latter is true as c is a double root of p. Similar arguments show the correctness of the other solutions. Obviously, linear combinations of solutions are solutions. It remains to show that there are no other solutions, and that the solutions we already know are linearly independent. We refer to the literature for that.