Fixing the Fibonacci sequence inside Pascal's triangle in a couniverse

Posted on January 28, 2017 by Siddhanathan Shanmugam

In the year 1914, Srinivasa Ramanujan presented an infinite sequence for approximating the circle constant pi that seemed to converge surprisingly fast. The equation he gave was the following:

\[ \frac1{\pi} = \frac{2\sqrt{2}}{9801} \sum_{k=0}^\infty \frac{(4k)!(1103+26390k)}{(k!)^4 396^{4k}}\! \]

What’s interesting here is the presence of constants that seem to have appeared out of nowhere. What seemed like magic numbers to the rest of the world was just mathematics to Ramanujan; the reason being, he was autodidact. Having no formal training in pure mathematics, he was unable to explain the pattern he saw. Ramanujan’s story is enlightening because it tells us that we can understand the world of the infinite by recognizing patterns, even if we don’t understand the mathematical proofs behind these patterns.

In this post, I hope to explore the concept of infinity in a computational setting by relating the Fibonacci sequence to Pascal’s triangle. Not only are these concepts related, but they can be understood using simple geometric transformations that can be visualized. Our stepping stone into this infinite world is understanding geometric transformations using Pascal’s triangle. Constructing Pascal’s triangle is simple. Starting with a seed value of {1}, every element of the triangle is the sum of the two values directly above it (we can add imaginary zeroes at the edges).

AnimatedPascal

AnimatedPascal

Rather than keeping things abstract, we can represent Pascal’s triangle in computer code. I will be using Haskell, which is a typed purely functional programming language with call by need semantics.

Generating Pascal’s Triangle

Our goal is to generate a list of rows of the triangle, where each row contains numbers. We could tackle this problem directly, but as any good programmer, we value composability - the ability to build small reusable components which can be combined to solve a larger problem. In our case, we would like to be able to generate one row of the triangle given the row’s predecessor. We call this function pascalStep. Once we have our pascalStep function, the entire triangle can be evaluated by repeated applications of this function on the starting seed of {1}.

So how exactly does pascalStep work? Well, we know that it takes a list of numbers as its argument, and adds adjacent elements in this list together. This can be viewed using geometric transformations. First we duplicate the row, then shift the duplicate by one position to the right, add zeroes on the ends as appropriate, and perform column-wise addition.

pascalStep

pascalStep

pascalStep :: forall f a . (Num a, ListLike (f a) a) => f a -> f a
pascalStep xs = zipWith (+) (cons 0 xs) (snoc xs 0)

The syntax might be confusing if you’re not familiar with Haskell. The first line is the type of the function, which says that pascalStep is a function that takes an argument of type f a and returns a value of type f a, where f is a list containing numeric values of type a. The second line is the actual implementation.

Equipped with the pascalStep function, we need a function that repeatedly applies this function to our starting seed. This function is called iterate in Haskell.

-- iterate f xs = [ x, f x, f (f x), f (f (f x)), ...]
pascalTriangle
  :: forall f a
  . (Num a, ListLike (f a) a, InfiniteListLike (f (f a)) (f a))
  => f (f a)
pascalTriangle = iterate pascalStep (singleton 1)

From the type of the function, we can see that pascalTriangle is an infinite list containing rows, where rows are finite lists of numbers. What’s interesting is that iterate actually does produce an infinite list. We leave it upto the consumer of this function to decide how many iterations are needed. Lazy evaluation ensures that we don’t compute more than we need to. This idea of separating the logic of the producer from the consumer’s requirements allows us to write code that’s easier to reason about.

We could turn this into a one liner if we wanted to, but we value composability, so we resist the temptation.

oneLiner = iterate (zipWith (+) (cons 0 xs) (snoc xs 0)) (singleton 1)

Now, if Pascal’s triangle wasn’t very interesting, this post would end here. However, that’s clearly not the case. Pascal’s triangle was actually known to ancient mathematicians long before Blaise Pascal. In India, it was known as the staircase of Mount Meru. In Iran, it was the Khayyam triangle. And in China, it was called Yang Hui’s triangle. Today, the triangle is named after Pascal for his contributions in recognizing the patterns it contains. Let’s first look at a simple pattern in Pascal’s triangle and see if we can understand why it occurs. Then we will look at a more interesting pattern.

