4th Task


TAF3023: Discrete Mathematic Task 4: Sequences, Mathematical Induction and Recursion

4.1 Sequences
- Definition of sequence
- Example problem involving sequence.
-Types of sequence
-Give 1 example sequences use in computer programming

4.2 Mathematical Induction 1
-List down the principle of Mathematical Induction.
-Explain the method of Proof by mathematical Induction
-Give 2 example problems that use for solving mathematical induction.
_________________________________________________________________________________

4.1) SEQUENCES
A)Definition of sequences.
a)-Sequence is a function from a subset of the natural numbers(usually of the form {0, 1, 2, . . . } to a set S.  

-For an example:-
   A={0,1,2,3,4…….x} and  B={1,2,3,4……..x}
                  are called initial segments of N.
b)-Geometric progression is a sequence of the form
             a,ar,ar2,ar3………,arn,….
-Geometric progression is a discrete analogue of the exponential function f(x)=arn.
-Example:-
The sequence bn=(-1)n. We start with n=0. Initial term and common ratio equal to 1 and −1.The list of the term begins with b0,b1,b2,b3
1,−1, 1,−1, 1, . . . ;
c) -An arithmetic progression is 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.

-An arithmetic progression is a discrete analogue of the linear function
 f (x) = dx + a.
 -Example:-
The sequence of sn=-1+4n.We start at n=0. Initial terms and common differences equal to −1 and 4. The list of terms s0, s1, s2, s3, . . . begins with
                                                −1, 3, 7, 11, . . . ,
d) -A recurrence relation for the sequence {an} is an equation that expresses an in terms of one or more of the previous terms of the sequence, namely, a0, a1, . . . , an−1, for all integers n with n ≥ n0, where n0 is a nonnegative integer. A sequence is called a solution of a recurrencerelation if its terms satisfy the recurrence relation.

- 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?

- Example:-

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?

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.

e) The Fibonacci sequence, 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.
                        
The recurrence relation for the Fibonacci sequence tells us that we find successive erms 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             
      

4.1) SEQUENCES
A)Definition of sequences.
a)-Sequence is a function from a subset of the natural numbers(usually of the form {0, 1, 2, . . . } to a set S.  

-For an example:-
   A={0,1,2,3,4…….x} and  B={1,2,3,4……..x}
                  are called initial segments of N.

B)Types of sequences 
1)-Geometric progression is a sequence of the form

-Geometric progression is a discrete analogue of the exponential function f(x)=arn.
-Example:-
The sequence bn=(-1)n. We start with n=0. Initial term and common ratio equal to 1 and −1.The list of the term begins with b0,b1,b2,b3
1,−1, 1,−1, 1, . . . ;


2) -An arithmetic progression is a sequence of the form 

-An arithmetic progression is a discrete analogue of the linear function
 f (x) = dx + a.
 -Example:-
The sequence of sn=-1+4n.We start at n=0. Initial terms and common differences equal to −1 and 4. The list of terms s0, s1, s2, s3, . . . begins with
      −1, 3, 7, 11, . . . ,


3)The Fibonacci sequence, 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.
                        
The recurrence relation for the Fibonacci sequence tells us that we find successive erms 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             

      
-A recurrence relation for the sequence {an} is an equation that expresses an in terms of one or more of the previous terms of the sequence, namely, a0, a1, . . . , an−1, for all integers n with n ≥ n0, where n0 is a nonnegative integer. A sequence is called a solution of a recurrencerelation if its terms satisfy the recurrence relation.

- 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?

- Example:-

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?

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.



