TASK 4: SEQUENCE ,MATHEMATICAL INDUCTION, RECURSION

4.1DEFINITION OF SEQUENCE :

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

EXAMPLE :

1.  Consider the sequences  an where 

The list of the terms of this sequences beginning with a1 , namely.

Start with

EXAMPLE PROBLEM INVOLVING SEQUENCES

1.  Find the 30^th term If the first three terms of an arithmetic sequence are 3,8, and 13.

ü Use the below formula to find the n^th term of an arithmetic sequence.

ü h = a+(n-1)dwhere,

a = the initial term of the sequence

n = number of term

d = common different    d=8-3=5

ü so…

h = 3+(30-1)5

h = 3+(29)5

h = 148

:. The 30^th term of the arithmetic sequence is 148.

2.  Find five consecutive integers that sum up to 350.

ü Suppose the five integers were x, x+1, x+2, x+3, x+4. Their sum is 350

ü  so we have

        x + x+1 + x+2 + x+3 + x+4 = 350

5x + 10 = 350

x = 68

        :. The five integers are 68, 69, 70, 71, and 72  

Types of Sequences.

1)  Geometric sequences.

2)  Arithmetic sequences.

3)  Special number sequences
4)Lucas sequences 
5)The Fibonacci Numbers

Geometric progression

a sequence of the form

 

where the initial term a and the common ratio r are real numbers.

Remark: A geometric progression is a discrete analogue of the exponential function

~ EXAMPLE ~

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

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

Arithmetic progression

a sequence of the form

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

where the initial term a and the common difference d are real numbers.

Remark: An arithmetic progression is a discrete analogue of the linear function f (x) = dx + a.

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 1:

Let {an} be a sequence that satisfies the recurrence relation an = an−1 + 3 for n = 1, 2, 3, . . . ,

and suppose that a0 = 2. What are a1, a2, and a3?

Solution: We see from the recurrence relation that a1 = a0 + 3 = 2 + 3 = 5. It then follows

that a2 = 5 + 3 = 8 and a3 = 8 + 3 = 11.

EXAMPLE 2:

Let {an} be a sequence that satisfies the recurrence relation an = an−1 −an−2 for n =2, 3, 4, . . . ,

and suppose that a0 = 3 and a1 = 5. What are a2 and a3?

Solution: We see from the recurrence relation that a2 = a1 −a0 = 5 −3 = 2 and a3 = a2 −

a1 = 2 −5 = −3.We can find a4, a5, and each successive term in a similar way.

The initial conditionsfor a recursively defined sequence specify the terms that precede the first term where the recurrence relation takes effect. Recurrence relation together with its initial conditions determines a unique solution.

Fibonacci sequence

define a particularly useful sequence defined by a recurrence relation, f0, f1, f2, . . . , is defined by the initial conditions f0 = 0, f1 = 1,

and the recurrence relation

fn = fn−1 + fn−2

for n = 2, 3, 4, . .

Example:

Find the Fibonacci numbers f2, f3, f4, f5, and f6.

Solution: The recurrence relation for the Fibonacci sequence tells us that we find successive terms by adding the previous two terms. Because the initial conditions tell us that f0 = 0 and

f1 = 1, using the recurrence relation in the definition we find that

f2 = f1 + f0 = 1 + 0 = 1,

f3 = f2 + f1 = 1 + 1 = 2,

f4 = f3 + f2 = 2 + 1 = 3,

f5 = f4 + f3 = 3 + 2 = 5,

f6 = f5 + f4 = 5 + 3 = 8.

Example of question the Fibonacci sequences

Compound Interest with Compounding Several Times a Year
When an annual interest rate of i is compounded m times per year, the interest rate paid per period is i/m. For instance, if 3% = 0.03 annual interest is compounded quarterly, then the interest rate paid per quarter is 0.03/4 = 0.0075. For each integer k ≥ 1, let Pk = the amount on deposit at the end of the kth period, assuming no additional deposits or withdrawals. Then the interest earned during the kth period equals the amount on deposit at the end of the (k −1)st period times the interest rate for the period: interest earned during kth period = P k−1(i m). The amount on deposit at the end of the kth period, Pk, equals the amount at the end of the (k −1)st period, Pk−1, plus the interest earned during the kth period: Pk = Pk−1 + Pk−1(i m)= Pk−1(1+ i m). 5.6.4 Suppose $10,000 is left on deposit at 3% compounded quarterly.
     a. How much will the account be worth at the end of one year, assuming no additional deposits or withdrawals? 