Sum of the rows

pascalHorizontalSum

pascalHorizontalSum

The sum of any row on Pascal’s triangle is a power of two. A very interesting pattern which can be easily seen with the pascalStep function. Because we duplicate the row and add it to itself in the pascalStep function, the sum of a row must be necessarily twice the sum of its predecessor.

Fibonacci numbers

pascalFibonacci

pascalFibonacci

The sum of the diagonals yield the Fibonacci sequence. This one actually threw me off guard when I noticed it. How does a mathematical sequence where the ratio of consecutive terms asymptotically approach the golden ratio show up in this triangle? Since it is embedded, does that mean there is a way to generate the Fibonacci sequence the same way we construct Pascal’s triangle? We will know the answer in a bit.

Calculating the Fibonacci sequence is simple. The sequence starts with 1 and 1, and every term after that is the sum of the previous two terms. If we were to naively implement a function that calculates the nth Fibonacci number, we could write something like the following:

fibN :: Natural -> Natural
fibN 0 = 1
fibN 1 = 1
fibN n = f (n-1) + f (n-2)

However, that only gives us the nth Fibonacci number. Computing the entire list of Fibonacci numbers becomes an expensive computation with this approach. The alternative approach is to try understanding the Fibonacci sequence with simple geometric transformations.

Entering the couniverse

To do this, we need to leave this universe, and move into the couniverse! Sounds crazy, but it will make sense in a bit. If somehow we could take the list of infinite Fibonacci numbers, duplicate this list, drop the first element in one copy, and add column-wise, we end up getting every 3rd element of the Fibonacci sequence.

fibsHaskell

fibsHaskell

So theoretically, if we appended two 1’s to this list, we would get the Fibonacci sequence:

fibs :: forall f a . (Num a, ListLike (f a) a) => f a
fibs = cons 1 . cons 1 $ zipWith (+) (tail fibs) fibs

Now, although I said theoretically, it’s quite marvelous that this pseudocode we made up is actually valid Haskell code, and produces an efficient binary that also memoizes previous results. This is the magic of the couniverse! You can manipulate lists of infinite size in the couniverse, and you still end up with efficient implementations (sometimes more efficient than its dual counterpart in the universe).

Although that’s quite elegant by itself, we want to see the relation between the Fibonacci sequence and Pascal’s triangle. There is some similarity that’s evident right away:

pascalStep xs = zipWith (+) (cons 0 xs) (snoc xs 0)
fibs =  1 : 1 : zipWith (+) (tail fibs) fibs

In the case of pascalStep, we duplicate xs, and in the case of fibs we duplicate fibs. In both cases, we manipulate these copies, then add them together column-wise using zipWith (+). But does the similarity stop there?

Data and Codata

To understand a deeper connection, we need to talk about data and codata. In our universe, we deal with data, that is, finite values. In the couniverse, we deal with codata, that is, infinite values. Properties of the universe may not hold in the couniverse, and vice versa. To understand this, let’s consider a partial function:

unsafeHead [] = error "unsafeHead on empty list!"
unsafeHead (x:_) = x

unsafeHead is unsafe because it returns an error when provided an empty list. But suppose we are dealing with codata, where the list being passed is infinite, then unsafeHead is actually safe!

That’s neat! Our unsafe functions become safe. But can things go the other way?

sum [] = 0
sum (x:xs) = x + sum xs

Taking the sum of a list, which used to be a safe function when dealing with data now becomes a non-terminating function when dealing with codata!

This explains a crucial point about the difference between data and codata. They actually live in different domains, and functions may be safe/unsafe depending on the domain you’re working with. Haskell makes no distinction between data and codata, so the lines that distinguish them are blurred here.

Equational Reasoning in a couniverse

What’s interesting, is that pascalStep acts on data, but the zipWith (+) in fibs acts on codata. When acting on codata, non-intuitive things happen, the same way weird things happen when dealing with infinite sets in mathematics. We know what happens when you add an element to the start of an infinite list - we get back what we expect. But what happens when we add an element to the end of an infinite list?

