Sequence and Series I: Arithmetic Sequence and Series

Sequence

A list of numbers that are in order represent a sequence. For example, there is an odd numbers sequence $\{1, 3, 5, ...\}$ and the Fibonaccifibonacci sequence {0, 1, 1, 2, 3, 5, 8, 13, …}, and so on.

The order of a sequence can be increasing, decreasing, or a combination of both.

We can define a rule for any sequence. For example, identify the starting point of a sequence or the difference between the two consecutive numbers in a sequence.

Series

The sum of a sequence is called series. For example the odd series will be $(1+3+5+7+9+...)$

---

Remember: The order matters in the case of a sequence, but a series is independent of the order. For example, $1, 2, 3$ is not the same as $3, 2, 1$ but $1+2+3$ is just as same as $3+2+1$. Similarly, the two sequences will have the same size if one sequence is the mirror image of the other. Like the following two sequences are of the same size (having $\log_2 n$ elements)

$$1,2,4,8, ... , n/4, n/2, n$$

A geometric sequence with a common ratio of $2$ and starting term is $1$ and end term is $n$.

$$n, n/2, n/4, ..., 8, 4, 2, 1$$

A decreasing geometric sequence with common a ratio of $1/2$ and starting term is $n$ and the end term is $1$.

---

Arithmetic sequence

By establishing a rule (keeping the difference between two consecutive numbers the same in a sequence) the sequence will be converted to arithmetic sequence. Let’s say $a$ is the very first number of a sequence $X$ and $d$ is the difference between two consecutive numbers of that $X$ then any term in $X$ can be extracted from the following rule:

$$X_n = a+d(n-1)$$

In simpler words, we can get $n^{th}$ number of the sequence by adding the first term of the sequence with the product of common difference and $n-1$.

The common difference is not used in the first term. The first term is only $a$ and the next term comes by adding $d$ to it, and so on. So the general sequence should like this:

$$X = a+0 \cdot d, a+d, a+2d , ... , a+(n-1)d$$

Arithmetic series (sum of natural numbers)

The arithmetic series is,

$$S_n = a+ (a+d) + (a+2d) + ... + (a+(n-1)d)$$

For example, for $a = 1$ and $d=1$, the above arithmetic sequence is nothing but the sum of the first $N$ positive integers.

$$S_n = 1+2+3+4+...+n$$

The sum of first $n$ natural numbers can be calculated using this rule:

$$S_n = \frac{n}{2}(n+1)$$

In order to understand why is it so, let’s calculate the sum of an arithmetic series $(1+2+3+...+9+10)$. According to the given formula:

$$S_{1...10} = \frac{10}{2}(10+1)=55$$

We get the sum to be 55, which is true, by adding the numbers from $1$ to $10$ on each slide. Let’s see if we can figure out how it’s done!

Firstly, in the above slides, each element of the series was paired. 1 is paired up with the last number 10, 2 is paired with the second last number 9 yielding 11 again, so a total of $10/2=5$ pairs are created, where the sum of each pair is $11$. Hence, the total sum will be $10/5\times11=55$.

Generally, for the sum of the first $n$ numbers, $1$ is paired with $n$ yielding ${1+n}$, 2 is paired with $n-1$ yielding $2+(n-1)=n+1$, and so on. So a total of $\frac{n}{2}$ pairs will be created, where the sum of each pair is $(n+1)$. Hence, the total sum will be $S_n = \frac{n}{2}(n+1)$.

Application of arithmetic series

Suppose we have an infinite number of planes and lines, lines can intersect each other to make regions, and our objective is to maximize the number of regions. Can we come up with a rule to find out the maximum number of regions for $n$ number of lines in a plane?

Directions

With no line drawn, the entire plane is just one region. By adding a line, a new region will be produced. Now, when we’ll add a new line, $2$ new regions will be created. Upon adding the third line, $3$ new regions will be created.

Solution

First of all, let’s visualize the pattern in the following slides.

Number of lines	New regions	Total number of regions
$0$	-	$1$
$1$	$1$	$1+(1)=2$
$2$	$2$	$1+(1+2)=4$
$3$	$3$	$1+(1+2+3)=7$
$4$	$4$	$1+(1+2+3+4)=11$
$\vdots$	$\vdots$	$\vdots$
n	n	???

Two things to note here:

1. We have $1$ region before any line, such asthe entire plane.
2. For maximizing the number of regions, each $i$'th newly added line should create the maximum number of new regions which is only possible if the $i$'th line not only intersects with every already present line that is $i-1$ previous line but also at a different point of intersection. Hence, creating $i$ new regions ($i-1$ for intersecting every line and +1 for dissecting the final region from where the line is exiting into the infinite space). Therefore, the total number of regions with $n$ lines are as follows:
   • $\space1+$ (initial empty infinite plane)
   • $\space \space \space+1$ (for the first line)
   • $\space \space \space+2$ (for the second line)
   • $\space \space \space+3$ (for the third line)
   • $\space \space \space+ ...$
   • $\space \space \space+ n$ (for the $n$'th line)
   • $= 1+ \frac{n \times (n+1)}{2}$

Exercise 1: Counting handshakes

On your first day at college, your social science teacher suggests that it would be a good idea for each student to meet every other student in the class. If there were $20$ students in the class,

1. How many total handshakes would happen?
2. What if there were $N$ students? Can you tell the total number of handshakes in terms of $N$?

Directions to look at the exercise

One student will shake hands with another student only once. For example, if we have A, B, and C, then A will shake hands with both B and C. But B will only shake hands with C because he has already shaken hands with A. Now, C does not need to shake hands with A or B because he has already shaken hands with them.

Exercise 2: Counting squares in a chess board

If we have an 8 x 8 chessboard, how many squares (within that chessboard) would there be in total? (64 is not the answer).