TASK 4

#Sequences

Definition of sequence

• Ordered list of objects (or events)
• Contains elements or terms

Example : {M,a,r,y} is a sequence of letter ‘M’ first and ‘Y’ last.

• Sequence can be finite or infinite

Types of sequence

1. Arithmetic sequence

• sequence of number with common difference, and the difference must be constant
• example : 2,4,6,8....
• common difference is 2
• so you have arithmetic sequence

2. geometric sequence

• sequence of number where each form in sequence is found by multiplying previous term with unchanging number called common ratio.
• Example: 2,6,18,54.
  
  
  With common ratio 3
  
  
  
  
  Example sequences use in computer programming.
  
  

  • Sequence of the form a_{1 ,} a_{2 ,….. ,}a_n are often use in computer science.
  • This finite sequence are also called strings .
  • The length of a string is the number of terms in the string.
  • The empty string,is the string that has no terms(has length zero).

  
  
  

  Example:

  The string abcd is a string of length four.

  
  
  #Mathematical Induction
  
  
  The Principle of Mathematical Induction
  
  
  • 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, ∀nP(n)
  
  
  • 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, ∀nP(n).
  
  
  In the induction step, the assumption that Pnholds is called the Induction Hypothesis
  (IH). In more formal notation, this proof technique can be stated as
  [P(0)∧∀(P(k)            P(k+1))]                 ∀P(n)
  
  
  Example 1 :
  
  
  E(n) is 1+2+3+4+5+...+ n = (1+n)n/2
  
  
  First step:
  We'll show the truth of E(1). We have to show: 1 = (1+1).1/2
  We see immediately that both sides are equal. So, E(1) is true.
  V contains '1'.
  
  
  Second step:
  Assume for a moment that E (k) is true.
  Given : 1+2+3+4+5+...+k = (1+k)k/2
  We'll show the truth of E(k+1).
  Proof:
  
  
  left side
  = (1+2+3+4+5+...+k)+ (k+1)
  = (1+k).k/2 + (k+1)
  = (k+1)(k+2)/2
  
  
  right side
  = (1+(k+1)).(k+1)/2
  = (2+k)(k+1)/2
  We see that the left side is equal to the right side.
  Thus if E (k) is true then E(k+1) is true.
  If k is in V, then k+1 is in V.
  But 1 is in V, so 2 is in V, so 3 is in V, etc..
  So, V = { 1,2,3,4,....}
  
  
  Conclusion: The property is proved for all natural numbers starting from 1
  
  
  Explain the method of Proof by mathematical Induction
  
  
  In general, mathematical induction can be used to prove statements that assert that P(n) is
  true for all positive integers n, where P(n) is a propositional function. A proof by mathematical induction has two parts, a basis step, where we show that P(1) is true, and an inductive step, where we show that for all positive integers k, if P(k) is true, then P(k+ 1) is true.
  
  
  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:
  
  
  BASIS 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.
  
  
  To complete the inductive step of a proof using the principle of mathematical induction, we assume that P(k)is true for an arbitrary positive integer k and show that under this assumption, P(k+ 1) must also be true. The assumption that P(k)is true is called the inductive hypothesis. Once we complete both steps in a proof by mathematical induction, we have shown that P(n) is true for all positive integers, that is, we have shown that ∀nP (n) is true where the quantification is over the set of positive integers. In the inductive step, we show that ∀k(P(k) ¡ú P(k+ 1)) is true, where again, the domain is the set of positive integers
  
  
  
  
  Rules of Mathematical Induction
  
  
  Show that the result holds for n = 1
  Step 1:Show that the result is true for n= 1.
  Step 2:Assume the validity of the result for ‘n’ equal to some arbitrary but fixed natural number, say ‘k’.
  Step 3:Show that the result is also true for n= k + 1.
  Step 4:Conclude that the result holds for all natural numbers.
  
  
  
  
  Example 1:
  
  
  Show that if n is a positive integer, then
  
  
  1 + 2+…..+n =
  
  
  Solution: Let P(n) be the proposition that the sum of the first n positive integers, 1+2+…+n=n(n+1)/2. We must do two things to prove that P(n) is true for n = 1, 2, 3, . . .
  Namely, we must show that P(1) is true and that the conditional statement P(k) implies P(k + 1) is true for k = 1, 2, 3,…..
  
  
  BASIS STEP: P(1) is true, because 1 =
  (The left-hand side of this equation is 1 because 1 is the sum of the first positive integer. The right-hand side is found by substituting 1 for n in n(n + 1)/2.)
  
  
  INDUCTIVE STEP: For the inductive hypothesis we assume that P(k) holds for an arbitrary positive integer k. That is, we assume that
  1 + 2+· · ·+k =
  Under this assumption, it must be shown that P(k + 1) is true, namely, that
  1 + 2+· · ·+k + (k + 1) ==
  is also true. When we add k + 1 to both sides of the equation in P(k), we obtain
  
  
  1+2+....+k+(k + 1)=+(k+1)
  =
  =
  
  
  This last equation shows that P(k + 1) is true under the assumption that P(k) is true. This completes the inductive step.
  We have completed the basis step and the inductive step, so by mathematical induction we know that P(n) is true for all positive integers n. That is, we have proven that 1 + 2+· · ·+n =n(n + 1)/2 for all positive integers n.
  
  
  
  
  Example 2:
  
  
  Prove by the principle of mathematical induction method
  4 + 8 + 12 + … + 4n = 2n(n + 1).
  Solution:
  P(n)= 4 + 8 + 12 + … + 4n = 2n(n + 1)
  Put n = 1
  P(1) is true
  Assume that statement be true for n = k
  Assume P(k) true.
  Assume 4 + 8 + 12 + … + 4k = 2k(k + 1) be true
  To prove P(k + 1) is true.
  4 + 8 + 12 + … + 4(k+1) = 2(k+1)(k+1 + 1)= 2(k+1)(k+2)
  P(k + 1) is true.
  If P(k) true, then P(k + 1) is also true.
  P(n) is true for all n ∈ N.