Sequence and Mathematical Induction

Sequences

Definition :

A sequence is an ordered list of numbers or object.A sequence is a function from subse of the set of integers (usually either the set {0,1,2,.......} or the set {1,2,3....} ) to a set S.We use the notation an to denote the image of the integer n.We call an a term of sequence.

Type of sequence

• Arithmetric progression
• Geometric progression
• Fibonacci sequence

Arithmetric progression

1. An arithmetric progression or arithmeric sequence is simply a sequence of number with a common difference and this common difference has to be constant.
2. In general,you can write a arithmetric sequence like this: 

                                   a ,a+d ,a+2d,a+3d ,......a+nd

                                a is the first term and d is the common difference.

 

Consider  a_n =2n + 1. Please write down the sequence of {a_n} starting from n = 1.

Solution:

a₁ = 2 (1) + 1= 3

a₂ = 2 (2) + 1= 5

a₃ = 2 (3) + 1= 7

a₄ = 2 (4) + 1= 9

a₅ = 2 (5) + 1= 11

Geometric progression

1. A geometric progression / sequence is a sequence of number where each term in the sequence is found by multiplying the previous ter with a unchanging number called the common ratio (r)
2. In general, you can write an geometric sequence like this:

                                         a is the first term and r is the common ratio
                                                            * r cannot be 0

 Let the initial term a = 3 and the common ratio is 2. Write a sequence of geometric progression starting from n = 0.

{ arⁿ }= 3, 3(2)¹, 3(2)², 3(2)³, 3(2)⁴, ……

Therefore, the geometrical progression { arⁿ } is 3, 6, 12, 24, 48, ……

Recurrence Relation

Recurrence relation is a way of expressing each term in a sequence by referring to its previous terms before the specified term.

Given that a_n is dictated by a_n-1 times 2. So, when a₁ is 1. The values for the sequence is
a₂ = 2 (a₁ ) = 2 (1) = 2.

a₃ = 2 (a₂ ) = 2 (2) = 4

a₄ = 2 (a₃ ) = 2 (4) = 8.

 So, the solution to the sequence is 1, 2, 4, 8, 16......

Initial condition

An initial condition of a sequence with recurrence relation states the first term that would occur as the starting point of the sequence. Refer to Example 5, as we can see that the question stated if a₀ = 1. The expression  a₀ = 1 is the initial condition for the sequence { a_n }. This means that the sequence { a_n } starts with the term a₀, which is 1. Then followed by a₁, a₂, a₃, a₄, …… We can also say that a₀ is the starting term of the sequence { a_n }

Special number sequences

Special number sequences are derived from arithmetic sequence or geometrical sequence, or sometimes both. The terms in a special number sequence are arranged in such a way it can indirectly represents a mathematical theorem or a formula.

Squared Number Sequence

As the name of the sequence has told, a squared number sequence consists of the list of squared terms. Each term is represented by the form of n² for any real number

Solution:

{ a_n } = { n² }

{ n² } = 1², 2², 3², 4², 5² ……

therefore the solution to this  sequence will be:

{ n² } = 1, 4, 9, 16, 25 ……

This special number sequence had indirectly showed us the theorem of squared numbers and showed the squared numbers starting from n = 1 in a sequence.

 

Fibonacci sequence

The fibonacci sequence , f0,f1,f2......, is defined by the initial conditions f0 = 0 , f1=1 and recurrence relation.

                                                                   fn = fn-1 + fn-2

for n = 0,1,1,2,3,5,8,13,21,34...

MATHEMATICAL INDUCTION

Let’s say in a can of Mister Potato, there is an immeasurable amount of potato chips inside. So,

Q(n) : We want to be able to reach all the potato chips in the can.

To prove that ∀n Q (n) is true, we will need to eat the all chip in the can to prove that we can reach all the chips in the can. Since the potato chips are too many to count, we can’t possible finish counting before getting ourselves diabetes and high blood pressure. Therefore, we say that if we need to eat through n number of chips if we want to reach the n^th piece of chips in the can.

For example, we have to eat 99 pieces of potato chips to reach the 100^th piece of potato chips.

So, we propose

P (n): we must finish n piece of potato chips before we can reach the (n+1)^th piece of potato chips.
Since P(n) is true for all values of n, then we can also conclude that Q(n) is true, which states that we can reach any number of chips as long as we finishes the chips before the target.

The technique that we’ve used in the above example to determine if all the values are true or not, is called mathematical induction.

The Method of Proof by Mathematical Induction

Let a statement P be true with any natural number, n.

To prove the statement by induction, there are 2 steps that we need to do:

1.     The basis step:

Initially we assume n = 1. We prove P (1) is true.

2.     The inductive step:

After the basis step, we prove that if P (n) is true, then P (n + 1) is true. While n represents any natural numbers.