Deriving Recursive Functions Using Graphs and Matrices¶

Fibonacci¶

Consider a two-node graph where the two nodes are connected by an edge, and the first node has a self-loop. We want to calculate the number of walks of length n from node 1 to itself, which we denote as \(f_n\). We condition on the first edge of the walk. If the first edge of the walk is the self-loop, then by definition we can continue in \(f_{n-1}\) ways. However, if the first step moves to the other node, the second edge of the walk is uniquely determined (we must return to the first node). After this, we can continue in \(f_{n-2}\) ways. Thus, we have:

The number of 0-length and 1-length walks from node 1 to itself is 1, so the sequence \(f\) is the well-known Fibonacci sequence. Therefore, to compute the n-th Fibonacci number, we can raise the adjacency matrix of this graph to the n-th power. Specifically, the (1,1) entry of the matrix

is precisely the n-th Fibonacci number.

It is not necessary to construct a graph from scratch for every recursive relation. Instead, we can find general transformations and modify the graph to accommodate specific patterns of functions. For example, the partial sum transformation is discussed below.

Suppose we have a graph where the number of walks of length n from vertex i to j is equal to \(f_n\). We define the sequence g as follows:

We aim to modify the graph such that it can compute the above sequence. To do this, we add a new vertex k to the graph, add an edge from vertex j to k, and place a loop on the new vertex. The number of walks from i to j remains unchanged. We claim that the number of walks of length n from i to k equals the desired value. First, it is clear that the base case holds: there are no 0-length walks from i to k. To prove the inductive step, we consider cases based on the last edge of the walk. Either the last edge is the loop itself, in which case the prefix walk has \(g_{n-1}\) possibilities, or it is the edge from j to k, in which case the prefix walk has \(f_{n-1}\) possibilities by the initial assumption.