Notes on Sequences and Recurrence

Sequences: Basic Concepts A sequence is simply an ordered list of items or numbers. Unlike a set, the order of elements in a sequence is important. Sequences can be either: - Finite: They have a specific number of terms, meaning there's a last term. - Infinite: They continue indefinitely, with no last term. We typically use $U<em>n$ to represent the '$n$-th' term in a sequence, with $U</em>1$ being the very first term.

Notation and Indexing of Sequences

There are two main ways to define a sequence:

1. Explicit (Direct) Definition: This gives a direct formula for finding any term $U<em>n$ using only its position $n$. It looks like $U</em>n = f(n)$.

   • Example: The sequence of odd numbers can be explicitly defined by the formula $U<em>n = 2n - 1.$ Using this, we can find any term: $U</em>1 = 1$, $U<em>2 = 3$, $U</em>3 = 5$, and so on.

2. Recursive (Recurrence) Definition: This defines each term based on one or more of the previous terms in the sequence. It requires initial values (like $U<em>1$ or $U</em>2$) to get started. It looks like $U<em>n = g(U</em>{n-1}, U_{n-2}, \ldots)$.

   • In the recursive formula $U<em>n = g(U</em>{n-1}, U_{n-2}, \ldots)$:

     • $U_n$ represents the current term in the sequence that you are trying to find.

     • $n$ is the position or index of the term you are calculating (e.g., if $n=3$, you are finding the third term).

     • $g$ represents the function or rule that defines how the current term is derived from previous terms.

     • $U<em>{n-1}$ refers to the term immediately preceding $U</em>n$ (the term at position $n-1$).

     • $U<em>{n-2}$ refers to the term two positions before $U</em>n$ (the term at position $n-2$).

     • The "$\ldots$" indicates that a term might depend on even earlier terms (e.g., $U<em>{n-3}$, $U</em>{n-4}$), depending on the specific sequence's rule.

   • Example: The famous Fibonacci sequence is defined recursively by the formula $U<em>n = U</em>{n-1} + U<em>{n-2} \text{ for } n \ge 3,$ with its first two terms being $U</em>1 = 1 \text{ and } U_2 = 1.$ This means each term (from the third one onwards) is the sum of the two preceding terms. The sequence unfolds as: $1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots$

In general, we are interested in both the formula that defines the sequence and the actual numbers it generates.

Arithmetic (Linear) Sequences

Arithmetic sequences, also known as linear sequences, have a constant difference between any two consecutive terms. This consistent difference is called the common difference, denoted by $d$. They can be written using one of these equivalent formulas:

• $U_n = a n + b$ (where $a$ is the common difference and $b$ is a constant)

• $U<em>n = U</em>1 + (n-1)d$ (where $U<em>1$ is the first term and $d$ is the common difference) The common difference $d$ can always be found by subtracting any term from the term that immediately follows it: $d = U</em>{n+1} - U_n$. This value will always be the same for all terms in an arithmetic sequence.

• Specific Example: Consider the sequence defined by $U_n = -4n + 15$. Let's find its first term and common difference.

  • The first term is $U_1 = -4(1) + 15 = 11$.

  • The common difference is $d = U<em>{n+1} - U</em>n$. If we apply the formula: $d = -4.$ (You can see this because the coefficient of $n$ is $-4$.) This means the sequence starts at 11 and decreases by 4 with each step, giving the terms: $11, 7, 3, -1, -5, \ldots$

Sequences: Basic Concepts A sequence is simply an ordered list of items or numbers. Unlike a set, where the arrangement of elements doesn't matter (e.g., ${\sqrt{1}, 2, 3}$ is the same as ${\sqrt{3}, 2, 1}$), the order of elements in a sequence is crucial. For example, the sequence $(1, 2, 3)$ is distinct from $(3, 2, 1)$). Sequences can be either:

• Finite: These sequences have a specific, countable number of terms, implying there is a definitive last term. An example would be the sequence of days in a week: $(Monday, Tuesday, \ldots, Sunday)$.

• Infinite: These sequences continue indefinitely without a last term. The sequence of natural numbers $(1, 2, 3, \ldots)$ is an infinite sequence.

We typically use $U<em>n$ to represent the '$n$-th' term in a sequence, with $U</em>1$ being the very first term, $U_2$ the second, and so on. The subscript $n$ indicates the position of the term in the sequence.

Notation and Indexing of Sequences

There are two primary methods for defining a sequence:

1. Explicit (Direct) Definition:
   This method provides a direct formula, $U<em>n = f(n)$, that allows you to calculate any term $U</em>n$ solely based on its position $n$ in the sequence. You don't need any preceding terms to find the current one.

   • Example: The sequence of odd numbers can be explicitly defined by the formula $U_n = 2n - 1$. Using this formula, we can directly find any term:

     • For $n=1$ (the first term): $U_1 = 2(1) - 1 = 1$

     • For $n=2$ (the second term): $U_2 = 2(2) - 1 = 3$

     • For $n=3$ (the third term): $U_3 = 2(3) - 1 = 5$
       …and so on.

