#recurrence relations

Recall the defining recurrence relation of the Fibonacci sequence (and there's nothing special about this sequence, it's just a typical example): $F_{n+2} = F_{n+1} + F_{n}$. This can be represented as a polynomial in the shift operator $X$: $(X^2-X-1)F_n = 0$, so this characteristic polynomial $X^2-X-1$ is said to annihilate the sequence. "Annihilate" is a strong word, but here we just mean that it makes something 0.

I mentioned another recurrence relation too, $F_{n+3} - 2 F_{n+1} - F_n = 0$. The polynomial corresponding to this is $X^3-2X-1$, which is different from what we had before. For one thing, it's degree is higher. Is it related to the other one? It turns out that we can factor this polynomial: $$ X^3-2X-1 = (X+1)(X^2-X-1)$$ hey, there's that polynomial again! It's just a multiple of the original one! (Actually, that's exactly how I came up with this new relation!)

Two questions immediately spring to my mind:

Does every recurrence relation of this sequence turn out to be a multiple of $X^2-X-1$?

Is $X^2-X-1$ itself a multiple of some other, smaller polynomial?

We can answer the second one without anything more than high school algebra, and the answer is no (well, I mean, aside from being a multiple of 1, because everything is a multiple of 1): using the quadratic formula, we have roots $$ x = \frac{1 \pm \sqrt{(-1)^2-4(1)(-1)}}{2} = \frac{1}{2} \pm \frac{\sqrt{5}}{2},$$ and both roots are irrational numbers, which means the polynomial $X^2-X-1$ can't be factored with rational numbers (if you don't buy that, think about what would happen if you could factor it. Check that you can only get rational roots then.).

Ok, so $X^2-X-1$ isn't a multiple of anything else. We call such polynomials irreducible. It's sorta like a prime number! What about that first question?

Let's think about all possible polynomials that give recurrence relations for the Fibonacci sequence, and call the collection of all of them $\mathcal{A}_F$ -- the $\mathcal{A}$ is for "annihilators" and the subscript $F$ means we're focusing on annihilators of the Fibonacci sequence. If we had another sequence in mind, we simply change the subscript. To be precise, we could say $$ \mathcal{A}_F = \{P(X) \mid P(X) \cdot F_n = 0\},$$ which means it's the set of all polynomials $P(X)$ such that when $P(X)$ acts on the sequence, you get zero (in the sense of the multiplication we defined last time -- $X \cdot F_n = F_{n+1}$).

In particular, $X^2-X-1$ is a member of $\mathcal{A}_F$, and so is $X^3-2X-1$. So is the polynomial $0$, because anything times 0 is 0. This set satisfies some neat properties:

$\mathcal{A}_F$ is closed under addition and subtraction, that is, if $P(X)$ and $Q(X)$ are two polynomials in the set, the polynomial $P(X)+Q(X)$ is too.

Given a polynomial $P(X)$ in $\mathcal{A}_F$ and any polynomial $R(X)$, the product $R(X) P(X)$ is in $\mathcal{A}_F$.

Here's a quick proof of the second one, I'll leave the first as an exercise: suppose $P(X)$ is in $\mathcal{A}_F$ and let $R(X)$ be any ol' polynomial. Then by definition of $\mathcal{A}_F$, we have $P(X) \cdot F_n = 0$. To show that $R(X)P(X)$ is in $\mathcal{A}_F$, we need to check that it satisfies that defining property. Then $$(R(X)P(X))\cdot F_n = R(X) \cdot (P(X) \cdot F_n) = R(X) \cdot (0) = 0,$$ where the first equality is justified by the way we defined this "$\cdot$" multiplication -- remember it's not a standard multiplication, we had to make sense of how to multiply $X$ and $F_n$.

These are nice properties! The second one in particular is what I used to make that second recurrence relation; I started with a known relation, took its polynomial $X^2-X-1$, multiplied by the first polynomial I thought of ($X+1$), and translated back to a recurrence relation. You can multiply by anything you like and get one that works! Try to come up with some cool ones!

These properties are so nice, we call a set that satisfies them an ideal. They occur frequently and in many different contexts. The set of all even integers are an ideal of the integers: two even integers added or subtracted give another even integer, and multiplying by any integer (even an odd one!) gives an even. Here, the "context" was different, the set of integers with addition and multiplication, rather than polynomials. This "universe" that an ideal lives in is called a ring. We'll have more to say about rings later.

We still haven't answered the question! Does every recurrence relation come from a multiple of $X^2-X-1$? Spoiler: yes. The reason: it turns out every ideal of the standard polynomial ring is principal, meaning "generated by a single element."

So what is a sequence, anyway? It's a string of numbers, but the order is important; a sequence has a 1st number, a 2nd number, and so on. In fact, there's one for every positive integer, so sequences are infinitely long. Of course, there's only one "first" number, only one "second," no number is "tied for first" or anything like that. That means a sequence is a function; plug in a number and you get some unique number out.

