Golden ratio and Fibonacci


I’m currently doing a course on linear algebra, and while working on a hand-in, I discovered this neat proof that the Fibonacci sequence grows exponentially.

Definition: Define two sequences:

  1. a_1 = 1, a_2 = 3, \text{ and } a_n = a_{n-1} + a_{n-2} \text{ for } n>2
  2. b_1 = 1, b_2 = 1, \text{ and } b_n = b_{n-1} + b_{n-2} \text{ for } n>2

Notice that b corresponds to the Fibonacci sequence, and a corresponds to the Lucas numbers, first index truncated.

Lemma 1: For all k>0

  1. a_k = \frac{1}{2} \left ( a_{k-1} + 5\cdot b_{k-1} \right )
  2. b_k = \frac{1}{2} \left ( a_{k-1} + b_{k-1} \right )

Proof. Shown only for 1.1, the proof is similar for 1.2. Proven using strong induction on k.

  • Base-case: 
    Notice that \frac{1}{2} \left ( a_{0} + 5\cdot b_{0} \right ) = \frac{1}{2} \left ( 1 + 5\cdot 1 \right ) = \frac{1}{2} \left ( 6 \right ) = 3 = a_1.
    Which is what we wanted to show.
  • Induction: 
    We see a_k = a_{k-1} + a_{k-2}, by definition.
    We apply the induction hypothesis on k-1, and k-2 to get: a_k = \frac{1}{2} \left ( a_{k-2} + 5\cdot b_{k-2} \right ) + \frac{1}{2} \left ( a_{k-3} + 5\cdot b_{k-3} \right ). We use the definition of a_k and b_k, and get
    a_k = \frac{1}{2} \left ( a_{k-1} + 5\cdot b_{k-1} \right ). Which is what we wanted to show. \blacksquare.

Lemma 2: For all k>0\phi^k = \frac{1}{2} a_k + \frac{1}{2} b_k \cdot \sqrt{5}.

Proof. We prove this lemma using induction on k.

  • Base-case:
    We see that, \frac{1}{2} a_1 + \frac{1}{2} b_1 \cdot \sqrt{5} = \frac{1}{2} 1 + \frac{1}{2} 1 \cdot \sqrt{5} = \frac{1}{2} \left(1 + \sqrt{5} \right) = \phi. Which is what we wanted to show.
  • Induction step:
    We get \phi^k = \phi \cdot \phi^{k-1} = \frac{1}{2}(1+\sqrt{5})\cdot \left( \frac{1}{2} a_{k-1} + \frac{1}{2} b_{k-1} \cdot \sqrt{5} \right), using the induction hypothesis. Multiplying, we get \phi^k = \frac{1}{2} \left ( \frac{1}{2} \left ( a_{k-1} + 5 b_{k-1} \right ) \right ) + \frac{1}{2} \left ( \frac{1}{2} \left ( a_{k-1} + b_{k-1} \right ) \right ) \cdot \sqrt{5}. Using lemma 2, we find \phi^k = \frac{1}{2} a_k + \frac{1}{2} b_k \cdot \sqrt{5}, which is what we wanted to show. \blacksquare.

Now for the interesting part of this article:

Theorem: b_n = \Theta(\phi^n).

Proof. We split the proof into two parts; first proving that b_n = O(\phi^n), then proving b_n = \Omega(\phi^n).

  • b_n = \Omega(\phi^n).
    We see that \phi^n < \frac{1}{2} a_n \cdot \sqrt{5} + \frac{1}{2} b_n \cdot \sqrt{5}, because of lemma 2. Because of lemma 1.2, we have b_n = \frac{1}{2} a_n + \frac{1}{2} b_n, so we get \phi^n < b_{n+1} \cdot \sqrt{5}. This implies that b_n = \Omega(\phi^n).
  • b_n = O(\phi^n).
    We see that \phi^n > \frac{1}{2} b_n because of lemma 2, which implies that b_n = O(\phi^n).

Because b_n = O(\phi^n), and b_n = \Omega(\phi^n), we have b_n = \Theta(\phi^n). That is, the Fibonacci sequence grows exponentially, with base \phi. \blacksquare.

Advertisements

Calkin-Wilf Fractals


Suppose we have two natural numbers i,j. Define a sequence a_0 = i, a_1 = j and a_n = |a_{n-1} - a_{n-2}|. That is, we start with two initial values, and repeatedly subtract the smallest value from the largest value. Since i,j \geq 0, we know that a_n \geq 0 for all n.

Eventually, we will reach the cycle \ldots 1, 1, 0, 1, 1, 0 \ldots no matter our choice of i,j (to see why, consider the termination function \mu(i,j)=i+j and the invariant that any term must be positive).

Define

\text{chainLength}(i,j) = \text{largest } n \text{ such that } a_n \notin \{1, 0\}

We can now make pretty pictures. For each pixel (x,y) color pixel by \text{chainLength}(x,y) which can be calculated using a simple recursive procedure:

int chainLength(int x, int y){
 if(x == y || x==0 || y==0)
     return 0;
 if(x>y)
     return 1+chainLength(x-y,y);
 else
     return 1+chainLength(x,y-x);
 }

calkinwilf

Generated using the DELTA library.

Connection to Calkin-Wilf trees

The Calkin-Wilf tree is an infinite binary recursive tree, where the root node is defined as 1/1, and every node a/b has a left child \dfrac{a+b}{b} and right child \dfrac{a}{a+b}.

 

capture

The Calkin-Wilf tree is useful because it allows us to define a bijection between the natural numbers and the rational numbers, which can be used to show that the rational numbers are a countably infinite set.

Notice that if a node x/y is a left child, then x>y, and if it’s a right child then y > x. This allows us to determine the parent node of a given node.

