What do you show in the basis step and what do you show in the inductive step when you use (ordinary) mathematical induction to prove that a property involving an integer n is true for all integers greater than or equal to some initial integer?

• Basis step
• Show that p(n) is true
• Inductive step
• Show that any integer k greater or equal n0, if P(k) is true, then P(k+1) is true

Example

• Prove that for any natural number n,   0 + 1 + ... + n = n( n + 1 )/2
• Basis step:
• If n = 0, then LHS = 0, RHS = 0 * (0+1) = 0
• LHS (0) = RHS (0)

• Inductive step:
• LHS à n + 1 = 0 + 1 + … + n + (n + 1) = (0 + 1 + … + n) + (n + 1)
• n(n + 1)/2 + (n + 1) – using induction hypothesis
• (n + 1)(n + 2)/2 – factoring (n + 1)
• LHS = RHS for n + 1

What is the inductive hypothesis in a proof by (ordinary) mathematical induction?

• Inductive hypothesis is the assumption in inductive step that statement hold for some n.

• In order to perform the inductive step, one must assumes the inductive hypothesis and then uses this assumption to prove the statement for n + 1.

• Inductive hypothesis indicates in three ways:
• by explicit mention in the text
• by inserting acronym IH over an equal sign or a sign for an inequality
• by specify the inductive hypothesis as the reason for a step in a multi-line display

Use (ordinary) mathematical induction to construct proofs involving various kinds of statements such as formulas, divisibility properties and inequalities

Formulas:

Show that if n is a positive integer,

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

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, . . .

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 =  1(1+1)
                                                 2

INDUCTIVE STEP:

1 + 2+· · ·+k =  k(k+1)
                               2

Show that P(k + 1) is true,

1 + 2+· · ·+k + (k + 1) = (k+1)[(k+1)+1]
                                                    2
                                         
                                     = (k+1)(k+2)
                                                2

Add k + 1 to both sides of the equation in P(k),

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

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

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.

 1 + 2+· · ·+n =n(n + 1)/2 for all positive integers n have proven.

Divisibility properties

Proposition:

For any integer n≥1, 7ⁿ - 2ⁿ is divisible by 5.        

Proof :

1) Basis step:

The statement is true for n=1:                                                      

                                   7¹ – 2¹ = 7 - 2 = 5 is divisible by 5.

2) Inductive step:

Assume the statement is true for some k≥1                              

                                                            (inductive hypothesis) ;

P(k):                7^k - 2^k is divisible by 5.                                                 

            Then 7^k - 2^k = 5a   for some aÎZ .                                

 We need to show:

P(k+1):7^k+1 - 2^k+1 is divisible by 5.                                                                

             7^k+1 - 2^k+1 = 7·7^k - 2·2^k = 5·7^k + 2·7^k - 2·2^k

                                    = 5·7^k + 2·(7^k - 2^k)  =  5·7^k + 2·5a           

                                    = 5·(7^k + 2a) which is divisible by 5.                         

Show that it is true for k+1.                                                     

P(n) is true by induction.   

Inequalities

Theorem:

 For all integers n≥5,    n² < 2ⁿ.                         

Proof (by induction):

1) Basis step:

                        The statement is true for n=5:                             

                                                            5² =25 < 32 = 2⁵.

2)Inductive step:

Assume the statement is true for some k≥5 ;                        

P(k):                          k² < 2^k.                                              

We need to show:  

P(k+1):                 (k+1)² < 2^k+1.                                                              

             (k+1)² = k²+2k+1 < k² +2^k                

                                           < 2^k + 2^k                        

                                           = 2·2^k  = 2^k+1.

                                   

Show that it is true for k+1 .                                          

Thus, P(n) is true by induction.

Sequences – Definition of Sequence

• Sequence is a list of number of objects in a special order.

•Example:

•3, 5, 7, 9, …… is a sequence starting at 3 and increasing by 2 each time.

• A sequence is a (finite or infinite) set of numbers.

Example problem involving Sequence

Problem Number One:

If the first three terms of an arithmetic sequence are 2, 6 and 10, find the 40th term.

To solve the problem we use this formula for finding the nth term of an arithmetic sequence.

An = A + (n - 1) d

Where, An = is the nth term, in the case of our problem it is the 40th term

A = the first term of the sequence, in our problem it is 2.

