Manuel Kauers Hagenberg, October 29, 2003 RISC-Linz

Analytic Combinatorics

Homework 4

Exercise 10 a) Complete the generating function proof of Binet’s identity which was outlined in the lecture

b) Derive Binet’s identity by the general theorem on solving linear C-finite recurrences.

c) Prove f_{n} ∼ \frac{1}{\sqrt{5}}r_{+}^{n+1} in the notation of the lecture.

d) Prove f_{n} = ⌊\frac{1}{\sqrt{5}}r_{+}^{n+1}⌋ in the notation of the lecture.

Ad a) We have seen in the lecture that

f(x) = \frac{1}{1 − x − x^{2}}

is a generating functions for the Fibonacci numbers f_{n} and that 1 − x − x^{2} = (1 − r_{+}x)(1 − r_{−}x) where

r_{+} = \frac{1}{2}(1 + \sqrt{5}), r_{−} = \frac{1}{2}(1 − \sqrt{5}).

We compute a partial fraction decomposition for f(x).

f(x) = \frac{1}{1 − x − x^{2}} = \frac{α}{1 − r_{+}x} + \frac{β}{1 − r_{+}x}
α = \frac{1 − xr_{−}}{1 − x − x^{2}} |_{x=1/r_{−}} = \frac{1}{10}(\sqrt{5} + 1)\sqrt{5}

β = \frac{1 − xr_{+}}{1 − x − x^{2}} |_{x=1/r_{+}} = \frac{1}{10}(\sqrt{5} − 1)\sqrt{5}

This representation of f does now admit the application of the geometric series.

f(x) = \frac{α}{1 − r_{+}x} + \frac{β}{1 − r_{+}x} = α ∑_{n=0}^{∞} r_{+}^{n}x^{n} + β ∑_{n=0}^{∞} r_{−}^{n}x^{n}.

Comparing coefficients gives

f_{n} = αr_{+}^{n} + βr_{−}^{n} = \frac{1}{\sqrt{5}} \frac{1 + \sqrt{5}}{2}r_{+}^{n} − \frac{1}{\sqrt{5}} \frac{1 − \sqrt{5}}{2}r_{−}^{n} = \frac{1}{\sqrt{5}}(r_{+}^{n+1} − r_{−}^{n+1}),

as desired.

Ad b) By definition, the Fibonacci sequence forms a solution of the C-finite recurrence

f_{n+2} − f_{n+1} − f_{n} = 0 (n ∈ ℕ).

According to the theorem of Exercise 9 (previous sheet) the solutions to this recurrence are given precisely by linear combinations of {r_{+}^{n}}_{n}, {r_{−}^{n}}_{n} where r_{+}, r_{−} are the roots of the polynomial X^{2} − X − 1, their values are as in part a).

We find the linear combination from the initial conditions of {f_{n}}_{n}.

f_{0} = 1 = αr_{+}^{0} + βr_{−}^{0} = α + β
f_{1} = 1 = αr_{+}^{1} + βr_{−}^{1} = αr_{+} + βr_{−}.

This linear system has the solution

α = \frac{1}{2} + \frac{1}{10} \sqrt{5}, β = \frac{1}{2} − \frac{1}{10} \sqrt{5},

and it follows that

f_{n} = (\frac{1}{2} + \frac{1}{10} \sqrt{5})r_{+}^{n} + (\frac{1}{2} − \frac{1}{10} \sqrt{5})r_{−}^{n}

= \frac{1}{\sqrt{5}}(\frac{1}{2} \sqrt{5} + \frac{1}{2})r_{+}^{n} + \frac{1}{\sqrt{5}}(\frac{1}{2} \sqrt{5} − \frac{1}{2})r_{−}^{n}

= \frac{1}{\sqrt{5}}(r_{+}^{n+1} − r_{−}^{n+1}),

as expected. Ad c) By |r_{−}| = \frac{1}{2}|1 − \sqrt{5}| = \frac{1}{2}(\sqrt{5} − 1) < \frac{1}{2} \sqrt{5} we get |r_{−}/\sqrt{5}| < 1 and therefore

f_{n} = \frac{1}{\sqrt{5}}(r_{+}^{n+1} + r_{−}^{n+1}) = \frac{1}{\sqrt{5}}r_{+}^{n+1} + o(1).

The claim follows immediately. Ad d) This is not true:

⌊\frac{r_{+}^{0}}{\sqrt{5}}⌋ = 0 ≠ 1 = f_{0}.

However, from part c) we know

f_{n} = \frac{r_{+}^{n+1}}{\sqrt{5}} + o(1),  i.e.  f_{n} − \frac{r_{+}^{n+1}}{\sqrt{5}} ⟶^{n→∞} 0.

It is also immediate that this convergence is monotonous. Noting further that |f_{0} − r_{+}^{1}/\sqrt{5}| < 0.3 (which can easily be checked numerically), we conclude that f_{n} is the closest integer to r_{+}^{n+1}/\sqrt{5}. This is in accordance with (6.124) of [GKP89].

Exercise 11 Look up Strassen’s algorithm. Done. But I will not reproduce it here in order to save time and paper.

Exercise 12 Prove

\binom{a}{k} = \binom{a − 1}{k} + \binom{a − 1}{k − 1}

for a ∈ ℂ and k ∈ ℤ. Let a ∈ ℂ and k ∈ ℤ. We start a straightforward computation:

\binom{a − 1}{k} = \frac{(a − 1)(a − 2) ⋯ (a − k + 1)(a − k)}{k!}
\binom{a − 1}{k − 1} = \frac{(a − 1)(a − 2) … (a − k + 1) k}{(k − 1)! k}
\binom{a − 1}{k} + \binom{a − 1}{k − 1} = \frac{(a − 1)(a − 2) … (a − k + 1)((a − k) + k)}{k!} = \binom{a}{k}.

If k ∉ ℤ, then k − 1 ∉ ℤ and so

\binom{a}{k} = \binom{a − 1}{k} = \binom{a − 1}{k − 1} = 0,

so the identity also holds for k ∉ ℤ.

Exercise 13 Prove that for each given polynomial f(k) there exists a polynomial g(k) such that f(k) = g(k + 1) − g(k) for all integers k.

Let f_{1}, f_{2} be arbitrary polynomials and α a constant. If g_{1}, g_{2} are polynomials with the desired property for f_{1}, f_{2}, respectively, then g_{1} + g_{2} is such a polynomial for f_{1} + f_{2} and αg_{1} is such a polynomial for αf_{1}. Therefore, it suffices to show the claim for f(k) = k^{n} (n ∈ ℕ_{0}).

Ansatz. Let g(k) = ∑_{i=0}^{n+1} γ_{i}k^{i} and show that there are coefficients γ_{i} such that

g(k + 1) − g(k) = ∑_{i=0}^{n+1} γ_{i}((k + 1)^{i} − k^{i}) = k^{n}.

As the leading terms on the left hand side are easily seen to cancel out, we are left with a linear system of n + 1 equations in n + 2 unknowns. The homogenous part of the system must have a nontrivial solution. Observe that the homogenous system has the form

A · x = (1, 0, 0, …, 0)^{T}

and this is only unsolvable if A = 0 which is not the case. This completes the proof.