Summary
IVocabulary and key conceptsAVocabularyBRecursive and explicit sequencesIIArithmetic and geometric sequencesAArithmetic sequencesBGeometric sequencesIIIMathematical inductionAPrincipleBUse of mathematical inductionVocabulary and key concepts
Vocabulary
Sequence
A sequence of numbers is an infinite ordered list of numbers.
The following is an example of a sequence:
\{1{,}3{,}5{,}7,\ldots\}
The dots " \ldots " are used to indicate that the list of numbers continue on forever with respect to the pattern indicated by the first several terms.
The sequence above is the sequence of odd numbers.
Term
Suppose \{a_1,a_2,a_3,\ldots\} is a sequence of numbers. If n is a natural number then the number appearing in the n th spot of the sequence is referred to as the n th term of the sequence.
Consider the sequence of positive even numbers:
\{2{,}4{,}6{,}8,\ldots\}
Then we have the following:
- The fourth term of the first sequence is 8.
- The third term of the first sequence is 6.
- If n is a natural number then the n th term of the sequence is 2n.
Recursive and explicit sequences
Recurrence equation
A recurrence equation is an equation that recursively defines a sequence of numbers.
Consider the following recurrence equation:
a_{n+1}=a_n+a_{n-1}+3
If \{a_1,a_2,\cdots\} is a sequence of numbers such that a_{10}=9 and a_{11}=10, then we have the following:
- a_{12}=a_{11}+a_{10}+3=10+9+3=22
- a_{13}=a_{12}+a_{11}+3=22+10+3=35
Recursive sequence
A recursive sequence \{a_1,a_2,a_3,\ldots\} is a sequence of numbers generated by a recurrence equation and a finite number of terms.
Let \{a_1,a_2,a_3,\ldots\} be the sequence with the following properties:
- a_0=3
- For any natural n\geq1, a_n=a_{n-1}+5
Then the sequence is a recursive sequence and the recursive equation is a_n=a_{n-1}+5.
The following list is the first few terms of this sequence:
3{,}8{,}13{,}18{,}23,\ldots
Some recursive sequences are determined by more than one term and a recursive equation.
Let \{a_1,a_2,a_3,\ldots\} be the sequence with the following properties:
- a_1=1
- a_2=1
- For all n\geq 3 let a_n=a_{n-1}+a_{n-2}
Then the sequence is a recursive sequence and the recurrence equation is a_n=a_{n-1}+a_{n-2}.
The following list is the first few terms of this sequence:
1{,}1{,}2{,}3{,}5{,}8{,}13{,}21{,}34{,}55{,}89,\ldots
Observe that each term is the sum of the previous two terms.
Given the beginning of a sequence of numbers \{a_1,a_2,a_3,\ldots\} it is useful to identify a pattern in order to study higher terms of the sequence. This can be accomplished by identifying a recurrence equation.
Consider the following sequence:
\{1,-1,-5,-13,-29,\ldots\}
The difference between the first two terms is:
-1-1=-2
The difference between the third term and second term is:
-5-\left(-1\right)=-4
The difference between the fourth term and third term is:
-13 -\left(-5\right)=-8
The difference between the fifth term and the fourth term is:
-29-\left(-13\right)=-16
Therefore the sequence satisfies the following recurrence equation:
a_n-a_{n-1}=-2\left(n-1\right)
The above recurrence equation is also equivalent to:
a_n=a_{n-1}-2\left(n-1\right)
If you are given the first few terms of a sequence, then one can only take an educated guess at the pattern of the sequence.
Consider the following sequence of numbers:
\{2{,}2{,}0,-2,\ldots\}
There are four terms of the sequence given so we can try and guess the explicit pattern to the sequence. However, nothing is for certain unless we are given an explicit recurrence equation.
The above sequence could be defined by a number of different recurrence equations. For example, it is possible that the above sequence is defined by one of the following:
- a_1=a_2=2 and a_n=a_{n-1}-a_{n-2} for all n\geq 3
- a_1=2 and a_n= a_{n-1}-2^{n-2} for all n\geq 2
Explicit sequence
An explicit sequence is a sequence of numbers \{a_1,a_2,a_3,\ldots\} such that for each natural number n the n -term of the sequence is defined by an explicit formula which only depends on n.
Consider the sequence of numbers such that:
For any natural n, a_n=n^2+1.
Then the sequence is an explicit one. The following list is the first terms of the sequence:
2{,}5{,}10{,}17,\ldots
A sequence can sometimes be explicit and recursive.
Consider the sequence of odd numbers \{1{,}3{,}5{,}7{,}9,\ldots\}.
The sequence is recursive because for each n :
a_{n+1}=a_{n}+2
However, the sequence is also explicit because the n th term of the sequence is given by the following explicit formula:
a_n=2\left(n-1\right)+1
Arithmetic and geometric sequences
Arithmetic sequences
An arithmetic sequence is a sequence of numbers such that the difference between any two consecutive terms agree.
Arithmetic sequence
A sequence of numbers \{a_1,a_2,a_3,\ldots\} is an arithmetic sequence if there is a constant c such that for each n :
a_{n+1}=a_n+c
Consider the recursive sequence numbers defined by a_1=7 and a_n=a_{n-1}+4 for all n\geq 2.
\{7{,}11{,}15{,}19{,}23,\ldots\}
The sequence is an arithmetic sequence since the difference of any two consecutive terms is 4.
A sequence \{a_n\} is demonstrated to be arithmetic by showing that there exists a constant c so that for each n :
a_{n}-a_{n-1}=c
Consider the following sequence of odd numbers:
\{1{,}3{,}5{,}7,\ldots\}
The sequence is an arithmetic sequence because the difference of two consecutive odd numbers is always 2.
Let's consider an arithmetic sequence of numbers \{a_0,a_1,a_2,a_3,\ldots\} such that for each n :
a_{n+1}=a_n+c
The sequence can also be written explicitly. For any natural n:
a_n=a_0+n.c
Let's consider the arithmetic sequence defined by a_0=2 and a_n=a_{n-1}+3 for all n\geq 1. The sequence is also defined as:
For any natural number n, a_n=2+3n
Geometric sequences
A geometric sequence is a sequence of numbers such that the ratio of any two consecutive numbers agree.
Geometric sequence
A sequence of numbers \{a_1,a_2,a_3,\ldots\} is said to be geometric if there is a constant c such that for each n :
a_{n+1}=ca_n
Consider the sequence of numbers defined by a_1=1 and a_n=2a_{n-1} for all n\geq 2. The sequence is geometric because for each n :
a_{n+1}=2a_n
The first terms of the sequence are:
1{,}2{,}4{,}8{,}16{,}32,\ldots
Consider the following sequence of numbers defined by a_1=6 and a_n=\dfrac{1}{2}a_{n-1} for all n\geq 2. The sequence is a geometric sequence because for each n we have:
a_{n+1}=\dfrac{1}{2}a_n
The first terms of the sequence are:
6, 3, \dfrac{3}{2}, \dfrac{3}{4},\ldots
A sequence \{a_n\} is shown to be geometric by showing that there is a constant c such that for any natural number n:
\dfrac{a_{n+1}}{a_{n}}=c
The sequence \{a_n\} defined by a_n=2^n is a geometric sequence because, for any number n:
\dfrac{a_{n+1}}{a_n}=\dfrac{2^{n+1}}{2^2}\\=2^{n+1-n}\\=2
Let's consider the geometric sequence of numbers \{a_0,a_1,a_2,a_3,\ldots\} such that for each n :
a_{n+1}=a_n.c
The sequence can also be written explicitly. For any natural n:
a_n=a_0.c^n
Let's consider the arithmetic sequence defined by a_0=2 and a_n=3a_{n-1} for all n\geq 1. The sequence is also defined as:
For any natural number n, a_n=2.3^n.
Mathematical induction
Principle
Mathematical induction is a method of proving mathematical statements indexed by natural numbers.
Before going through the process of how mathematical induction works, let's first explain its governing principle through an example.
Let's suppose we study genealogy and we wish to show that every member of a family posses gene X. To do this we can trace back a family's heritage and show that a distant relative carried gene X. We then prove that this family member passed gene X to their children and they passed gene X to their children and so on. In conclusion, we have inductively shown that every member of a family posses the gene X.
Principal of mathematical induction
For every natural number n let P\left(n\right) be a mathematical statement. Suppose the following:
- The mathematical statement P\left(1\right) is true.
- For every natural number k the assumption that P\left(k\right) is true implies that P\left(k+1\right) is also true.
Then the mathematical statement P\left(n\right) is true for every natural number n.
The principal of mathematical induction can be used to prove the following statement for every natural number n\geq 1 :
P\left(n\right) "The number 11^n-1 is divisible by 10."
Proof for n=1
The statement P\left(1\right) is:
" 11^1-1=10 is divisible by 10 "
It is indeed a true statement.
Proof of recurring pattern
To complete the proof, let's consider a natural number k. We assume the statement P\left(k\right) is true and show that P\left(k+1\right) is true.
Therefore we assume 11^k-1 is divisible by 10 and prove 11^{k+1}-1 is divisible by 10. Therefore we are assuming that there exists an integer N such that 11^k-1=10 N.
Therefore:
11^{k+1}-1=11\cdot 11^{k}-1\\=11\cdot\left(10 N+1\right)-1\\=11\cdot 10 N+11-1\\=11\cdot 10 N +10\\=10\left(11 N+1\right)
Therefore 11^{k+1}-1 is also divisible 10. P\left(k+1\right) is true.
Conclusion
By mathematical induction 11^n-1 is divisible by 10 for every natural number n\geq 1.
Use of mathematical induction
Mathematical induction can be used to prove the following formula:
1+2+\cdots +n=\dfrac{n\left(n+1\right)}{2}
In the setup of mathematical induction, the mathematical statement P\left(n\right) is:
" 1+2+\cdots +n=\dfrac{n\left(n+1\right)}{2} "
Proof for n=1
Begin by checking the validity of P\left(1\right):
\dfrac{1\left(1+1\right)}{2}=1
Therefore P\left(1\right) is a true statement.
Proof of recurring pattern
Let k be a natural number. We assume the mathematical statement P\left(k\right) and try to show the validity of the mathematical statement P\left(k+1\right).
Consider the sum of the first k+1 natural numbers:
1+2+\cdots +k+k+1
We are assuming P\left(k\right) is valid, that is:
1+2+\cdots +k=\dfrac{k\left(k+1\right)}{2}
Therefore we have the following:
1+2+\cdots +k+k+1=\left(1+2+\cdots +k\right)+\left(k+1\right)\\=\dfrac{k\left(k+1\right)}{2}+k+1\\=\dfrac{k\left(k+1\right)}{2}+\dfrac{2k+2}{2}\\=\dfrac{k^2+3k+2}{2}\\=\dfrac{\left(k+1\right)\left(k+2\right)}{2}
P\left(k+1\right) is true. We have shown the mathematical statement P\left(k+1\right) is implied by the mathematical statement P\left(k\right).
Conclusion
Therefore by mathematical induction:
1+2+\cdots +n=\dfrac{n\left(n+1\right)}{2}
for every natural number n\geq 1.
Mathematical induction can be used to prove the sum of the first n odd numbers is n^2. That is for each natural number n\geq 1 :
1+3+5+\cdots +\left(2n-1\right)=n^2
In the setup of mathematical induction, the mathematical statement P\left(n\right) is:
" 1+3+5+\cdots +\left(2n-1\right)=n^2 "
Proof for n=1
Begin by checking validity of the mathematical statement P\left(1\right) :
1=1^2
Therefore the mathematical statement P\left(1\right) is valid.
Proof of recurring pattern
Let k be a natural number.
We assume that the mathematical statement P\left(k\right) is valid and try to derive the mathematical statement P\left(k+1\right). Therefore we assume the following:
1+3+5+\cdots + \left(2k-1\right)=k^2
and we try to prove the following:
1+3+5+\cdots +\left(2\left(k+1\right)-1\right)=\left(k+1\right)^2
This is done as follows:
1+3+5+\cdots +\left(2\left(k+1\right)-1\right)\\=1+2+3+\cdots +\left(2k-1\right)+\left(2\left(k+1\right)-1\right)\\=k^2+2k+1\\=\left(k+1\right)^2
P\left(k+1\right) is true.
Conclusion
Therefore by mathematical induction the sum of the first n odd numbers is n^2.