Generating Function for Fibonacci Sequence

We seek closed form for the power series \sum_{n=0}^\infty F_nz^n, where F_0 = 1, F_1 = 1 and F_{n+2} = F_{n+1} + F_n. First we note that the ratio test yields

\lim_{n\rightarrow\infty}\frac{F_{n+1}}{F_n}|z| = \varphi |z|, where \varphi = \frac{1+\sqrt{5}}{2} is the golden ratio. Thus the series converges on the region of the complex plane where |z| < \frac{1}{\varphi}. Now let the power series be denoted by F(z), and note that

F(z) - zF(z) - z^2F(z) = 1 + \sum_{n=0}^\infty (F_{n+2}-F_{n+1}-F_n)z^{n+2} = 1

and so F(z) = \frac{1}{1-z-z^2}. It seems so unlikely, before you know better at least, that things like that can be done. Why should it be that the nth Fibonacci number is given by \frac{1}{2\pi i}\oint\frac{1}{z^{n+1}(1-z-z^2)}dz, the integral along some closed contour in the complex plane of a function that otherwise seems unrelated. That’s maths!


On Complex vs Real Differentiability

Once upon a time I was confused about what really made a holomorphic function different from a function on \mathbb{R}^2 which is differentiable in the real sense. I mean obviously I knew how they were different but I wanted to put it in a context that was more meaningful for me, and after some thinking I thought the following and was satisfied:

Let’s cover some definitions; it’s likely I’ll write these classic definitions in more detail in later posts. Let f:\mathbb{C}\rightarrow\mathbb{C} be a complex function and let z_0 be a complex number. f is called (complex) differentiable at z_0 if the limit

f'(z_0) = \lim_{z\rightarrow z_0}\frac{f(z) - f(z_0)}{z-z_0}

exists, where the limit is taken along whatever path you like. The function f is differentiable on a subset A\subset\mathbb{C} if it is differentiable for all z_0\in A. Now a complex number can be written as z = x+iy, where x,y\in\mathbb{R}, and a complex function can be written as f(z=x+iy) = u(x,y)+iv(x,y) where u and v are both functions from \mathbb{R}^2 to \mathbb{R}. As \mathbb{R}-vector spaces, \mathbb{C} and \mathbb{R}^2 are isomorphic and we can think of f as a function f:\mathbb{R}^2\rightarrow\mathbb{R}^2 given by

(x,y)\mapsto (u(x,y),v(x,y)).

Now we it can be said that a complex function is complex differentiable if and only if it is differentiable in the real sense (i.e. all partial derivatives of u and v exist and are continuous) and u and v satisfy the Cauchy-Riemann equations (\frac{\partial u}{\partial x} = \frac{\partial v}{\partial y} and \frac{\partial v}{\partial x} = -\frac{\partial u}{\partial y}).

This observation is well known and does a good job of contrasting the two senses of differentiability, but I wanted to know the answer to “why is the derivative of the real version of the function a linear transformation (given by the Jacobian matrix) but the derivative of the complex version another complex function?” The answer to that is obvious in hindsight, but I was happy when I went from not knowing to knowing so I thought I better recount it here. The trick is, of course, that we construct a field isomorphism (which I’ll call \varphi) from \mathbb{C} into \mathrm{M}_2(\mathbb{R}) (the ring of 2 by 2 matrices with real entries) given by

\varphi(z) = \begin{pmatrix} \mathrm{Re}z & -\mathrm{Im}z \\ \mathrm{Im}z& \mathrm{Re}z \end{pmatrix}.

Now taking the derivative  of f gives us a function \mathrm{D}f:\mathbb{R}^2\rightarrow\mathrm{M}_2(\mathbb{R}), but the Cauchy-Riemann equations mean that if f is complex differentiable, then \mathrm{D}f(\mathbb{R}^2) \subset \varphi(\mathbb{C})\subset\mathrm{M}_2(\mathbb{R}). So in that case we can think of \mathrm{D}f as a function from \mathbb{R}^2\cong\mathbb{C} to \varphi(\mathbb{C})\cong\mathbb{C}, and so my question is resolved! The real version of the function is complex differentiable precisely when the Jacobian matrix can be identified with a complex function through the isomorphism \varphi.