Ryan's Repository of Random Reflections

In this blog post, I will share a technique I have used in the past to evaluate linear recurrence relations efficiently using a little bit of linear algebra. As a motivating example, assume you have a sequence of numbers that you want to know more about: 1, 2, 3, 7, 24, 100, 448, 2051, 9444, 43549, 200889, 926770, 4275598, 19725314, 91002117, 419835526. Can you spot a pattern (hint: it's a 3rd order linear recurrence relation with constant term and a dependence on \( n \), the index into the sequence)? Once you figure it out, check out my other blog post on  finding recurrence relations from integer sequences to see if you came up with the same recurrence relation. By this point, you have figured out \( f(0) = 1 \), \( f(1) = 2 \), \( f(2) = 3 \), and \( f(n) = 5 f(n-1) - 2f(n-2) + f(n-3) - 2n + 1 \) for \( n \geq 3 \). Now let's say I want top compute the last \( 8 \) digits of \( f(10^{18}) \). A naive solution would be to write a for loop, but that would many orders...

In a lot of the recreational math and computer science problems I solve, I try to derive a recurrence relation that describes the situation. These recurrence relations pop up pretty often in counting problems (how many ways can you tile a 2xn grid with 2x1 tiles?) In some cases, I am unable to derive a recurrence relation directly from the problem statement, but still suspect that there exists some recurrence relation. In these cases, I end up solving the problem usin g brute force methods for small input sizes and analyzing/extrapolating the pattern. However, when the relation is obscure, it becomes hard to find. In order to make this process easier in the future, I created a program that can automatically find recurrence relations for arbitrary integer sequences. To use it, simply type in the first few terms of a sequence you are interested in, and it will try to find a recurrence relation for that sequence. There are some constraints on the allowable inputs/outputs which I di...

In my last blog post , I showed how matrices and matrix multiplication in particular can make sense for more than just numbers. In fact, I used a boolean matrix construct to find the connected components of a graph. In this blog post I will extend that idea to two more types of matrices: "Distance" matrices to find the shortest distances between any two nodes Path matrices to find the (shortest) list of actions that lead between any two states The first type of matrix that I will talk about is what I call a 'Distance' matrix. This is not to be confused with how distance matrices are usually defined in mathematics and computer science (pairwise distance between points). Instead, my definition is more closely related to an adjacency matrix, where connected nodes have non-zero entries (given by the weight, or distance between the nodes), and unconnected nodes have a distance of 'X' to denote that there is no edge between the nodes. Using this newly de...

Matrices are a fundamental part of linear algebra, and we typically think of a matrix as a 2 dimensional array of numbers. In this post, I will show that matrices can be used in other ways too, and I will show that these new types of matrices can be used to solve real problems. Adjacency Matrix If you are already familiar with Adjacency matrices, I recommend you skip ahead to the next section; otherwise, read on! Matrices are especially important in graph theory, as they can be used to model the structure of a graph. A graph is a set of vertices and edges, and the edges indicate how the vertices are connected. Graphs can be used to model a number of real world things: the internet, social networks, road systems, etc. One common representation of a graph is an adjacency matrix: For a matrix \( A = [a_{ij}] \), \( a_{ij} = 1 \) if node i is connected to node j and \( a_{ij} = 0 \) otherwise (Note I implicitly implied there is some ordering on the nodes). One interesting prop...

A few weeks ago, I was using a Markov Chain as a model for a Project Euler problem, and I learned about how to use the transition matrix to find the expected number of steps to reach a certain state. In this post, I will derive the linear system that will help answer that question, and will work out specific an example using a 1-dimensional random walk as the model. Terminology Before I begin the derivation, let me define some terms. The transition matrix is an \( n \) by \( n \) matrix that describes how you can move from one state to the next. The rows of the transition matrix must always sum to 1. States can either be transient or absorbing . An absorbing state is one that cannot be left once reached (it transitions to itself with probability 1). A transient state is a state that is not an absorbing state. In many problems, it is of general interest to compute the expected number of steps to reach an absorbing state (from some start state). Derivation  Let \...