b. The annual percentage rate (APR) is the percentage increase in the value of the account over a one-year period. What is the APR for this account?


Solution
     a. For each integer n ≥ 1, let Pn = the amount on deposit after n consecutive quarters, assuming no additional deposits or withdrawals, and let P0 be the initial $10,000. Then
by equation (5.6.4) with i = 0.03 and m = 4, a recurrence relation for the sequence P0, P1, P2,...is (1) Pk = Pk−1(1+0.0075) = (1.0075)·Pk−1 for all integers k≥1. The amount on deposit at the end of one year (four quarters), P4, can be found by successive substitution: (2) P0 = $10,000 (3) P1 = 1.0075·P0 = (1.0075)·$10,000.00 = $10,075.00 by (1) and (2) (4) P2 = 1.0075·P1 = (1.0075)·$10,075.00 = $10,150.56 by (1) and (3) (5) P3 = 1.0075·P2 ∼ = (1.0075)·$10,150.56 = $10,226.69 by (1) and (4) (6) P4 = 1.0075·P3 ∼ = (1.0075)·$10,226.69 = $10,303.39 by (1) and (5) Hence after one year there is $10,303.39 (to the nearest cent) in the account.
     b. The percentage increase in the value of the account, or APR, is 10303.39−10000 10000 = 0.03034 = 3.034%.

 
 

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, f₀ = 0 while f₁ = 1 but L₀ and L₁ can be of any number when we are dealing with Lucas sequence. (L is used to represent a Lucas sequence.).

   Example:

Construct a Lucas sequence, L_n with the initial condition,  L₀ = 4 while L₁ = 2.

Solution:

Lucas sequence pays no heed to the value of f₀ and f₁ 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 f₂, we find the sum of 2 previous terms before it. which is  f₁ and f₀.

L₂ = L₁ +  L₀

Given that f₀ = 4 and f₁ = 2.

L₂ =  2 + 4

L₂ =  6

Same technique used for other consecutive terms.

L₃ =  L₂ +  L₁

L₃ =  6 +  2

L₃ =  8

L₄ =  L₃ +  L₂

L₄ =  8 +  6

L₄ =  14

L₅ =  L₄ +  L₃

L₅ =  14 +  8

L₅ =  22

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

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

Example 6:

Write a squared number sequence, { a_n } for n = 2, 4, 6, 8, 10, ……

Solution:

{ a_n } = { n² }

{ n² } = 2², 4², 6², 8², 10², ……

{ n² } = 4, 16, 36, 64, 100, ……

Example of sequence used in computer programming.

Write a program that helps the user count his money. The program should ask how many RM1 the user has, then how many RM2, then how many RM5, then how many coins. Then the program should tell the user how much money he has, expressed in RM.

Your output should be as below:

How many RM1 do you have? 5

How many RM2 do you have? 2

How many RM5 do you have? 2

How many coins/cent do you have? 50

Your total money is RM 19.50.

Solution :

Output :

4.2 Mathematical Induction 1

List down the principle of Mathematical Induction.

Principle of Mathematical Induction

Let P(n) be a property that is defined for integers n, and let a be a fixed integer. Suppose the following two statements are true:

1.  P(a) is true.

2.   For all integers k ≥a, ifP(k) is true then P(k +1) is true. Then the statement for all integers n ≥a, P(n)is true.

Proving a statement by mathematical induction is a two-step process.

 The first step is called the basis step, and the second step is called the inductive step.

Method of Proof by Mathematical Induction Consider a statement of the form, “For all integers n ≥a, a property P(n) is true.” To prove such a statement, perform the following two steps: Step 1 (basis step): Show that P(a) is true. Step 2 (inductive step): Show that for all integers k ≥a, ifP(k) is true then P(k +1) is true. To perform this step, suppose that P(k) is true, where k is any particular but arbitrarily chosen integer with k ≥a. [This supposition is called the inductive hypothesis.] Then show thatP(k +1) is true.

Here is a formal version of the proof about coins previously developed informally.

Proposition 5.2.1

 For all integers n ≥ 8, nc / can be obtained using 3c / and 5c / coins.

Proof (by mathematical induction):

Let the property P(n) be the sentence