snoc infiniteList e == infiniteList

This is counter-intuitive. The length of the new list remains unchanged, and the result is as if we did not do anything to the list to begin with! Using this fact, we can view our fibs functions with new light:

pascalStep xs = zipWith (+) (cons 0 xs) (snoc xs   0)
fibs =  1 : 1 : zipWith (+) (tail fibs) (snoc fibs 0) -- (snoc fibs 0 == fibs)

Close! But tail fibs is not the same as cons 0 xs. At this point, we can make use of the fact that the Fibonacci numbers could start with 0 and 1, instead of 1 and 1, hence doing a non-trivial rewrite.

pascalStep xs = zipWith (+) (cons 0   xs) (snoc xs   0)
fibs =      1 : zipWith (+) (cons 0 fibs) (snoc fibs 0)

This rewrite is hard to explain. You can convince yourself that this works by evaluating this in a GHCi session. With this rewrite, the connection is clear:

fibs = 1 : pascalStep fibs

We can continue refactoring by using function composition:

fibs = cons 1 . pascalStep $ fibs

Which makes the self recursion evident, allowing us to write a much stronger claim:

fibonacci :: forall f a . (Num a, ListLike (f a) a) => f a
fibonacci = fix (cons 1 . pascalStep)

The Fibonacci sequence is the least fixed point of the composition of the pascalStep function with a function that adds 1 to the start of the list. Mathematically speaking, the least fixed point is the smallest point for which repeated applications of the function do not change the value - that is, f x = x. It comes from a branch of mathematics known as Order Theory.

Final thoughts

To see the fixed point in action, we could fire up a GHCi session and see how the fibonacci sequence gets evaluated.

GHCi, version 8.0.1: http://www.haskell.org/ghc/  :? for help
Prelude> pascalStep xs = zipWith (+) (0:xs) (xs++[0])
Prelude> f = (1:) . pascalStep
Prelude> f $ []
[1,0]
Prelude> f . f $ []
[1,1,1,0]
Prelude> f . f . f $ []
[1,1,2,2,1,0]
Prelude> f . f . f . f $ []
[1,1,2,3,4,3,1,0]
Prelude> f . f . f . f . f $ []
[1,1,2,3,5,7,7,4,1,0]
Prelude> f . f . f . f . f . f $ []
[1,1,2,3,5,8,12,14,11,5,1,0]
Prelude> f . f . f . f . f . f . f $ []
[1,1,2,3,5,8,13,20,26,25,16,6,1,0]
Prelude> f . f . f . f . f . f . f . f $ []
[1,1,2,3,5,8,13,21,33,46,51,41,22,7,1,0]
Prelude> 

We can see that on applying the function a few times, we do not get the Fibonacci sequence! However, on repeated application, the first few elements converge to the fibonacci sequence. This is to say, if we applied the function infinite times, we would get the Fibonacci sequence.

To convince yourself that this is indeed a fixed point, try passing in a different list as the argument to f and see if the values converge on repeated applications of this function. In fact, we can write a QuickCheck property to verify this:

prop_fix :: [Integer] -> Int -> Bool
prop_fix xs n = take n ((!!n) . iterate f $ xs) == take n fibs
-- +++ OK, passed 100000 tests.

This illustrates some important points:

Extending Pascal’s triangle

So the Fibonacci sequence lives in the couniverse. This begs the question, does Pascal’s triangle also live in the couniverse? We could take an alternate approach by using a different starting seed.

extendedTriangle

extendedTriangle

Essentially a 2D infinite zipper with zeroes extending on both ends and the focus being a point in the triangle. However, there’s unanswered questions here, like what happens when you go above the first row? Do we mirror the triangle, or just say the operation is undefined?

This post is quite lengthy as it is, so I will stop here. But, looking at it again, why exactly does the non-trivial rewrite work? Simple:

fibs = let fs = 1 : 0 : zipWith (+) (tail fs) fs in drop 2 fs