n = number of terms, in our problem it is 40.

d = the interval of the terms, or the difference of the next term from the previous term,

to get d; d = 6 - 2 = 4.

Now, it is time to substitute the values to the formula for solving nth term where the 40th term is to be solved.

An = 2 + (40 - 1) 4

An = 2 + (39) 4

An = 2 + 156

An = 158.

The 40th term of the arithmetic sequence is 158.

Problem Number Two:

If the first term of an arithmetic sequence is -3 and the eighth term is 11, find d and write the first 10 terms of the sequence.

In this problem,

A = -3 n = 8 A8 = 11

If these values are substituted in the formula for An, we have

11 = -3 + (8 - 1) d

11 = -3 + 7d

14 = 7d

d = 2

The first ten terms are -3, -1, 1, 3, 5, 7, 9, 11, 13, 15

Arithmetic Progression

• A sequence in which the difference between any two successive terms is constant is called an arithmetic sequence @ arithmetic progression.
• The constant difference is called the common difference.
• Denoted by d.

Geometric Progression

• A sequence in which the ratio of every pair of successive terms is constant is called a geomatric sequence @ geometric progression
• The constant ratio is called the common ratio.
• Denoted by r.

List down the principle of mathematical induction.

To prove that P(n) is true for all positive integers n, where P(n) is a propositional function

11)   verify that P(1) is true.

22)   Show that the conditional statement P(k) → P(k + 1) is true for all positive 

integers k. The technique that we’ve used in the above example to determine if all the values are true or not, is called mathematical induction. 

Template proof by mathematical induction

1.express to be proved in the form “for all n ≥ b, P(n) for integer b


2.write “Basic Step”. 


Show that P(b) is true,take the correct value of b used is used.


3.write word “Inductive Step”


4.state clearly the inductive hypothesis in the “ assume that p(k) is true for an arbitrary


fixed integer k ≥ b ”


5.proved under assumption that inductive is true


Write P(k + 1) says


6.prove P(k + 1),make assumption P(k)
,

Make sure proof is valid for all integer k with k ≥ b

,
taking care proof work for small value of k, including k = b


7.conclusion of the induction step, saying “ this complete the inductive step”


8.namely that by mathematical induction P(n) is true for all integer n ≥ b

Use of Sequence in Computer Programming

Example:

First of all, we need to write a  program. 

The output should looks like this.

The output of  product is presented in sequence form.

Use of Sequence in Computer Programming

Example:

First of all, we need to write a  program.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

The output should looks like this.

The output of  product is presented in sequence form.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Function

FUNCTION

Definition of function

function is a relationship between two quantities, one of which is completely determined by the value of the other. A function f from a set X to a set Y is a relation between the elements of X (called the inputs) and the elements of Y (called the outputs) with the property that each input is related to one and only one output. We use the notation

f : X → Y

Concept of Boolean Functions

An expression that is form with binary variables. It can be represented as an algebraic expression or in truth table.

      

       TYPES  OF FUNCTION

1.      INJECTIVE

o   one-to-one

o   f  is called injective when the a = b

o   can express in quantifier

2.      SURJECTIVE

o   onto

o   f  is called surjective when there is a function from element A to element B

3.      BIJECTIVE

o   one-to-one correspondence

o   f  becomes function when no value in  the domain are signed to the same function value

o   no repeatation of domain

Inverse function and composition of function

Inverse function

Definition :-

¨      Let f  be one-to-one correspondence from the set A to the set B

¨      f  is the function that assign to be an element b belonging to B the unique element a in A such that f (a) = b

¨      Function of f is denoted by  f ˉ ¹ then  f ˉ ¹( b) = a when f (a) = b

       

        example

                           is the relation 

      

Composition function

¨       Let g be a function from the set A to the set B and let f be a function from the set B to the set C

¨      Function f and g, denoted for all a Î A by  f  ° g is defined by

      

           ( f  ° g )(a) = f( g(a) )

      

  example

                   f  ° g is defined  by   ( f  ° g )(a) = f  ( g(a)) = f (b) = 2

               ( f  ° g )(b) =  f ( g(b)) = f(c) =1 and ( f  ° g )(c) =  f ( g(c)) = f(a) =3

       Noted that:-

                f  ° g is not defined because the range of   f  is not a subset of domain of  g