# Deriving a Closed-Form Solution of the Fibonacci Sequence using the Z-Transform

The Fibonacci sequence might be one of the most famous sequences in the field of mathmatics and computer science. Already high school students starting with programming classes compute the first few Fibonacci numbers with their programs using different iterative or recursive approaches. One reason for its popularity might be that the Fibonacci sequence is closely related to many other fields of math and physics, often in very astonishing ways which one might not expect. Usually, the Fibonacci sequence is defined in a recursive manner. Hence, in order to compute the n-th Fibonacci number all previous Fibonacci numbers have to be computed first. In this blog post we will derive an interesting closed-form solution to directly compute any arbitrary Fibonacci number without the necessity to obtain its predecessors first. Interestingly, we will solve this problem with the help of a tool – the so called Z-Transform – which is actually more common in the field of digital signal processing.

# Derivation of a Weighted Recursive Linear Least Squares Estimator

$$\let\vec\mathbf \def\myT{\mathsf{T}} \def\mydelta{\boldsymbol{\delta}} \def\matr#1{\mathbf #1}$$

In this post we derive an incremental version of the weighted least squares estimator, described in a previous blog post.

# Gaussian Distribution With a Diagonal Covariance Matrix

Often, it is convenient to use an alternative representation of a multivariate Gaussian distribution if it is known that the off-diagonals of the covariance matrix only play a minor role. In this case one can assume to have only a diagonal covariance matrix and one can estimate the mean and the variance in each dimension separately and describe the multivariate density function in terms of a product of univariate Gaussians. This is shown in the following.

# Conway's Game of Life

Conway’s Game of Life is a so called zero-player game designed by the British mathematician John Horton Conway in 1970. It only has a initial configuration which can be set by the player and then evolves without any further interactions with the game.

The rules are rather simple. Here is an excerpt from wikipedia.org:

The universe of the Game of Life is an infinite, two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, alive or dead, (or populated and unpopulated, respectively). Every cell interacts with its eight neighbors, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

1. Any live cell with fewer than two live neighbors dies, as if by underpopulation.
2. Any live cell with two or three live neighbors lives on to the next generation.
3. Any live cell with more than three live neighbors dies, as if by overpopulation.
4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed; births and deaths occur simultaneously, and the discrete moment at which this happens is sometimes called a tick. Each generation is a pure function of the preceding one. The rules continue to be applied repeatedly to create further generations.

In this post we will program the game in $R$ and look at a few results.

# Verifying Results based on Precision, Recall and False-Positive-Rate

Recently, I read a paper which reported quite impressive results on a time series anomaly detection task with several time series. The paper was already cited by many other researchers and the presented algorithm really seems to perform quite well. However, after doing some calculations, it appears like the results were presented in a way which is a little misleading and strange. But let us take a closer look.