CHAPTER 3:SEQUENCES

SEQUENCES

A discrete structure used to represent an ordered list.

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

solution:

We see from the recurrence relation a1 = a0 + 3 = 2 + 3 = 5. It then follows that a2 = 5 + 3 = 8 and a3 = 8 + 3 = 11

Types Of Sequence:

1) Arithmetic Progression

 A sequence of the form a, a+d, a+2d, .....a+nd,.... where the initial term, a and common    difference, d are real number.

Example of arithmetic progression:

Find the sum of the first 10 terms of the following series:
3, 8, 13, 18, 23, 28, 33, 38, 43,...

Solution: 

If you observe the above series, you noticed that there is a fixed difference of 5 between successive terms and is it so an Arithmetic Series. Therefore i=3, d=5, n=10

S= (n/2)[2i+(n-1)d] = 5[6+9(5)]=255
S10=255


2) Geometric Progression

A sequence of the form a, ar, ar²,….,arⁿ,…. where the initial term, a and common difference, d are real number.

Example of geometric progression:

Find the number of terms in geometric progression 6, 12, 24, 34,...1536

Solution: 

a1=6, a2=12, a3=24, an=1536
r=a2/a1=12/6=2
1536=(6)(2)^n-1
256=2^n-1
2^8=2^n-1
8=n-1
8+1=n
n=9
hence, 1536 in 9th term


Example sequences use in computer programming

Sequences of the form a1,a2,a3...are often used in computer  sciences.
These  finite sequences also called strings.The sring is also denoted by a1,a2,a3...The length of a string is the number of terms in this string.The empty string, denoted by λ, is the string that no terms.The length zero.

example:

                     The string abcd is the string of length four

Mathematical Induction

Principle of Mathematical Induction

to prove that P(n) is true for all positive integers n, where P(n) is a propositional function, we complete two steps:

• Basic Step : we verify that P(1) is true.
• Inductive Step: we show that the conditional statement P(k) → P(k + 1) is true for all positive integers k.

In the induction step, the assumption that P(n) holds is called the Induction Hypothesis.In more formal notation, this proof technique can be stated as 

      In the induction step, the assumption that P n holds is called the Induction Hypothesis

(IH). In more formal notation, this proof technique can be stated as

                                        (P(1) ˄  ∀k( P(k) → P(k +1))) → ∀n P(n)

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!

Example problem that use Mathematical Induction 

1)  Prove that   1 + 3 + 5 + … + (2n-1) = n² , for all n Î P.

Ans:

        Basic Step:

        Take n=1, LHS =2(1) –1 =1.           RHS=1²=1 , Therefore LHS=RHS

        Take n=2, LHS =1 + [2(2) –1] =4.  RHS=2²= 4 , Therefore LHS=RHS

       

         Inductive Step:

          p(n) ®  p(n+1) is true for all n Î P.

          p(n) : 1 + 3 + 5 + … + (2n-1) = n²  is true for all n Î P , then we have to prove

          p(n+1) : 1 + 3 + 5 + … + (2n-1) + [2(n+1)-1]= (n+1)²  is true for all n Î P .

      

          Proof:

           1 + 3 + 5 + … + (2n-1) + [2(n+1)-1] = 1 + 3 + 5 + … + (2n-1)  + [2n+2-1]

                                                                      = 1 + 3 + 5 + ...  + [ 2n +1 ]

                                                                      = n² + 2n  + 1

                                                                      = n²  + 2n  + 1

                                                                      = ( n + 1 )² = RHS   - proved.

 2) Prove that   1 + 2 + 3 + …. + n = [n(n+1)] / 2   , for all n Î P.

Ans:

        Basic Step:

        Take n=1, LHS= 1             RHS =[1(1+1)] / 2=1(2) /2 =1.   Therefore LHS=RHS

        Take n=2, LHS =1+2=3    RHS =[2(2+1)] / 2=[2(3)] /2 =3. Therefore LHS=RHS

     

         Inductive Step:

          p(n) ®  p(n+1)  is true for all n Î P , then

          p(n) : 1 + 2 + 3 +…. + n=[n(n+1)] / 2 is true for all n Î P. ,then we have to prove

          p(n+1) : 1 + 2 +3 +  … + n + (n+1)= [ (n+1){(n+1)+1 }] / 2  is true for all n Î P.

                                                                  = [ (n+1)(n+2) ] /2  is true for all n Î P.

        Proof:

          1 + 2 +3 +  … + n + (n+1)   = 1 + 2 +3 +  … + n + (n+1)

                                                      =­ 1 + 2 +3 +  … + n + (n + 1)

                                                      =  [n(n+1)] / 2 +  n + 1

                                                      =  [n(n+1)] / 2 + 2( n + 1)/2

                                                      =  [ n(n+1) + 2n + 2] / 2

                                                      =  [ n² +n + 2n + 2 ] / 2

                                                      =  [ n² + 3n + 2 ] / 2

                                                      =  [ (n+1)(n+2) ] /2  = RHS  -- proved.

                                        _n

Summation  Notation.:  å

                                       ⁱ⁼¹  

                    

                                                                                                 _n

Example:  .i) p(1) + p(2) + p(3) + …. + p(n)  can be written as  å  p(n).

                                                                               .                ⁿ⁼¹

                         _n

                    ii)  å  k = 1 + 2 + 3 + ….. + n

 .                 .     ^k=1

                        _n

                   iii) å 2k = 2 + 4 +  6 + ….. + 2n

                       ^k=1

                        _2n

                   iv) å 2k = 2 + 4 +  6 + ….. + 2n + 2(n+1) + ….. + 4n

                       ^k=1

                        _n-1

                    v) å 2k = 2 + 4 +  6 + ….. + 2(n-1)

                        ^k=1

                       _2n-1

                   vi) å 2k = 2n + 2(n+1) +….. …..+ 2(2n-1)

                       ^k=n

Example:        _n

1) Prove that  å (3k – 2 ) = (3n² –n ) /2  for all n Î P.

                     ^k=1 

Ans:

        Basic Step:

        Take k=1, n=1 LHS= 3(1)-2=1 :  RHS =[3(1²)-1]/2= 2 /2 =1. Therefore LHS=RHS

        Take k=1, n=2, LHS =[3(1)-2] + [3(2)-2]=1 + 4 =5  : RHS =[3(2²)-2]/2= 10/2=5 .                                    

                                 Therefore LHS=RHS

         Inductive Step:

        p(n) ®  p(n+1) is true for all n Î P.

                     _n

           p(n):   å (3k – 2 ) = (3n² –n ) /2  is true for all n Î P , then we have to prove

                    ^k=1

                                 _n+1

            p(n+1):   å (3k – 2 ) = [3(n+1)² –(n+1)] /2  for all n Î P.

                         ^k=1

           Proof:

                                _{n+1                        n}

            LHS =  å (3k – 2 ) =  å (3k – 2 )  + [3(n+1) –2]

                        ^{k=1                       k=1}

                                            =  ­_from p(n)_­ + [3n +1]

                                             =  (3n² –n ) /2     + [3n +1]

                                            =  (3n² –n ) /2     +  (2[3n +1])/2

                                             = {(3n² –n )   + 2[3n +1] } / 2

                                             = {(3n² –n  + 6n +2)} / 2

                                             =  [3n² + 5n +2 ] / 2

            RHS = [3(n+1)² –(n+1)] /2

                     = [3(n² +2n +1)–(n+1)] /2

                     = [3n²  + 6n +3 – n-1)] /2

                     =  [3n²  + 5n + 2)] /2                        

           Therefore LHS =  RHS  , proved.