Group Members

  • Pang Kok An 032195
  • Muhd. Faiz Fahimi B. Razali 033225
  • Hasyazid B. Osman 033147
  • Nurul Nabilah Bt. Azman 032236
  • Nurul Fasihah Bt. Che Azmi 032220
  • Siti Aminah Bt. Ahmad Sahrel 032806
  • Roshatul Hidaya Bt. Rosdin 032558
  • Nusaibah Bt. Yahaya 032357

Sunday 17 March 2013

SEQUENCES



Sequences

A sequence is a method of representing a list of ordered terms by using the pattern of  a1, a2, a3, …… such as 1, 2, 3, 4, 5, …… , 3, 5, 7, 9, 11 and so on.


Example 1:

Given xn = n, show the sequence of {xn} from n = 1. 

Solution:

When we come across with sequence such as x1, x2, x3, …. We often denote a sequence with {xn}, which means that a sequence is actually the list of elements in a set.

To show the sequence of xn, just substitute numbers starting from 1 to n. Therefore we can get a sequence like this:

{ xn } = x1, x2, x3, x4, x5, …

{ xn } = ( x1 = 1 ), ( x2 = 2 ), ( x3 = 3 ), ( x4 = 4 ), ( x5 = 5 ), …

{ xn } = 1, 2, 3, 4, 5, …


Example 2:

an = 2x – 1, find {an} starting from n = 2.

Solution:

Just as the example above, substitute the values starting from n = 2. Therefore you would get:

{an} = 2(2)-1, 2(3)-1, 2(4)-1, 2(5)-1, 2(6)-1, …

{an} = 3, 5, 7, 9, 11, …


Types of Sequence

There are commonly 3 types of sequences. The geometric sequence, the arithmetic sequence and the special number sequence. 

 



Geometric Progression

Geometric progression is a sequence with a pattern like a, arn, arn+1, arn+2, ……, where a is the intial term of the sequence and r is the common ratio. Each of the term has a common ratio with the terms just before and after them.

Example 3:

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

{ arn }= a, arn, arn+1, arn+2, ……
{ arn }= 3, 3(2)1, 3(2)2, 3(2)3, 3(2)4, ……
{ arn }= 3, 6, 12, 24, 48, ……

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


Arithmetic Progression

Arithmetic Progression is a sequence with a pattern like a, a + nd, a + (n + 1) d, a + (n + 2) d, ……, where a is the intial term of the sequence and d is the common difference. Each term in arithmetic progression has the same difference with the terms next to it.

Example 4:

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

Solution:

a1 = 1 + 3 (1) = 4
a2 = 1 + 3 (2) = 7
a3 = 1 + 3 (3) = 10
a4 = 1 + 3 (4) = 13
a5 = 1 + 3 (5) = 16

Therefore the sequence for arithmetic progression, {an} is 4, 7, 10, 13, 16, ……


Recurrence Relation

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


Example 5:

Given an = an-1 + 2. Find {an} starting from n = 1, if a0 = 1.

Solution:

From the given statement an = an-1 + 2, In order to find an-1, we have to determine the previous term for an, which is an-1. To determine an-1, we need its previous term too, which is an-2. This method of solving a term by using its previous term depicts the recurrence relation. 

Since the question stated starting from n=1 start with a1. As the statement an = an-1 + 2 had mentioned, a1 should be a1 = a0 + 2. Since a0 = 1 is given, therefore a1 = 1 + 2 = 3.

For a2, a3 and the rest of the terms, we just carry out the same process as what we did to find a1.

a2 = a1 + 2
a2 = 3 + 2
a2 = 5

a3 = a2 + 2
a3 = 5 + 2
a3 = 7

a4 = a3 + 2
a4 = 7 + 2
a4 = 9

The sequence, { an } = 3, 5, 7, 9, …


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 a0 = 1. The expression  a0 = 1 is the initial condition for the sequence { an }. This means that the sequence { an } starts with the term a0, which is 1. Then followed by a1, a2, a3, a4, …… We can also say that a0 is the starting term of the sequence { an }

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.

There are many examples that show the characteristics of a typical special number sequence. Let us look at some of them.


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 n2 for any real number


Example 6:

Write a squared number sequence, { an } for n = 1, 2, 3, 4, 5, ……


Solution:

{ an } = { n2 }

{ n2 } = 12, 22, 32, 42, 52, ……

{ n2 } = 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.

Another example of special number sequence is Fibonacci sequence.


Fibonacci Sequence

A Fibonacci sequence is a sequence in which obeys the initial condition that f0 = 0 and f1 = 1 (We use f to represent terms in a Fibonacci sequence). The rest of the terms is just merely the addition of the previous 2 terms before the appointed term.


Example 7:

Write a Fibonacci sequence, fn from n = 2 to n = 6.

Solution:

The initial condition for a Fibonacci sequence is f0 = 0 and f1 = 1. As the definition had defined, a term is the sum of 2 previous terms before it. Therefore, to find f2, we have to sum up f1 and f0.

f2 =  f1 +  f0

