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.
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 InductionThe string abcd is the string of length four
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!
1)
Prove that 1 + 3 + 5 + … +
(2n-1) = n2 , for all n Î P.
Ans:
Basic Step:
Take n=1, LHS =2(1) –1 =1.
RHS=12=1 , Therefore LHS=RHS
Take n=2, LHS =1 + [2(2) –1] =4.
RHS=22= 4 , Therefore LHS=RHS
Inductive Step:
p(n) ®
p(n+1) is true for all n Î P.
p(n) : 1 + 3 + 5 + … + (2n-1) = n2 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)2 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 ]
= n2 + 2n
+ 1
= n2 + 2n + 1
= ( n + 1 )2 = 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
= [ n2 +n + 2n + 2 ] / 2
= [ n2 + 3n + 2 ] / 2
= [ (n+1)(n+2) ] /2 = RHS
-- proved.
n
Summation Notation.:
å
i=1
n
Example:
.i) p(1) + p(2) + p(3) + …. + p(n)
can be written as å p(n).
. n=1
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
) = (3n2 –n ) /2 for all n Î P.
k=1
Ans:
Basic Step:
Take k=1, n=1 LHS= 3(1)-2=1 : RHS
=[3(12)-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(22)-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
) = (3n2 –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)2 –(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]
= (3n2 –n ) /2 + [3n +1]
= (3n2 –n ) /2 +
(2[3n +1])/2
=
{(3n2 –n ) + 2[3n +1] } / 2
=
{(3n2 –n + 6n +2)} / 2
= [3n2 + 5n +2 ] / 2
RHS = [3(n+1)2 –(n+1)]
/2
= [3(n2
+2n +1)–(n+1)] /2
= [3n2 + 6n +3 – n-1)] /2
= [3n2 + 5n + 2)] /2
Therefore LHS = RHS ,
proved.