Summation Notation (Sigma Notation)
Introduction
Summation notation, often represented by the Greek letter sigma (Σ), is a concise way to express the sum of a series of numbers. It is a powerful tool used in various areas of mathematics, including calculus, statistics, and discrete mathematics.
Basic Structure:
Example:
This expression represents the sum of the first five natural numbers: 1 + 2 + 3 + 4 + 5.
Key Concepts:
Applications in Computer Science:
Example in Computer Science:
for i in range(n):
for j in range(i):
# some operation
The time complexity of this code snippet can be expressed as:
Σi=1n Σj=1i 1 = Σi=1n i = n(n+1)/2
This demonstrates how summation notation can be used to analyze the number of operations performed by an algorithm.
Conclusion:
An arithmetic progression (AP) or arithmetic sequence is a sequence of numbers such that the difference between the consecutive terms is constant. For instance, the sequence \(5, 7, 9, 11, 13, 15 \ldots\) is an arithmetic progression with common difference of 2.
If the initial term of an arithmetic progression is \(a_{1}\) and the common difference of successive members is d, then the \(n-\)th term of the sequence (\(a_{n}\)) is given by: \[ a_{n}=a_{1}+(n-1)d, \] and in general \[ a_{n}=a_{m}+(n-m)d.\]
The behavior of the arithmetic progression depends on the common difference d. If the common difference is:
The sum of the members of a finite arithmetic progression is called an arithmetic series. For example, consider the sum: \[2+5+8+11+14\] This sum can be found quickly by taking the number n of terms being added (here 5), multiplying by the sum of the first and last number in the progression (here 2 + 14 = 16), and dividing by 2: \[{\frac {n(a_{1}+a_{n})}{2}}\]
In the case above, this gives: \[2+5+8+11+14={\frac {5(2+14)}{2}}={\frac {5\times 16}{2}}=40.\] This formula works for any real numbers \(a_{1}\) and \(a_{n}\). For example: \[\left(-{\frac {3}{2}}\right)+\left(-{\frac {1}{2}}\right)+{\frac {1}{2}}={\frac {3\left(-{\frac {3}{2}}+{\frac {1}{2}}\right)}{2}}=-{\frac {3}{2}}.\]
Find the sum of the arithmetic progression {
\[ 11 + 13 + 15 + \ldots + 49 + 51 \] }
First recall two useful equations for working with arithmetic
progressions.\
For the arithmetic sequence \(a,(a+d) ,(a+2d), \ldots\)
[(i)] \(t_n\) is the \(n-th\) term of series.\[ t_n= a+(n-1)d \]
[(ii)] \(S_n\) is the sum of the first \(n\) terms
\[ S_n = \frac{n }{ 2} \left[ 2a+(n-1)d \right] \]
Find the sum of the arithmetic progression { \[ 11 + 13 + 15 + \dots + 49 + 51 \] }
There are 21 terms in the series.
\[ S_n = {n \over 2} \left[ 2a+(n-1)d \right] \]
Recall \(a=11\),\(d=2\) and \(n=21\)
\[ \phantom{S_n = {21 \over 2} \left[ (2.11) +[(21-1)2] \right]} \] \[ \phantom{S_n = 10.5 \left[ 22 + 40 \right] = 10.5 \times 62}\] \[ \phantom{S_n = 651} \]
In this chapter we’ll be taking a look at sequences and (infinite)
series. Actually, this chapter will deal almost exclusively with series.
However, we also need to understand some of the basics of sequences in
order to properly deal with series.
We will therefore, spend a little time on sequences as well.
Series is one of those topics that many students don’t find all that useful. To be honest, many students will never see series outside of their calculus class.
However, series do play an important role in the field of ordinary differential equations and without series large portions of the field of partial differential equations would not be possible.
[a] Sum arithmetic, geometric and telescoping series; [b] test series for convergence; [c] find the Maclaurin series of a function; [d] manipulate power series; [e] use l’Hopital’s rule. [f] Integrate standard functions using substitution and parts; [g] Apply to calculation of areas and volumes.
In other words, series is an important topic even if you won’t ever see any of the applications. Most of the applications are beyond the scope of most Calculus courses and tend to occur in classes that many students don’t take. So, as you go through this material keep in mind that these do have applications even if we won’t really be covering many of them in this class.
Here is a list of topics in this section
Sequences We will start the chapter off with a brief discussion of sequences. This section will focus on the basic terminology and convergence of sequences
[More on Sequences] Here we will take a quick look about monotonic and bounded sequences.
Series The Basics In this section we will discuss some of the basics of infinite series.
[Series Convergence/Divergence] Most of this chapter will be about the convergence/divergence of a series so we will give the basic ideas and definitions in this section.
[Special Series] We will look at the Geometric Series, Telescoping Series, and Harmonic Series in this section.
[Integral Test] Using the Integral Test to determine if a series converges or diverges.
[Comparison Test/Limit Comparison Test] Using the Comparison Test and Limit Comparison Tests to determine if a series converges or diverges.
[Alternating Series Test] Using the Alternating Series Test to determine if a series converges or diverges.
[Absolute Convergence] A brief discussion on absolute convergence and how it differs from convergence.
[Ratio Test] Using the Ratio Test to determine if a series converges or diverges.
[Root Test] Using the Root Test to determine if a series converges or diverges.
[Strategy for Series] A set of general guidelines to use when deciding which test to use.
[Estimating the Value of a Series] Here we will look at estimating the value of an infinite series.
[Power Series] An introduction to power series and some of the basic concepts.
[Power Series and Functions] In this section we will start looking at how to find a power series representation of a function.
[Taylor Series] Here we will discuss how to find the Taylor/Maclaurin Series for a function.
[Applications of Series] In this section we will take a quick look at a couple of applications of series.
[Binomial Series] A brief look at binomial series.
An arithmetic progression (AP) or arithmetic sequence is a sequence of numbers such that the difference between the consecutive terms is constant. For instance, the sequence \(5, 7, 9, 11, 13, 15 \ldots\) is an arithmetic progression with common difference of 2.
If the initial term of an arithmetic progression is \(a_{1}\) and the common difference of successive members is d, then the \(n-\)th term of the sequence (\(a_{n}\)) is given by: \[ a_{n}=a_{1}+(n-1)d, \] and in general \[ a_{n}=a_{m}+(n-m)d.\]
A finite portion of an arithmetic progression is called a finite arithmetic progression and sometimes just called an arithmetic progression. The sum of a finite arithmetic progression is called an arithmetic series.
The behavior of the arithmetic progression depends on the common difference d. If the common difference is:
The sum of the members of a finite arithmetic progression is called an arithmetic series. For example, consider the sum: \[2+5+8+11+14\] This sum can be found quickly by taking the number n of terms being added (here 5), multiplying by the sum of the first and last number in the progression (here 2 + 14 = 16), and dividing by 2: \[{\frac {n(a_{1}+a_{n})}{2}}\]
In the case above, this gives: \[2+5+8+11+14={\frac {5(2+14)}{2}}={\frac {5\times 16}{2}}=40.\] This formula works for any real numbers \(a_{1}\) and \(a_{n}\). For example: \[\left(-{\frac {3}{2}}\right)+\left(-{\frac {1}{2}}\right)+{\frac {1}{2}}={\frac {3\left(-{\frac {3}{2}}+{\frac {1}{2}}\right)}{2}}=-{\frac {3}{2}}.\]
A geometric progression, also known as a geometric sequence, is a sequence of numbers where each term after the first is found by multiplying the previous one by a fixed, non-zero number called the common ratio.
For example, the sequence \(2, 6, 18, 54, \ldots\) is a geometric progression with common ratio 3.
Similarly \(10, 5, 2.5, 1.25, \ldots\) is a geometric sequence with common ratio 1/2.
Examples of a geometric sequence are powers \(r_k\) of a fixed number r, such as 2k and 3k. The general form of a geometric sequence is \[a,\ ar,\ ar^{2},\ ar^{3},\ ar^{4},\ \ldots \] where \(r \neq 0\) is the common ratio and \(a\) is a , equal to the sequence’s start value.
A summation of a geometric progression, a geometric series, is the sum of the numbers in a geometric progression. For example: \[2+10+50+250=2+2\times 5+2\times 5^{2}+2\times 5^{3}.\,\]
Letting \(a\) be the first term (here 2), \(m\) be the number of terms (here 4), and r be the constant that each term is multiplied by to get the next term (here 5), the sum is given by: \[{\frac {a(1-r^{m})}{1-r}}\] In the example above, this gives: \[2+10+50+250={\frac {2(1-5^{4})}{1-5}}={\frac {-1248}{-4}}=312.\]
\[ u_n = u_{n-1} + u_{n-2} \qquad \mbox{ for } n \geq 3 ,\; u_1=0,\;u_2=1 \]
The first few terms of the Fibonnaci Sequence looks like this: \[ 1, 1, 2, 3, 5, 8, \ldots\]
\[ F_{n} = F_{n-1} + F_{n-2} \mbox{ For }\]
\[ F_{n} = F_{n-1} + F_{n-2} \mbox{ For }\]
A series is the sum of a sequence. For a given sequence \(a_0,a_1,a_2,a_3,\ldots,a_n,\ldots\) the terms in the corresponding series \(s_n\) are given by
\[ \begin{align*} s_0&=a_0 s_1&=a_0+a_1 s_2&=a_0+a_1+a_2 s_3&=a_0+a_1+a_2+a_3,\quad \text{etc} \end{align*} \]
The general term \(s_n\), which is the \(n^{th}\) term in the series, is given by \[ s_n=a_0+a_1+a_2+\cdots+a_{n-1}+a_n\] Note that
Let \(a_n=n^2\), So that the terms in the sequence are \(0,1,4,9,16,25,\ldots\)
\[\begin{align*} s_0&=0 s_1&=0+1=1 s_2&=0+1+4=5 s_3&=0+1+4+9=14,\quad \text{etc} \end{align*}\]
A geometric progression, also known as a geometric sequence, is a sequence of numbers where each term after the first is found by multiplying the previous one by a fixed, non-zero number called the .
For example, the sequence \(2, 6, 18, 54, \ldots\) is a geometric progression with common ratio 3.
Similarly \(10, 5, 2.5, 1.25, \ldots\) is a geometric sequence with common ratio 1/2.
Examples of a geometric sequence are powers \(r_k\) of a fixed number r, such as 2k and 3k. The general form of a geometric sequence is \[a,\ ar,\ ar^{2},\ ar^{3},\ ar^{4},\ \ldots \] where \(r \neq 0\) is the common ratio and \(a\) is a , equal to the sequence’s start value.
A summation of a geometric progression, a , is the sum of the numbers in a geometric progression. For example: \[2+10+50+250=2+2\times 5+2\times 5^{2}+2\times 5^{3}.\,\]
Letting \(a\) be the first term (here 2), \(m\) be the number of terms (here 4), and r be the constant that each term is multiplied by to get the next term (here 5), the sum is given by: \[{\frac {a(1-r^{m})}{1-r}}\] In the example above, this gives: \[2+10+50+250={\frac {2(1-5^{4})}{1-5}}={\frac {-1248}{-4}}=312.\]
Telescoping Series
A telescoping series is a series whose partial sums eventually only have a finite number of terms after cancellation.
The cancellation technique, with part of each term cancelling with part of the next term, is known as the method of differences.
Telescoping Series - Worked Example - HERE
In mathematics, a telescoping series is a series whose partial sums eventually only have a fixed number of terms after cancellation.
Such a technique is also known as the method of differences.
\[ \sum^{\infty}_{n=1} \frac{1}{n} - \frac{1}{n+1} \]
is telescoping.
In mathematics, a telescoping series is a series whose partial sums eventually only have a fixed number of terms after cancellation.[1][2] Such a technique is also known as the method of differences. For example, the series \[\sum_{n=1}^\infty\frac{1}{n(n+1)}\] simplifies as \[\begin{align} \sum_{n=1}^\infty \frac{1}{n(n+1)} & {} = \sum_{n=1}^\infty \left( \frac{1}{n} - \frac{1}{n+1} \right) \\ {} & {} = \lim_{N\to\infty} \sum_{n=1}^N \left( \frac{1}{n} - \frac{1}{n+1} \right) \\ {} & {} = \lim_{N\to\infty} \left\lbrack {\left(1 - \frac{1}{2}\right) + \left(\frac{1}{2} - \frac{1}{3}\right) + \cdots + \left(\frac{1}{N} - \frac{1}{N+1}\right) } \right\rbrack \\ {} & {} = \lim_{N\to\infty} \left\lbrack { 1 + \left( - \frac{1}{2} + \frac{1}{2}\right) + \left( - \frac{1}{3} + \frac{1}{3}\right) + \cdots + \left( - \frac{1}{N} + \frac{1}{N}\right) - \frac{1}{N+1} } \right\rbrack = 1. \end{align}\]
For example, the series \[\sum_{n=1}^\infty\frac{1}{n(n+1)}\] simplifies as \[\begin{align} \sum_{n=1}^\infty \frac{1}{n(n+1)} & {} = \sum_{n=1}^\infty \left( \frac{1}{n} - \frac{1}{n+1} \right) \\ {} & {} = \lim_{N\to\infty} \sum_{n=1}^N \left( \frac{1}{n} - \frac{1}{n+1} \right) \\ {} & {} = \lim_{N\to\infty} \left\lbrack {\left(1 - \frac{1}{2}\right) + \left(\frac{1}{2} - \frac{1}{3}\right) + \cdots + \left(\frac{1}{N} - \frac{1}{N+1}\right) } \right\rbrack \\ {} & {} = \lim_{N\to\infty} \left\lbrack { 1 + \left( - \frac{1}{2} + \frac{1}{2}\right) + \left( - \frac{1}{3} + \frac{1}{3}\right) + \cdots + \left( - \frac{1}{N} + \frac{1}{N}\right) - \frac{1}{N+1} } \right\rbrack = 1. \end{align}\]
Look at the partial sums:
\[ \sum^{n}_{i=1} \frac{1}{i} - 1/(i+1) = (1/1 - 1/2) + (1/2 - 1/3) + \ldots + (1/n - 1/(n+1))\]
\[= 1 - 1/(n+1)\]
because of cancellation of adjacent terms.
So, the sum of the series, which is the limit of the partial sums, is 1.
You do have to be careful; not every telescoping series converges. Look at the following series:
\[ \sum^{\infty}_{i=1} n - (n + 1) \]
You might at first think that all of the terms will cancel, and you will be left with just 1 as the sum.. But take a look at the partial sums:
\[ \sum^{n}_{i=1} - (i + 1) = (1 - 2) + (2 - 3) + \ldots + (n - (n + 1)) =\]
\[1 - (n + 1) =\] \[-n.\]
This sequence does not converge, so the sum does not converge. This can be more easily seen if you simplify the expression for the term. You find that
\[ \sum^{\infty}_{i=1} n - (n + 1) = \sum^{\infty}_{i=1} -1 \]
and any infinite sum with a constant term diverges.
Part 1 : Sequences
Part 2 : Proof by Induction
Part 3 : Series and the Sigma Notation
Sigma Notation [6.49]
Finite Series : Summation of a sequence.
Mathematical notation uses a symbol that compactly represents summation of many similar terms: the summation symbol, \(\sum\), an enlarged form of the upright capital Greek letter Sigma.
This is defined as: \[\sum_{i=m}^n a_i = a_m + a_{m+1} + a_{m+2} +\cdots+ a_{n-1} + a_n. \] Where, i represents the index of summation; \(a_i\) is an indexed variable representing each successive term in the series; \(m\) is the lower bound of summation, and \(n\) is the upper bound of summation. The “i = m” under the summation symbol means that the index i starts out equal to m.
The index, \(i\), is incremented by 1 for each successive term, stopping when \(i = n\).
Here is an example showing the summation of exponential terms (all terms to the power of 2): \[\sum_{i=3}^6 i^2 = 3^2+4^2+5^2+6^2 = 86.\]
Informal writing sometimes omits the definition of the index and bounds of summation when these are clear from context, as in: \[\sum a_i^2 = \sum_{i=1}^n a_i^2.\]
(index term = i , Number of terms = n }
For some integers \(m\) and \(n\), with \(m<n\).
\[ \sum^{i=n}_{i=1} u_{i} = \sum^{i=m}_{i=1} u_{i} + \sum^{i=n}_{i=m+1} u_{i}\]
Suppose \(n=100\) and \(m=50\)
\[ \sum^{i=100}_{i=1} u_{i} = \sum^{i=50}_{i=1} u_{i} + \sum^{i=100}_{i=51} u_{i}\]
Evaluate the following expression: \[ \sum^{i=100}_{i=51} (i+1) \]
Step 1 Evaluate this expression using the identities (notice the lower bound)
\[ \sum^{i=100}_{i=1} (i+1) \]
Step 2 From the outcome of step 1, subtract the following \[ \sum^{i=50}_{i=1} (i+1) \]
Evaluate the following expression using the identities. In this step \(n=100\)
\[ \sum^{i=100}_{i=1} (i+1) = \sum^{i=100}_{i=1} i + \sum^{i=100}_{i=1} 1 \]
\[ \sum^{i=100}_{i=1} (i+1) = 5050 + 100 = 5150 \]
Evaluate the following expression using the identities. In this step \(n=50\) \[ \sum^{i=50}_{i=1} (i+1) = \sum^{i=50}_{i=1} i + \sum^{i=50}_{i=1} 1 \]
\[ \sum^{i=50}_{i=1} (i+1) = 1275 + 50 = 1325 \]
\[ \sum^{i=100}_{i=51} (i+1) = \sum^{i=100}_{i=1} (i+1) - \sum^{i=50}_{i=1}(i+1) \]
\[ \sum^{i=100}_{i=51} (i+1) = 5150 - 1325 =\boldsymbol{3825} \]
Sigma Notation (6:49 Minutes)
Finite Series – HERE (4:40 Minutes)
Evaluating the Sum of a Series – HERE ( 3:12 Minutes)
Let the sequence \(u_n\) be defined by the recurrence relation: \[ u_{n+1} = u_n + 2n, \]
for \(n=1,2,3,\ldots\). \ Initial Condition: \(u_1=1\).
Calculate \(u_2\), \(u_3\), \(u_4\) and \(u_5\), showing all your workings.
Starting with \(n=1\), \[ u_{n+1} = u_n + 2n, \] \[ u_{(1)+1} = u_{1} + 2\times 1, \] \[ u_{2} = 1 + 2, \] \[ u_{2} = 3. \]
With \(n=2\), \[ u_{n+1} = u_n + 2n, \] \[ u_{(2)+1} = u_{2} + 2\times 2, \] \[ u_{3} = 3 + 4, \] \[ u_{3} = 7. \]
With \(n=3\), \[ u_{n+1} = u_n + 2n, \] \[ u_{(3)+1} = u_{3} + 2\times 3, \] \[ u_{4} = 7 + 6, \] \[ u_{4} = 13. \]
With \(n=4\), \[ u_{n+1} = u_n + 2n, \] \[ u_{(4)+1} = u_{4} + 2\times 4, \] \[ u_{5} = 13 + 8, \] \[ u_{5} = 21. \]
The first five elements of the sequence are as follows: \[ \{1,3,7,13,21, \ldots\} \]
A recurrence relation is an equation that recursively defines a sequence, once one or more initial terms are given: each further term of the sequence is defined as a function of the preceding terms.
The term difference equation sometimes refers to a specific type of recurrence relation.
However, “difference equation” is frequently used to refer to any recurrence relation.
Recurrence Relations
CIS102 2004 Question 7 2 Marks
Consider the sequence given by \[ 1, 4, 7, 10, 13, \ldots\]
State a recurrence relation which expresses the nth term, \(u_n\), in terms of the\((n - 1)\)th term, \(u_{n-1}\),
State a recurrence relation which expresses the nth term, \(u_n\), in terms of the first term \(u_1\).
\(u_1\) = 1 , \(u_2\) = 4, \(u_3\) = 7 etc
Difference in successive terms is 3.
Therefore we can say \[ u_n = u_{n-1} + 3 \]
Difference between \(u_2\) and \(u_1\) is 3 (i.e. \(1 \times 3\)).
Difference between \(u_3\) and \(u_1\) is 6 (i.e. \(2 \times 3\))
Difference between \(u_4\) and \(u_1\) is 9 (i.e. \(3 \times 3\))
In general the difference between \(u_n\) and \(u_1\) is \((n-1)\times 3\). \[ u_{n} = u_1 + 3 \times (n-1) \] \[ u_{n} = 1 + (3n-3) = 3n-2\]
Equivalently \[ u_{n+1} = u_1 + 3n = 3n+1\]
Another sequence is defined by the recurrence relation \[ u_n = u_{n-1} + 2n-1 \] and \(u_1\) = 1.
Calculate \(u_2\) , \(u_3\) , \(u_4\) and \(u_5\) .
(Answers 1,4,9,16,25)
\[\begin{array}{|c|c|c|c|} n & u_{n-1} & 2n-1 & u_n \\ \hline 2 & 1 & 3 & u_2 = 4 \\ \hline 3 & 4 & 5 & u_3 = 9 \\ \hline 4 & 9 & 7 & u_4 = 16 \\ \hline 5 & 16 & 9 & u_5 = 25 \\ \hline \end{array}\]
Many sequences are defined by a recursive rule. Here each term in the sequence is defined by previous terms. In order to begin the recursion, initial terms or must be specified. For example \[\begin{align*} &\begin{cases} a_0=&1\\ a_n=&n a_{n-1} \end{cases} \end{align*}\] \[\begin{align*} a_0=&1 & &\\ a_1=&1 \cdot a_0 = 1 &=&1 \\ a_2=&2 \cdot a_1 = 2 \cdot 1 &=&2 \\ a_3=&3 \cdot a_2 = 3 \cdot 2 \cdot 1 &=&6 \\ a_4=&4 \cdot a_3 = 4 \cdot 3 \cdot 2 \cdot 1 &=&24 \\ a_5=&5 \cdot a_4 = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 &=&120 \\ a_6=&6 \cdot a_5 = 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 &=&620 \end{align*}\]
This sequences defines the . \(n!\) is the product of the first \(n\) integers. \[ a_n = n! = n \cdot (n-1) \cdot \left( n-2 \right) \cdot \left( n-3 \right) \cdots 3 \cdot 2 \cdot 1 \] This sequence grows very rapidly, with \(10!=3628800\), and \(100! \cong 9.33 \times 10 ^{157}\) is a number greater than the number of atoms in the known universe. The factorial sequence is one of the fastest growing elementary sequences. Note that by convention \(0!=1\).
The Fibonacci sequence is defined by the following recursive rule. \[\begin{align*} &\begin{cases} f_0=&0; \quad f_1=1\\ f_n=&f_{n-1}+f_{n-2} \end{cases} \end{align*}\] The current term \(f_n\) in the sequence is the sum of the previous two terms. The first few elements of this sequence are listed in the table below.This sequence is named after the Italian mathematician Fibonacci, who introduced the base-ten Hindu-Arabic numeral system into Europe. Fibonacci consider the sequence to arise from a pairs of rabbits, which each produce a new pair of rabbits every month. After two months, each new pair becomes a breeding pair and increases the sequence. He showed that the number of rabbit pairs obeys the recursive rule \(f_n=f_{n-1}+f_{n-2}\), though there are other problems in which this sequence emerges – for example, when computing the golden ratio.
One difficulty with recursive sequences is that in order to find later values in the sequence, all previous terms in the sequence must be computed first. This makes it difficult to compute a term like \(f_{1000}\). In the case of the Fibonacci sequence, alternative formulas exist, but this will not be the case for many recursive sequences.
Both Heron’s method and the Fast Reciprocal algorithm can be represented as recursive sequences. The base case of the algorithms is the initial guess \(G\).
{} \[\begin{align*} &\begin{cases} h_0=&G\\ h_{n+1}=&\frac{1}{2} \left( h_n + \frac{S}{h_n} \right) \end{cases} \end{align*}\]
{} \[\begin{align*} &\begin{cases} r_0=&G\\ r_{n+1}=&r_n \left( 2-D r_n \right) \end{cases} \end{align*}\] The recursive rule can be written in terms of \(a_{n}\) or \(a_{n+1}\).
A recurrence relation, also known as a recursive relation, is an equation that defines a sequence of values using recursion. Each term in the sequence is defined as a function of one or more previous terms. Recurrence relations are widely used in computer science, particularly in the analysis of algorithms, and they also appear in various fields such as mathematics and economics.
Fibonacci Sequence: \[ F(n) = F(n-1) + F(n-2) \] with initial conditions \(F(0) = 0\) and \(F(1) = 1\).
Factorial: \[ T(n) = n \cdot T(n-1) \] with initial condition \(T(0) = 1\).
Arithmetic Sequence: \[ a_n = a_{n-1} + d \] with a given initial term \(a_1\).
Geometric Sequence: \[ a_n = r \cdot a_{n-1} \] with a given initial term \(a_1\).
To solve a recurrence relation means to find a closed-form expression (an explicit formula that does not involve recursion) for the sequence. Various methods exist for solving recurrence relations:
Example 1: Fibonacci Sequence Given: \[ F(n) = F(n-1) + F(n-2) \] with initial conditions \(F(0) = 0\) and \(F(1) = 1\).
Solution: The characteristic equation for this recurrence relation is: \[ x^2 = x + 1 \] Solving this quadratic equation, we find the roots: \[ x = \frac{1 \pm \sqrt{5}}{2} \] These roots are often denoted as \(\alpha = \frac{1 + \sqrt{5}}{2}\) and \(\beta = \frac{1 - \sqrt{5}}{2}\).
The general solution is: \[ F(n) = A \alpha^n + B \beta^n \] Using the initial conditions to find \(A\) and \(B\): \[ F(0) = A \alpha^0 + B \beta^0 = A + B = 0 \] \[ F(1) = A \alpha + B \beta = 1 \]
Solving these equations: \[ A + B = 0 \] \[ A \alpha + B \beta = 1 \] We find: \[ A = \frac{1}{\sqrt{5}}, \quad B = -\frac{1}{\sqrt{5}} \]
Thus, the closed-form solution is: \[ F(n) = \frac{1}{\sqrt{5}} \left( \left( \frac{1 + \sqrt{5}}{2} \right)^n - \left( \frac{1 - \sqrt{5}}{2} \right)^n \right) \]
Recurrence relations are particularly useful in analyzing the time complexity of recursive algorithms.
Example 2: Merge Sort The time complexity \(T(n)\) of Merge Sort can be described by the recurrence relation: \[ T(n) = 2T\left(\frac{n}{2}\right) + O(n) \] Using the Master Theorem, we can solve this recurrence relation to find that the time complexity is \(O(n \log n)\).
I hope this lesson helps you understand recurrence relations and their applications! Let me know if you have any questions or need further examples.
Let \(s_n = 1 + 3 + 5 + \ldots + (2n-1)\) for \(n \in Z^{+}\).\
[1.] Express \(s_n\) using \(\sigma\) notation.
[2.] Calculate \(s_1\) , \(s_2\) and \(s_3\).
[3.] Find a recurrence relation which expresses \(s_{n+1}\) in terms of \(s_n\).
Express \(s_n\) using \(\sum\) notation. \[s_n = 1 + 3 + 5 + \ldots + (2n-1) \mbox{ for }n \in Z^{+}\]
: Express \(s_n\) using \(\sum\) notation. \[s_n = 1 + 3 + 5 + \ldots + (2n-1) \mbox{ for }n \in Z^{+}\]
\[ \sum^{k=n}_{k=1} (2k-1) \]
Calculate \(s_1\), \(s_2\) and \(s_3\).
\[ \sum^{k=n}_{k=1} (2k-1) \]
Calculate \(s_1\), \(s_2\) and \(s_3\).
\[ \sum^{k=n}_{k=1} (2k-1) \]
[\(s_1\)] [\(s_2\)] [\(s_3\)]
Find the sum of the following geometric series \[ 3 + 6 + 12 + 24 + \ldots + 3072 \]
Find a recurrence relation which expresses \(s_{n+1}\) in terms of \(s_n\).
\[ S_n = {n \over 2} \left[ 2a+(n-1)d \right] \]
Recall \(a=11\),\(d=2\) and \(n=21\)
\[ S_n = {21 \over 2} \left[ (2.11) +[(21-1)2] \right] \] \[ S_n = 10.5 \left[ 22 + 40 \right] = 10.5 \times 62\] \[ S_n = 651 \]
Find the sum of the arithmetic progression
\[ 11 + 13 + 15 + \ldots + 49 + 51 \]
First recall two useful equations for working with arithmetic
progressions.
For the arithmetic sequence \(a,(a+d) ,(a+2d), \ldots\)
[(i)] \(t_n\) is the \(n-th\) term of series.\[ t_n= a+(n-1)d \]
[(ii)] \(S_n\) is the sum of the first \(n\) terms
\[ S_n = {n \over 2} \left[ 2a+(n-1)d \right] \]
Find the sum of the arithmetic progression { \[ 11 + 13 + 15 + \dots + 49 + 51 \] }
* The last term is \(51\). *
\(t_n\) = 51 = [ 11 + (n-1)2 ] * \(t_n\) = 51 = 2n + 9 * \(n=21\)
There are 21 terms in the series.
\[ S_n = {n \over 2} \left[ 2a+(n-1)d \right] \]
Recall \(a=11\),\(d=2\) and \(n=21\)
\[ \phantom{S_n = {21 \over 2} \left[ (2.11) +[(21-1)2] \right]} \] \[ \phantom{S_n = 10.5 \left[ 22 + 40 \right] = 10.5 \times 62}\] \[ \phantom{S_n = 651} \]
\[ S_n = {n \over 2} \left[ 2a+(n-1)d \right] \]
Recall \(a=11\),\(d=2\) and \(n=21\)
\[ S_n = {21 \over 2} \left[ (2.11) +[(21-1)2] \right] \] \[ S_n = 10.5 \left[ 22 + 40 \right] = 10.5 \times 62\] \[ S_n = 651 \]
Find \(S_n\), the sum of \(n\) terms, of the geometric series
\[ 2 + \frac{2}{3} + \frac{2}{3^2} + \frac{2}{3^3} + \ldots + \frac{2}{3^{n-1}} \]
If \(S_n\) = 242/81, find the value of \(n\).
\[ 2 + \frac{2}{3} + \frac{2}{3^2} + \frac{2}{3^3} + \ldots + \frac{2}{3^{n-1}} \] \[ \phantom{ 2 \times \left[ 1 + \frac{1}{3} + \frac{1}{3^2} + \frac{1}{3^3} + \ldots + \frac{1}{3^{n-1}} \right] } \]
\[ \sum^{n}_{r=0} x^r = \frac{x^{n+1}-1}{x-1} \] \[ \phantom{k \sum^{n}_{r=0} x^r = k \frac{x^{n+1}-1}{x-1} } \]
\[ 2 + \frac{2}{3} + \frac{2}{3^2} + \frac{2}{3^3} + \ldots + \frac{2}{3^{n-1}} \] \[ 2 \times \left[ 1 + \frac{1}{3} + \frac{1}{3^2} + \frac{1}{3^3} + \ldots + \frac{1}{3^{n-1}} \right] \]
\[ \sum^{n}_{r=0} x^r = \frac{x^{n+1}-1}{x-1} \] \[ k \sum^{n}_{r=0} x^r = k \left( \frac{x^{n+1}-1}{x-1} \right) \] Here \(k=2\) and \(x = 1/3\)
\[ k \sum^{n}_{r=0} x^r = k \left( \frac{x^{n+1}-1}{x-1} \right) \] Here \(k=2\) and \(x = 1/3\) \[ \phantom{ 2 \sum^{n}_{r=0} (1/3)^r = 2 \left( \frac{(1/3)^{n+1}-1}{(1/3)-1} \right) } \]
\[ k \sum^{n}_{r=0} x^r = k \left( \frac{x^{n+1}-1}{x-1} \right) \] Here \(k=2\) and \(x = 1/3\) \[ 2 \sum^{n}_{r=0} (1/3)^r = 2 \left( \frac{(1/3)^{n+1}-1}{(1/3)-1} \right) = \frac{242}{81} \]
\[2 \left( \frac{(1/3)^{n+1}-1}{(1/3)-1} \right) = \frac{-3}{4} \left[ (1/3)^{n+1}-1 \right] = \frac{242}{81} \]
\[ \frac{-3}{4} \left[ (1/3)^{n+1}-1 \right] = \frac{242}{81} \]
\[ \left[ (1/3)^{n+1}-1 \right] = \frac{-4}{3} \times \frac{242}{81} \]
\[ S_n = \frac{a(1-r)^n}{1-r} \] } * Sum to infinity of a geometric series
\[ \mbox{ when } 0 < r < 1 : S_{\infty} = \frac{a}{1-r} \]
Geometric Series- Example 1
\[ \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{16} +\ldots \]
Summation Theorem
\[ \sum^{n}_{r=0} x^r = \frac{x^{n+1}-1}{x-1} \]
Here \(x = 1/3\)
\[ 2 + \frac{2}{3} + \frac{2}{3^2} + \frac{2}{3^3} + \ldots + \frac{2}{3^{n-1}} \]
First recall two useful equations for working with Arithmetic Progressions
For the arithmetic sequence \(a,(a+d) ,(a+2d), \ldots\)
[(i)] \(t_n\) is the \(n-th\) term of series = \(a+(n-1)d\)
[(ii)] \(S_n\) is the sum of the first \(n\) terms
\[ S_n = {n \over 2} \left[ 2a+(n-1)d \right] \]
Find the sum of the arithmetic progression { \[ 11 + 13 + 15 + \dots + 49 + 51 \] }
There are 21 terms in the series.
\[ S_n = {n \over 2} \left[ 2a+(n-1)d \right] \]
Recall \(a=11\),\(d=2\) and \(n=21\)
\[ \phantom{S_n = {21 \over 2} \left[ (2.11) +[(21-1)2] \right]} \] \[ \phantom{S_n = 10.5 \left[ 22 + 40 \right] = 10.5 \times 62}\] \[ \phantom{S_n = 651} \]
\[ S_n = {n \over 2} \left[ 2a+(n-1)d \right] \]
Recall \(a=11\),\(d=2\) and \(n=21\)
\[ S_n = {21 \over 2} \left[ (2.11) +[(21-1)2] \right] \] \[ S_n = 10.5 \left[ 22 + 40 \right] = 10.5 \times 62\] \[ S_n = 651 \]
\[ S_n = \frac{a(1-r)^n}{1-r} \]
\[ \mbox{ when } 0 < r < 1 : S_{\infty} = \frac{a}{1-r} \]
\[ \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{16} +\ldots \]