2. Recursive (Recurrence) Definition:
   This approach defines each term in the sequence by relating it to one or more of the previous terms. To use a recursive definition, you must be given one or more initial values (base cases), such as $U<em>1$ or $U</em>2$ (or more, depending on the sequence), to start the sequence. The general form is $U<em>n = g(U</em>{n-1}, U_{n-2}, \ldots)$.

   • Let's break down the recursive formula Un = g(U{n-1}, U_{n-2}, \ldots)$ rearrangements:

     • U_n$: This is the current term you are trying to find.</p></li><li><p>$n$: This is the position or index of the term you are calculating. For instance, if$n=3$, you are finding the third term.</p></li><li><p>$g$: This represents the function or rule that specifies how the current term is derived from its predecessors.</p></li><li><p>$U{n-1}$: Refers to the term immediately preceding$Un$(the term at position$n-1$).</p></li><li><p>$U{n-2}$: Refers to the term two positions before$Un$(the term at position$n-2$).</p></li><li><p>The "$\ldots$": Indicates that a term might depend on even earlier terms (e.g.,$U{n-3}$,$U{n-4}$), depending on the specific rule of the sequence.</p></li></ul></li><li><p><strong>Example:</strong> The famous Fibonacci sequence is a classic example defined recursively by the formula$Un = U{n-1} + U{n-2} \text{ for } n \ge 3$. It requires two initial terms to begin:$U1 = 1 \text{ and } U_2 = 1$. Using these, the sequence unfolds as follows:</p><ul><li><p>$U3 = U2 + U_1 = 1 + 1 = 2$</p></li><li><p>$U4 = U3 + U_2 = 2 + 1 = 3$</p></li><li><p>$U5 = U4 + U_3 = 3 + 2 = 5$<br>The sequence is:$1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots$</p></li></ul></li></ul></li></ol><p>In essence, understanding a sequence involves grasping both the underlying formula that defines it and the actual ordered list of numbers (or items) it generates.</p><p>Arithmetic (Linear) Sequences</p><p>Arithmetic sequences, also often called linear sequences, are characterized by a constant <em>difference</em> between any two consecutive terms. This consistent difference is known as the <strong>common difference</strong>, denoted by$d$. It's a key feature: to get from one term to the next, you always add (or subtract, if$d$is negative) the same value.</p><p>These sequences can be described using one of these two equivalent explicit formulas:</p><ol><li><p><strong>$U_n = a n + b$</strong></p><ul><li><p>In this form,$a$directly represents the common difference. This is because if you consider$Un = an + b$and$U{n+1} = a(n+1) + b$, then the difference$U{n+1} - Un = (a(n+1) + b) - (an + b) = an + a + b - an - b = a$. Thus,$a$is the constant amount added to each term to get the next one.</p></li><li><p>$b$is a constant that adjusts the sequence to its starting point. It can be thought of as$U_0$(the "zeroth" term) if the sequence started from$n=0$.</p></li></ul></li><li><p><strong>$Un = U1 + (n-1)d$</strong></p><ul><li><p>Here,$U_1$is the first term of the sequence.</p></li><li><p>$d$is the common difference.</p></li><li><p>The term$(n-1)$represents the number of "steps" or common differences you need to add to the first term ($U_1$) to reach the$n$-th term.</p><ul><li><p>To get to$U2$from$U1$, you take one step:$U1 + (2-1)d = U1 + d$.</p></li><li><p>To get to$U3$from$U1$, you take two steps:$U1 + (3-1)d = U1 + 2d$.</p></li><li><p>And so on, for the$n$-th term, you take$(n-1)$steps from$U_1$.</p></li></ul></li></ul></li></ol><p>The common difference$d$can always be calculated by subtracting any term from the term that immediately follows it:$d = U{n+1} - Un$. This value will consistently be identical for all pairs of consecutive terms within a given arithmetic sequence.</p><ul><li><p><strong>Specific Example:</strong> Let's examine the sequence defined by$U_n = -4n + 15$.</p><ul><li><p>To find its first term ($U1$): Substitute$n=1$into the formula:$U1 = -4(1) + 15 = -4 + 15 = 11$.</p></li><li><p>To find the common difference ($d$): We can observe that the coefficient of$n$in the$an+b$form is$-4$, so$d = -4$. Alternatively, we can calculate it using the formula$d = U{n+1} - Un$:<br>Calculate$U2$:$U2 = -4(2) + 15 = -8 + 15 = 7$.<br>Then,$d = U2 - U1 = 7 - 11 = -4$.<br>This means the sequence starts at 11 and decreases by 4 with each subsequent step, generating the terms:$11, 7, 3, -1, -