C)Example sequences used in computer programming
Scanner k=new scanner(system.in);
int number;
number=k.nextInt();
while(number<=100){
if(number%2==0){
System.out.println(“even”);}
else{
System.out.println(“odd”);}
The statement above shows that when the modulus 2 of an input number is 0.The value has no remainder and is divisible by 2.In nutshell, it is an even number. On the other hand, when the modulus 2 of the number is 1.The number input is odd. Sequence is applied in a way that each number shows a pattern closely to sequence and it would be tiresome to calculate every single number to know if it’s odd or even. Sequence makes it easier to know the even and odd properties of a number with  a much more larger value by tracing out the pattern.


              EXAMPLE PROBLEM INVOLVING SEQUENCE

A sequence is a set of numbers such as 1, 2, 3, … or 96, 48, 24, … that follow some sort of formula. 
Example 1 :
Find five consecutive integers that sum up to 405.
Solution : 
Instead of implementing a guess and check method, suppose the five integers were x, x+1, x+2, x+3, and x+4 = 405. Their sum is 405, so we have
x + (x+1) + (x+2) + (x+3) + (x+4) = 405
5x + 10 = 405
x = 79
The five integers are 79, 80, 81, 82, and 83.

Example 2 : 
Find the sum of all the integers starting from 1 to 1000.
Solution :
The sequence of integers starting from 1 to 1000 is given by 
1, 2, 3, 4, …, 1000
The first term is 1 and the last term is 1000. The common difference is equal to 1. The formula that gives the sum of the first and terms of an arithmetic sequence knowing the first and last term of the sequence and the number of terms.
S1000 = 1000 (1 + 1000) / 2 = 500500




First Principle of Mathematical Induction.

Let P(n) be a predicate with domain of discourse (over) the natural numbers N = {0; 1; 2; …}. If 

          (1) P(0), and
          (2) P(n) → P(n + 1)

then 8nP(n).

Terminology: The hypothesis P(0) is called the basis step and the hypothesis,
P(n) → P(n + 1), is called the induction (or inductive) step.

The Principle of Mathematical Induction is an axiom of the system of natural
numbers that may be used to prove a quantified statement of the form 8nP(n), where
the universe of discourse is the set of natural numbers. The principle of induction has
a number of equivalent forms and is based on the last of the four Peano Axioms. The axiom of induction states that if S is a set of natural numbers such that (i) 0 ϵ S and (ii) if n ϵ S, then n + 1 ϵ S, then S = N. This is a fairly complicated statement: Not only is it an “if ..., then ..." statement, but its hypotheses also contains an “if ..., then ..." statement (if n ϵ S, then n + 1 ϵ S). When we apply the axiom to the truth set of a predicate P(n), we arrive at the first principle of mathematical induction stated above. More generally,
we may apply the principle of induction whenever the universe of discourse is a set of
integers of the form {k; k + 1; k + 2; …} where k is some fixed integer. In this case
it would be stated as follows:

Let P(n) be a predicate over {k; k + 1; k + 2; k + 3; …}, where k ϵ Z. If

(1) P(k), and
(2) P(n) → P(n + 1)

then 8nP(n).

In this context the “for all n", of course, means for all n ≥ k.

Why does the principle of induction work? This is essentially the domino effect.
Assume you have shown the premises. In other words you know P(0) is true and you
know that P(n) implies P(n + 1) for any integer n ≥ 0.

Since you know P(0) from the basis step and P(0) → P(1) from the inductive
step, we have P(1) (by modus ponens).
Since you now know P(1) and P(1) → P(2) from the inductive step, you have
P(2).
Since you now know P(2) and P(2) → P(3) from the inductive step, you have
P(3).
And so on ad infinitum (or ad nauseum).

The Second Principle of Mathematical Induction. 

Let k be an integer, and let P(n) be a predicate whose universe of discourse is the set of integers {k; k + 1; k + 2; …}. Suppose

1. P(k), and
2. P(j) for k ≤ j ≤ n implies P(n + 1).

Then 8nP(n).

The second principle of induction differs from the first only in the form of the
induction hypothesis. Here we assume not just P(n), but P(j) for all the integers j
between k and n (inclusive). We use this assumption to show P(n+1). This method
of induction is also called strong mathematical induction. It is used in computer
science in a variety of settings such as proving recursive formulas and estimating the
number of operations involved in so-called “divide-and-conquer" procedures.



examples of mathematical induction
1.  Version:1.0 StartHTML:0000000167 EndHTML:0000001580 StartFragment:0000000457 EndFragment:0000001564
Scanner k=new scanner(system.in);
int number;
number=k.nextInt();
while(number<=100){
if(number%2==0){
System.out.println(“even”);}
else{
System.out.println(“odd”);}

The statement above shows that when the modulus 2 of an input number is 0.The value has no remainder and is divisible by 2.In nutshell, it is an even number. On the other hand, when the modulus 2 of the number is 1.The number input is odd. Sequence is applied in a way that each number shows a pattern closely to sequence and it would be tiresome to calculate every single number to know if it’s odd or even. Sequence makes it easier to know the even and odd properties of a number with a much more larger value by tracing out the pattern.


2.  Express gcd(252, 198) = 18 as a linear combination of 252 and 198. Solution: To show that gcd(252, 198) = 18, the Euclidean algorithm uses these divisions:
252 = 1 · 198 + 54 198 = 3 · 54 + 36 54 = 1 · 36 + 18
36 = 2 · 18. Using the next-to-last division (the third division), we can express gcd(252, 198) = 18 as a
linear combination of 54 and 36. We find that 18 = 54 1 · 36. The second division tells us that 36 = 198 3 · 54.
Substituting this expression for 36 into the previous equation, we can express 18 as a linear combination of 54 and 198. We have
18 = 54 1 · 36 = 54 1 · (198 3 · 54) = 4 · 54 1 · 198. The first division tells us that 54 = 252 1 · 198.
Substituting this expression for 54 into the previous equation, we can express 18 as a linear combination of 252 and 198. We conclude that
18 = 4 · (252 1 · 198) 1 · 198 = 4 · 252 5 · 198, completing the solution.
We will use Theorem 6 to develop several useful results. One of our goals will be to prove the part of the fundamental theorem of arithmetic asserting that a positive integer has at most one prime factorization. We will show that if a positive integer has a factorization into primes, where the primes are written in nondecreasing order, then this factorization is unique.

slide show version:


  • Digg
  • Del.icio.us
  • StumbleUpon
  • Reddit
  • RSS

0 comments:

Post a Comment