nc / can be obtained using 3c / and 5c / coins. ← P(n)

Show that P(8) is true:

P(8) is true because 8c / can be obtained using one 3c / coin and one 5c / coin.

Show that for all integers k≥8, if P(k) is true then P(k+1) is also true:

 [Suppose that P(k) is true for a particular but arbitrarily chosen integer k ≥ 8.

 That is:]

 Suppose that k is any integer with k ≥ 8 such that

kc / can be obtained using 3c / and 5c / coins. ← P(k)inductive hypothesis

[We must show that P(k +1) is true. That is:] We must show that

(k +1)c / can be obtained using 3c / and 5c / coins. ← P(k +1)

Case 1 (There is a 5 c / coin among those used to make up the kc /.):

 In this case replace the 5c / coin by two 3c / coins; the result will be (k +1)c /.

Case 2 (There is not a 5 c / coin among those used to make up the kc /.):

In this case, because k ≥ 8, at least three 3c / coins must have been used. So remove three 3c / coins and replace them by two 5c / coins; the result will be (k +1)c /. Thus in either case (k +1)c / can be obtained using 3c / and 5c / coins [as was to be shown].

[Since we have proved the basis step and the inductive step, we conclude that the propo- sition is true.]

EXPLAIN THE PROOF OF MATHEMATICAL INDUCTION

Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true for all natural numbers (positive integers). It is done by proving that the first statement in the infinite sequence of statements is true, and then proving that if any one statement in the infinite sequence of statements is true, then so is the next one.

A more precise definition of the principle of induction can be stated in terms of propositions about the natural numbers. A proposition P(i) about the natural numbers is a statement that for is either true or false each natural number i. For instance, P(i) could be "i is an even number". In that case P(4) would be true, but P(7) would be false. In these terms, induction is usually defined in the following manner.

The Principle Of Induction

If P(1) is true, and if whenever P(i) is true, we can infer the truth of P(i+1), then P(i) is true for all natural numbers i.

This makes sense because, if P(1) is true, then we know we can infer the truth of P(1+1) = P(2), which in turn means we can infer the truth of P(2+1) = P(3), and so on into infinity. Hence, we arrive at the most important fact about induction: if we can count, we probably use induction!

Two Example for Mathematical Induction

Example 1

Show that for each positive integer n, 1 + 2 + 3 + ... + n = n(n + 1) / 2

For each positive integer n, let S(n) be the statement 1 + 2 + 3 + ... + n = n(n + 1) / 2

Basis step: S(1) is the statement 1 = 1(1 + 1) / 2. Thus S(1) is true.

Inductive step: We suppose that S(k) is true and prove that S(k + 1) is true. Thus, we assume that   1 + 2 + 3 + ... + k = k(k + 1) / 2

and prove that

1 + 2 + 3 + ... + k + k + 1 = (k + 1)( k + 1 + 1) / 2

If we add k + 1 to both sides of the equality in S(k), then on the left side of the sum, we obtain the left side of equality in S(k + 1). Our hope is that the right of the sum equals the right side of S(k + 1).

Check: Adding K + 1 to both sides of S(k) get:

1 + 2 + 3 + ... + k + k + 1

= k(k + 1) / 2 + (k + 1)

= (k + 1)(k / 2 + 1)

= (k + 1)(k / 2 + 2 / 2)

= (k + 1)(k + 2) / 2

= (k + 1)(k + 1 + 1) / 2

If S(k) is true, then S(k + 1) is true.

Therefore, 1 + 2 + 3 + ... + n = n(n + 1) / 2 for each positive integer n.

Example 2

 Adding up Odd Numbers

1 + 3 + 5 + ... + (2n-1) = n2

Show it is true for n=1

1 = 12 is True

Assume it is true for n=k

1 + 3 + 5 + ... + (2k-1) = k2 is True

Now, prove it is true for "k+1"

1 + 3 + 5 + ... + (2k-1) + (2(k+1)-1) = (k+1)2 ... ?

Know that 1 + 3 + 5 + ... + (2k-1) = k2 (the assumption above), do a replacement for all but the last term:   k2 + (2(k+1)-1) = (k+1)2

Now expand all terms:   k2 + 2k + 2 - 1 = k2 + 2k+1

Simplify:   k2 + 2k + 1 = k2 + 2k + 1

So:   1 + 3 + 5 + ... + (2(k+1)-1) = (k+1)2 is True