Functions can have all sorts of inputs or outputs; $f(x) = x^2$ is a function with real numbers in, real numbers out, and we use the notation $f: A \to B$ to denote that a function $f$ takes values from a set $A$ as inputs (the domain) and spits out a value in the set $B$ (the codomain). Then a sequence can be defined as a function from the positive integers to the real numbers (the codomain isn't super important and could be anything). So we might say that the Fibonacci sequence $F_n$ is a sequence $F : { \mathbb{N} } \to {\mathbb{R}}$. 

I mentioned last time that the characteristic polynomial captures the shifts in the recurrence relation. What I mean is, the variable $X$ can be thought of as representing a function or operation on sequences to other sequences. Given a sequence $S_n$, we define $X$ to be the shift operator so that $X(S_n) = S_{n+1}$. The input is any old sequence, and the output is a totally new sequence. Well, not totally new; the first number of the new sequence is defined to be the second number of the original sequence. For example, with $F_n$ denoting the Fibonacci sequence:

\begin{align*} F_n &= (1,1,2,3,5,8,\ldots)\\\\ X(F_n) &= (1,2,3,5,8,13,\ldots)\\\\ X(X(F_n)) &= (2,3,5,8,13,21,\ldots) \end{align*}

Since the output of $X$ is another sequence, you can apply it repeatedly. Instead of writing $X(X(F_n))$, we'll just call this $X^2(F_n)$.

We can add and subtract sequences point-wise, meaning, if $S$ and $T$ are sequences, $S+T$ is a sequence whose $n$-th number is $S_n + T_n$. We can also multiply sequences in the same way, and it even makes sense to multiply a sequence by a constant number -- $2 F_n = (2,2,4,6,10,16,\ldots)$.

With these operations, we can make sense of how a polynomial acts on a sequence! I'm going to switch up the notation a bit here and use $X \cdot S_n$ rather than $X(S_n)$. Just remember that $X$ is really a function, its "multiplication" is defined in our special way. Here's an example of what the polynomial $3+X+2X^2$ does to $F_n$:

\begin{align*} (3+X+2X^2)F_n &= 3F_n + X \cdot F_n + 2 X^2 F_n \\\\ &= 3 F_n + F_{n+1} + 2 F_{n+2} \\\\ &= (3+1+4, 3+2+6,6+3+10,\ldots)\\\\ &= (8, 11, 19, \ldots) \end{align*}

Notice that this new sequence still satisfies the same recurrence relation, that each term is the sum of the previous two.

Now, let's look at that characteristic polynomial, $X^2-X-1$. We have

$$(X^2-X-1)F_n = F_{n+2}-F_{n+1}-F_n = (0,0,0,\ldots)$$

That is, the characteristic polynomial turns the Fibonacci sequence into the constant zero sequence! The standard terminology for this is the colorful phrase "the polynomial annihilates the sequence." Is it the only annihilator?

Many sequences satisfy a recurrence relation. For example, the factorial sequence $n!$ (that is, $n! = n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot 2 \cdot 1$) satisfies the relation $n! = n \cdot (n-1)!$; you can get the next term by multiplying the previous term by n. Letting $F_n$ denote the $n$-th Fibonacci number, we can say

$$ F_n = F_{n-1} + F_{n-2}$$

or rearranging the terms and shifting the indices,

$$F_{n+2} - F_{n+1} - F_n = 0.$$

This is more specifically a linear homogeneous recurrence relation. It's linear because it's a sum of a fixed number of previous terms (as opposed to something like a sum of previous terms squared) and has constant coefficients (which would exclude something like our factorial example). It's homogeneous because it's equal to zero and not some other constant (in which case we call it inhomogeneous).

Sorry about the definition dump, but I want to focus on these special kinds of recurrence relations because they have some neat properties and they're generally well-known.

So why might we care about recurrence relations? Well, they're a compact way of defining a sequence. With a recurrence relation and some initial conditions, the sequence is completely determined. You can find any Fibonacci number by using that recurrence relation given the first two terms are 1. Given enough time, you could figure out what any entry in the sequence is by building it up one step at a time. A closed form (that is, an explicit formula that gives you each term in the sequence) is better for computations though, but we can get one if we know the recurrence relation. On the other hand, closed forms can be messy and they obscure this fundamental relation of the sequence, which is often more useful in proofs.

Now, it's possible to find all sorts of recurrence relations in a sequence. For example, $F_{n+3} - 2 F_{n+1} - F_n = 0$ for any n too (check it, when n = 2,  5 - 2(2) -1 = 0). But this one seems... off. I mean, it works, but I like the original one better. Why? For the original one, we needed the relation and two initial conditions to define the sequence. This one would need three; $F_1 = 1$, $F_2 = 1$, and we have to assume $F_3 = 2$, otherwise we're missing some information. So the "best" recurrence relation seems to be the most efficient one, with minimal order.

Then given a recurrence relation, how do we know if it's minimal or not? Well, usually a proof by contradiction works; assume you have some recurrence of smaller order and arrive at a contradiction.

This is getting a little long, so I want to wrap things up. I want to work toward finding some sufficient conditions for concluding that a recurrence relation has minimal order. I'll give one more definition, then we'll pick this up later.

One of the methods of finding a closed form for a sequence uses the characteristic polynomial. This is the polynomial that you get by sort of replacing subscripts with superscripts:

$$F_{n+2} - F_{n+1} - F_n = 0 \mapsto X^2 - X - 1$$