In the initial condition, it is given that f0 = 0 and f1 = 1.

f2 =  1 + 0

f2 =  1

We use the same technique to find other consequtive terms.

f3 =  f2 +  f1

f3 =  1 +  1

f3 =  2


f4 =  f3 +  f2

f4 =  2 +  1

f4 =  3


f5 =  f4 +  f3

f5 =  3 +  2

f5 =  5


f6 =  f5 +  f4

f6 =  5 +  3

f6 =  8


Therefore, the Fibonacci sequence, { fn } from n = 2 = 1, 2, 3, 5, 8, ……


Lucas sequence

A lucas sequence works similarly like a Fibonacci sequence. The differences between 2 of them is the initial condition, in which in Fibonacci sequence, f0 = 0 while f1 = 1 but L0 and L1 can be of any number when we are dealing with Lucas sequence. (L is used to represent a Lucas sequence.).


Example 8:

Construct a Lucas sequence, Ln with the initial condition,  L0 = 4 while L1 = 2.

Solution:

As mentioned earlier, Lucas sequence pays no heed to the value of f0 and f1 as they can be of any value.

We’ll be using the same technique as what we’ve done in constructing the Fibonacci sequence.

To find f2, we find the sum of 2 previous terms before it. which is  f1 and f0.

L2 = L1 +  L0

Given that f0 = 4 and f1 = 2.

L2 =  2 + 4

L2 =  6

Same technique used for other consecutive terms.

L3 =  L2 +  L1

L3 =  6 +  2

L3 =  8


L4 =  L3 +  L2

L4 =  8 +  6

L4 =  14


L5 =  L4 +  L3

L5 =  14 +  8

L5 =  22

Therefore, the Lucas sequence, { Ln } from n = 2 = 6, 8, 14, 22, ……



Use of Sequence in Computer Programming

Sequence is very useful in the field of programming.


Example 9:

Every year, 10% of students graduated from SPM is chosen arbitrarily to must attend the National Service, which we usually called it as PLKN. 

 

You are asked to write a program for PLKN in which the program can choose arbitrarily the participants for them.

Solution:

We can use the concept of sequence here. For example, the list of all SPM students are key in in the database. Each of them has a unique ID. Therefore, the first student in the list might get an ID of 1 while the second student gets an ID of 2. Same as the rest of them. The sequence of all the students ID listed should look like this:

1, 2, 3, 4, 5, 6, ……

We take the first 10 students in the list for example:

ID
Name
1
Alex Soh Chye Wat
2
Chew Xiang Leng
3
Goh Yoon Kiat
4
Fatimah Che Bakri
5
Muhammad Kushairi
6
Chee Bai Kia
7
Lim Lao Bu
8
Goh Song Chiang
9
Karshan a/l Rajendran
10
Nanthini a/p Gunasegaran

We can make a Java program that reads the input from the user.








For example, a user input 2 as the number. Therefore, all the students with the ID which is divisible by 2 are chosen to enter PLKN. The ID which can be divisible by 2 can be presented in a sequence form like this:

2, 4, 6, 8, 10, ……

Therefore, refer to the table of ID and students’ name, we can know that Chew Xiang Leng, Fatimah Che Bakri, Chee Bai Kia, Goh Song Chiang and Nanthini a/p Gunasegaran are chosen for the PLKN programme.

If the user inputs 3, means that the ID 3, 6, 9, …… would be chosen. Refer to the table, Goh Yoon Kiat, Chee Bai Kia and Karshan a/l Rajendran are chosen for PLKN. 


 

Mathematical Induction

Suppose that we have a skyscraper with infinite height. We need to determine if we are able to reach all of the floors of the skyscraper. 


 
Let P(n) = We can reach the nth floor of the skyscraper.

To prove that ∀ n P(n) is true, we have to go through all the floors to prove it. Since the skyscraper has infinite height, there are infinite floors in the skyscraper. We can’t go through each floor to proof  ∀ n P(n). In this case, we have to use another more simpler way to proof it.

We know that, to reach the first floor, we must go through the ground floor first. Same as any other floors of the skyscraper. For example, if we want to reach the 37th floor, we must access the 36th floor first. So as the 201st floor, we have to get through the 200th in order to reach 201st.

From the above examples, we can deduce a statement like this:

Q (n) = We’ve to go through the nth floor first before we can go to the (n + 1)th floor.

Since Q(n) is true for all the floors in the skyscraper, therefore we can proof that ∀ n P(n) is true, which is we can access to each of the floors after we’ve accessed the previous floor.

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.

After the above 2 steps, we are able to prove that P(n) is true for all values of n. 

Because there are technical errors when doing with the example part, so please view the example from this link:
Click Here For Examples 

If this link fails, copy this into your URL bar. 

https://doc-10-bc-docs.googleusercontent.com/docs/securesc/qj9hdibv4bf8i64gm1a8hskjlae3h5dq/pphkosutvrp1joullsrvri3rhub05qla/1368007200000/06042155070242527045/06042155070242527045/0BzGLj71LFdH0Wk5MMUwxbE4zcG8?e=download