递归公式

(Video) Recursive Sequences

by PatrickJMT

This video by PatrickJMT talks about recursive sequences.

$\large{\text{Summary}}$

A recursive sequence is kind of like a sequence that refers back to itself.

The first problem Patrick looks at is,

Find the first $3$ terms of a sequence that has a first term of $a_1=4$ and $n^{\text{th}}$ term: $a_n=2a_{n-1}+3$.

$a_n=2a_{n-1}+3$ is a recursive formula because each term, $a_n,$ refers back to the previous term, $a_{n-1}.$ This equation is telling us that whatever term we want to find is equal to $2$ times the previous term, plus $3.$

We're given the first term to start. $$a_1=4$$

To find the second term, we use our equation. $$\begin{align} a_n&=2a_{n-1}+3\\ a_2&=2a_{2-1}+3\\ a_2&=2a_1+3\\ a_2&=2(\color{#29A603}{4})+3\\ a_2&=11 \end{align}$$

We use the same method to find the third term. $$\begin{align} a_n&=2a_{n-1}+3\\ a_3&=2a_{3-1}+3\\ a_3&=2a_2+3\\ a_3&=2(\color{#29A603}{11})+3\\ a_3&=25 \end{align}$$

The first three terms of this sequence are: $4,11,25$.

Answer

We're given the first term: $$a_1=2$$

Use the equation to find the second. $$\begin{align} a_n&=a_{n-1}\left(\frac{n+1}{n}\right)\\ a_2&=a_{2-1}\left(\frac{2+1}{2}\right)\\ a_2&=a_1\left(\frac{3}{2}\right)\\ a_2&=\color{#29A603}{2}\left(\frac{3}{2}\right)\\ a_2&=3 \end{align}$$

Then find the third. $$\begin{align} a_n&=a_{n-1}\left(\frac{n+1}{n}\right)\\ a_3&=a_{3-1}\left(\frac{3+1}{3}\right)\\ a_3&=a_2\left(\frac{4}{3}\right)\\ a_3&=\color{#29A603}{3}\left(\frac{4}{3}\right)\\ a_3&=4 \end{align}$$

Then the fourth. $$\begin{align} a_n&=a_{n-1}\left(\frac{n+1}{n}\right)\\ a_4&=a_{4-1}\left(\frac{4+1}{4}\right)\\ a_4&=a_3\left(\frac{5}{4}\right)\\ a_4&=\color{#29A603}{4}\left(\frac{5}{4}\right)\\ a_4&=5 \end{align}$$

And finally the fifth. $$\begin{align} a_n&=a_{n-1}\left(\frac{n+1}{n}\right)\\ a_5&=a_{5-1}\left(\frac{5+1}{5}\right)\\ a_5&=a_4\left(\frac{6}{5}\right)\\ a_5&=\color{#29A603}{5}\left(\frac{6}{5}\right)\\ a_5&=6 \end{align}$$

So our sequence is: $2,3,4,5,6$.

Recursive Formulas

Recursive formulas seem to show up everywhere we look, and they can be surprisingly useful. However, they can also be frustratingly mysterious.

A recursive formula relates the $n^{\text{th}}$ term, or $a_n,$ to previous terms like $a_{n-1}, a_{n-2},$ etc.

Recursive formulas show up everywhere, even in our day-to-day life. For example, suppose that you grew two inches each year. You could then describe your height on your $n^{th}$ year as: $$h_n=h_{n-1}+2$$

Simple, right? However, there are a few things that make recursive formulas more difficult than they might seem.

First is the need for initial conditions, also called base cases. Initial conditions are starting values in the sequence defined by the recursive formula. Without initial conditions, you can never know any of the terms in the sequence, because they could start anywhere.

In the above example, suppose you were born $8$ inches tall, i.e., $h_0=8.$ Then you would be $10$ inches by age $1,$ and $12$ inches by age $2,$ and so on. However, you could have also been born $10$ inches tall, i.e., $h_0=10.$ Then you would be $12$ inches by age $1,$ and $14$ inches by age $2,$ and so on. Your starting height would change how tall you were at every age. Without a base case, the entries in a recursive sequence can't be determined.

Second, and more frustratingly, there is no set way to solve every recursive formula. (By "solving", we mean obtaining a formula for the $n^{\text{th}}$ term that does not depend on any of the terms before it, except the base case. We would want to "solve" because finding the $n^{\text{th}}$ term of a complicated recursive formula can be very tedious for a large $n$.)

While the one above is pretty simple, many recursive formulas need very creative solutions, and some are completely unsolvable. However, there are some types of formulas that we know how to solve.

Solving a Simple Arithmetic Recursion

While there is unfortunately no method that can solve every recursive formula, it can be easy to solve simple arithmetic recursive formulas (which can describe arithmetic sequences). By "arithmetic recursive formula" we mean that the only operation involved is addition. The example above was an arithmetic recursive formula: $$h_n=h_{n-1}+2$$

However, we're going to use a slightly more complicated answer, so we can illustrate the power of solving a recursive formula. Suppose that on day one, a company makes $1$ dollar, and every day the company makes $23$ more dollars than the day before. We could describe their income on the $n^{th}$ day as: $$a_n=a_{n-1}+23$$

While it may be easy to calculate their profit for a few days or a week with the above formula, it would be difficult to estimate their profit after a few years. To do that, we have to solve it. We do this by listing some terms, finding the difference, $d,$ between each term, and then fitting the final formula to the sequence. The formula to find the $n^{\text{th}}$ term in an arithmetic sequence is: $$a_n=(n-1)d+a_1$$

Let's try it. With the formula above, the first $5$ terms are as follows: $$\begin{align} a_1 &= 1 \text{ (given to us as the base case)}\\ a_2&=a_1+23=24\\ a_3&=a_2+23=47\\ a_4&=a_3+23=70\\ a_5&=a_4+23=93 \end{align}$$

From there, we can easily see that the difference between each term is $23,$ and so we know $d$. This is important, because we know that $d$ will appear as the coefficient on the $n$ term in the final formula.

We then have to fit this $d$ to the final formula. Since we know that the formula for the $n^{\text{th}}$ term in an arithmetic sequence is $a_n=(n-1)d+a_1,$ we can come up with the following formula to describe the sequence: $$a_n=23(n-1)+1$$

We now can easily find how much money the company will make in $10, 100, 1000,$ or any other amount of days by substituting for $n.$

This formula is also interesting because it illustrates a pattern common to all arithmetic recursive formulas. We can see that our base case makes it into the final formula as the final term being added on, and given the initial formula, we can see that $d$ was there all along: $$a_n=a_{n-1}+{\color{#29A603}{23}}\quad d\text{ is the term being added}$$

With these two facts, we can find a general solution to a recursive formula of the form $a_n=a_{n-1}+d$ with $a_1=k$, for any constant $k:$ $$a_n=d(n-1)+k$$

To see this formula in action, try some examples for yourself!

Maximum Depth Exceeded: Fun with Sequences and Python, Part 1

We're going to talk about sequences, specifically about the relationship between closed forms and recursive formulas for sequences. In fact we're going to do something extra special and use our friends from Python to guide us.

A recurrence formula lets us generate a sequence by finding the terms one by one until we get the term we want (many questions are worded "find the $n^{\text{th}}$ term in this sequence if it's satisfied by this formula").

The formula is an equation, where one side is the current term we want to find out (usually written like $a_n$), and it depends on earlier terms in the sequence.

One example is

$$a_n = a_{n - 1} - 1,$$

where we assume we KNOW what $a_{n - 1}$ is and then just plug it in the formula. Let's type this into a Python function, shown below.

Well we tried to find $a_{10}$ and we failed. What gives? We keep moving backwards in the sequence to find a term that we actually KNOW the value of, but we aren't given any. For instance, we are usually told $a_0$ to make the recurrence formula useful. If $a_0 = 7$ rewrite our Python code is as follows:

Now if we try to find $a_{10}$ we get a result we expect:

Much better!

If you want to see the next part of this Python story, go here.

Recursive Sequences

Recursive sequences are sequences defined by recursive formulas. They are also called recurrence relations or recurrence equations.

A recursive formula relates each term in the sequence to previous terms in the sequence. This is different than an explicit formula, which describes each term in the sequence as a function of its position.

Let's look at the Fibonacci sequence.

Let's break down the recursive formula for the Fibonacci sequence.

$$\begin{align} F_n&=F_{n-1}+F_{n-2}\\ \text{Initial conditions}&: F_0=0, F_1=1 \end{align}$$

$F_n=F_{n-1}+F_{n-2}$ means that each term $(F_n)$ is equal to the sum of the previous term $(F_{n-1})$ and the term before the previous term $(F_{n-2}).$ We include initial conditions so the sequence has a place to start. Initial conditions are the first few terms in the sequence. Recursive sequences need initial conditions to define a starting point.

Let's check that this Fibonacci recurrence relation is correct. We know that our first couple terms are defined by the initial conditions $F_0=0$ and $F_1=1.$ So, let's start at the next term!

The next term is $F_2,$ and $F_2=1.$ The term before $F_2$ is $F_1=1,$ and the term before that is $F_0=0.$ Using our recurrence formula: $$\begin{align} F_n&=F_{n-1}+F_{n-2}\\ F_2&=F_{2-1}+F_{2-2}\\ F_2&=F_{1}+F_{0}\\ 1&=1+0\\ 1&=1 \checkmark \\ \end{align}$$

The next term is $F_3,$ and $F_2=2.$ The term before $F_3$ is $F_2=1,$ and the term before that is $F_1=1.$ Using our recurrence formula: $$\begin{align} F_n&=F_{n-1}+F_{n-2}\\ F_3&=F_{3-1}+F_{3-2}\\ F_3&=F_{2}+F_{1}\\ 2&=1+1\\ 2&=2 \checkmark \\ \end{align}$$

The next term is $F_4,$ and $F_4=3.$ The term before $F_4$ is $F_3=2,$ and the term before that is $F_2=1.$ Using our recurrence formula: $$\begin{align} F_n&=F_{n-1}+F_{n-2}\\ F_4&=F_{4-1}+F_{4-2}\\ F_4&=F_{3}+F_{2}\\ 3&=2+1\\ 3&=3 \checkmark \\ \end{align}$$

Let's do one last one! The next term is $F_5,$ and $F_5=5.$ The term before $F_5$ is $F_4=3,$ and the term before that is $F_3=2.$ Using our recurrence formula: $$\begin{align} F_n&=F_{n-1}+F_{n-2}\\ F_5&=F_{5-1}+F_{5-2}\\ F_5&=F_{4}+F_{3}\\ 5&=3+2\\ 5&=5 \checkmark \\ \end{align}$$

Try the rest on your own!

Another Example

Let's figure out the first four terms of the geometric sequence defined by the following recurrence relation and initial conditions: $$\begin{align} a_n&=4a_{n-1}\\ \text{Initial conditions}&: a_1=-1 \end{align}$$

We know that our first term is defined by the initial conditions $a_1=-1.$ So, let's start at the next term!

The next term is $a_2.$ the term before $a_2$ is $a_1,$ and $a_1=-1.$ Using our recurrence formula: $$\begin{align} a_n&=4a_{n-1}\\ a_2&=4a_{2-1}\\ a_2&=4a_{1}\\ a_2&=4(-1)\\ a_2&=\boxed{-4}\\ \end{align}$$

The next term is $a_3.$ the term before $a_3$ is $a_2,$ and $a_2=-4.$ Using our recurrence formula: $$\begin{align} a_n&=4a_{n-1}\\ a_3&=4a_{3-1}\\ a_3&=4a_{2}\\ a_3&=4(-4)\\ a_3&=\boxed{-16}\\ \end{align}$$

Last one! The next term is $a_4.$ the term before $a_4$ is $a_3,$ and $a_3=-16.$ Using our recurrence formula: $$\begin{align} a_n&=4a_{n-1}\\ a_4&=4a_{4-1}\\ a_4&=4a_{3}\\ a_4&=4(-16)\\ a_4&=\boxed{-64}\\ \end{align}$$

So, the first four terms in the sequence defined by this recurrence relation are: $$-1, -4, -16, -64 ...$$

Here is more on formulas for geometric sequences, if you are interested.