If for a given node x>y then we know it was the left child of its parent. So we know its parent is (x-y) / y. Similarly, if y>x, then its parent is x/(y-x). Notice that at each step, we subtract the smaller number from the larger number, and we terminate the procedure when we reach the fraction 1/1.

Going back to a_n, we could interpret a pixel (x,y) as the rational number x/y. The recursive sequence \text{chainLength}(x,y) would then be equivalent to the depth of the node $latex x/y$ in the Calkin-Wilf tree.

Keep in mind that the Calkin-Wilf tree only contains rational numbers in the lowest common term, so the node 2/2 does not exist in the Calkin-Wilf tree. To circumvent this issue, we convert our input node to the equivalent rational number in lowest common terms.

Incendium – HTML 5 App


fractal22

I just realized I have had this app up for a while on my github.io without posting it here. Anyway, I made an HTML5 app which implements the algorithm detailed in my previous post on fractal animations.

Moving the mouse around on the screen changes two different parameters, with each point P corresponding to a unique configuration.

http://ssodelta.github.io/incendium/

It is written for Google Chrome, and is known to act weird on Firefox sometimes. It may also crash, but just restart the page (sry).

AIArena – Bot Tournament


AIArena is a tournament where contestants write scripts for bots which battle each other in a virtual arena. I have written a dynamic web application which allows users to submit their own bots, written in a custom imperative scripting language dubbed BOTScript. The server will itself make the bots battle each other, ranking them on the website by how many wins each bot gets.

AIArena website: http://dank.business.com/bots/

GitHub: https://github.com/SSODelta/BotBrawl

If you have ideas, suggestions, feedback, criticism or whatever, drop me a line at admin@ssodelta.com.

Sample of the DELTA Library


The DELTA library

If you look through my blog, you’ll find posts where I detail an algorithm for making fractals, or other visually appealing animations/images. To aid myself in the future, I have written a library for Java8 which contains some nice classes and operations for manipulating colors and images.

You can take a look at it at its GitHub page (contains a README.md), though I will detail with the library with further scrutiny on this blog at some point in the future (studying is keeping me busy atm):

https://github.com/SSODelta/DELTA

Often when making single images, there are some dimensions you can change to produce animations. I thought two previous posts were especially suitable for this, so I have made two very nice animations, imo:

Newton Fractals

The biggest problem with animating this fractal, was that I lost the information about which root was assigned which colors when slighting altering the parameters of the polynomials. Instead, using DELTA I have colored each root r_0 using HSV colors with hue proportional to the argument \mathrm{arg}(r_0) and the number of iterations it took for the point to converge – and saturation/value decreased with increasing magnitude |r_0|.

Regex Fractals

Here, the hue is proportional to the edit distance and the time t, and saturation/value inversely proportional to only the edit distance.

Ludum Dare 34


12375456_10207058414872353_2058174363_o

I was convinced by some of my friends to participate in this year’s Ludum Dare. If you’re unfamiliar with the concepts, it’s a game jam – so you have to develop a video game from start to finish in a very limited time frame. In this case, we had 72 hours to develop our idea.

We chose to go with the theme “2 Button Controls” (this year had two possible themes) and developed a simple arcade fighting game à la Street Fighter. I did most of the programming, and my friend Thomas did the graphics, audio and design of the project. I’m very pleased with the result, it is the first game I have started in Unity that I’ve actually finished – most likely because of the short time span.

The code is unstructured, disorganized, fragmented and written pretty poorly. But it has go fast when you’re a jam – it’s not so much about creating the perfect piece of code art, it’s about getting shit done and getting it done fast. I had a lot of fun with this, and will definitely be participating in future jams.

Ludum Dare link: http://ludumdare.com/compo/ludum-dare-34/?action=preview&uid=66145

Play online (requires Unity WebPlayer): https://dl.dropboxusercontent.com/u/19633784/web.html

Download as executable (.exe): https://dl.dropboxusercontent.com/u/19633784/ld34.zip

Source code (Unity project): https://github.com/SSODelta/LudumDare34

LoGiX v1.1.1


LoGiX has been updated to a new build and includes some nice new features and small bug-fixes. Here is the changelog:

Added support for {...} statements and line-breaks;
Added support for in-line comments.
Added support for comments if the output is false.
Improved loading system.

Added support for {…} statements and line-breaks;

The most nice new feature is the curly brackets. I used to have this implemented, but when I rewrote the engine entirely once, I lost feature. But it’s really cool, basically, you type a list list {a,b,c}, and then the LoGiX-engine will replace the curly brackets with each element inside it. So we can type

:> def {P,Q}

Which evaluates as:

:> def P
:> def Q

Which saves a lot of space in programs. A nice example is modus ponens, which before was written as:

:> !def P
:> !def P implies Q
:> Q?
true

Using the new notation, we can write:

:> !def P {,implies Q};Q?
true

Which is very cool! I think this is the shortest you can write modus ponens in LoGiX. It is of course possible to do these multiple places in the command, so we get:

:> def {P,Q,R} implies {A,B}
def P implies A
def Q implies A
def R implies A
def P implies B
def Q implies B
def R implies B

Added support for in-line comments.

Another new feature is the ability to do inline comments. Before, the compiler would crash if a #-symbol appeared not at the beginning of a line. But now, it treats everything after the #-symbol as a comment.

:> def P #Now we've just defined P and made a comment
def P

Added support for comments if the output is false.

And now it’s also possible to use custom messages when the output is false. Before we could do:

:> def {P,Q} implies R
:> def P or Q
:> R?its true
its true

It interprets whatever is after the question mark as the message it prints if the statement is true. However, it was not possible to do the same if the statement was false – it would always return ‘false‘. But now you can do this too:

:> def P and Q implies R
:> def P or Q
:> R?its true|definitely not true
definitely not true