In a previous post, I presented a method of deriving the explicit formula for the terms of the Fibonacci Sequence. In this post, I will present a more concrete method that can be applied to an entire class of recursively-defined sequences.
If $a_n, b_n, c_n$ are sequences, find explicit formulas for each, given these initial conditions and recursive rules for each:
Let us start by returning to the problem of the Fibonacci Sequence: If we move all of the terms in our recursive definition to one side, we get Now suppose that the initial terms of the sequence were not given to us, and we were simply asked to find sequences satisfying this relationship, as if it were a functional equation. In functional equations, observing the properties of a function and making an assumption about its nature can often lead to helpful results. Thus, in this functional equation, I will consider functions of the form where $\rho$ is some real number. If I assume that $F_n$ takes this form, or assume that $F_n=f(n)$, then I obtain and, assuming that $\rho$ is nonzero, Given this, we may solve for $\rho$, using the quadratic formula: and so we now have two functions satisfying the recursive formula: and ...however, neither of these satisfy the initial conditions of the Fibonacci Sequence, so we must keep looking for a solution.
Now I will take a pause in our pursuit of an explicit formula to unveil the "trick" which is central to the solution of this problem, and many others like it. Suppose a sequence is defined by the recursive formula where each $k_i$ is some real constant, and the first $m$ terms are given. Then suppose that some sequence $S_1(n)$ satisfies the same recursive formula. Then and, if $a$ is some real number, and so $\alpha S_1(n)$ also satisfies the same recursive formula. Similarly, suppose some two sequences $S_1(n)$ and $S_2(n)$ both satisfy the recursive formula. Then, both and are true. Then, by adding the two equations, and so the sequence $(S_1+S_2)(n)$ also satisfies the recursive formula.
Back to our original problem. Because of the facts that we have just established, and because we had already shown that the functions and satisfy the recursive formula we may say that any function in the form satisfies the recursive formula, where $\alpha,\beta$ are real constants. Now we have determined an entire class of functions satisfying our recursive formula, and from among them, we need only find the function with initial values $f(0)=0$ and $f(1)=1$. To do this, we can set up a system of equation with unknowns $\alpha$ and $\beta$, and then solve for $\alpha$ and $\beta$: I will spare the reader the tedium of watching me solve a system of linear equations. After solving, we obtain the solutions Which gives us, as the final solution,
We may now apply this method to the four problems that I posed at the beginning of the post. First, we have the sequence with initial conditions $a_0=2, a_1=1$ and recursive definition Because this recursive rule is the same as that in the previous problem, we may use the same class of functions: But this time, $\alpha,\beta$ will have different values, since the initial conditions are different this time. To solve, we can set up the system By solving this, we obtain and so This sequence, a variation of the Fibonacci sequence, is known as the Lucas sequence.
Before beginning the next problem, I will take another pause to derive another result that is, in part, a generalization of the trick that we used earlier. Suppose again that some sequence satisfies Now notice that if some number $\rho$ has the property Then the sequence also satisfies the recurrence relation. As a consequence, if $\rho_1, \rho_2,...,\rho_m$ are the roots of the polynomial then any sequence in the form also satisfies the recurrence relation, where each $\alpha_i$ is a real number. This result is very helpful, because it allows us to instantly generate a family of solutions for any of our recursively defined sequences. Because of this, given a recursively define sequence, the polynomial is often referred to as its characteristic polynomial.
Now we can begin working on the second problem, with initial conditions $b_0=b_1=b_2=1$ and recursive rule Which can be rewritten as Now we can extract the characteristic polynomial with the following zeroes: Notice that, even though the polynomial has some nonreal zeroes, we can still go ahead and use the nonreal zeroes to create our formula. Our family of solutions will be in the form and so we can set up the following system of equations: And when we solve for $\alpha, \beta, \gamma$, we get the following values: So, at last, we have found our formula:
One last problem. The sequence $c_n$ has initial conditions $c_0=c_1=1$ and recursive definition Uh oh, there's a problem - this is similar to the Fibonacci Sequence, but there's a constant term in our recursive definition, and we don't know how to deal with that. If you want to try to figure out what to do on your own, you should stop reading here and try it.
Okay, here's the trick. Notice that we can rearrange our recursive definition to look like this: Now I'm going to define a new sequence $c'_n$, defined in terms of $c_n$ as Then the initial conditions of $c'_n$ are $c'_0=c'_1=2$, and by substituting into the recursive definition of $c_n$, Look, it's just like the Fibonacci Sequence, but it's initial terms are doubled. And since each term is a linear combination of the previous two terms, all of the terms are doubled. Thus and so and, since $c'_n=c_n+1$, or
...and that concludes this blog post. If you want another problem to try, here's a challenge problem (whose solution I will not post): try to find an algebraic representation for the nth term of the sequence