TASK 4

PRINCIPLE OF MATHEMATICAL INDUCTION:

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

Basis      : We show that P(1) is true to show that an initial value/lowest value of n is true for all Z+ of the propositional function.

Inductive : We show that the statement P(n+1) is true for all Z+ of n if P (n) is true.

Similarly, we can say that mathematical induction is a method for proving a property defined that the property for integer n is true for all values of n that are greater than or equal to some initial integer.

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

METHOD OF PROOF:

The proofs of the basis and inductive steps shown in the example illustrate 2 different ways to show an equation is true

-         -- Transforming LHS and RHS independently until they seem to be equal.

-         - Transforming one side of equation until it is seen to be the same as the other side of the equation.

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

The simplest and most common form of mathematical induction proves that a statement involving a natural number n holds for all values of n. The proof consists of two steps:

1.    The basis (base case): showing that the statement holds when n is equal to the lowest value that n is given in the question. Usually, n = 0 or n = 1.

2.    The inductive step: showing that, with respect to each n for which the statement holds, then the statement must also hold when n + 1 is substituted for n.

The assumption in the inductive step that the statement holds for some n is called the induction hypothesis (or inductive hypothesis). To perform the inductive step, one assumes the induction hypothesis and then uses this assumption to prove the statement for n + 1.

The choice between n = 0 and n = 1 in the base case is specific to the context of the proof: If 0 is considered a natural number, as is common in the fields of combinatory and mathematical logic, then n = 0. If, on the other hand, 1 is taken as the first natural number, then the base case is given by n = 1.

This method works by first proving the statement is true for a starting value, and then proving that the process used to go from one value to the next is valid. If these are both proven, then any value can be obtained by performing the process repeatedly. It may be helpful to think of the domino effect; if one is presented with a long row of dominoes standing on end, one can be sure that:

1.    The first domino will fall

2.    Whenever a domino falls, its next neighbor will also fall,

So it is concluded that all of the dominoes will fall, and that this fact is inevitable.

EXAMPLE

QUESTION 1.PROVING A FORMULA:
This time we will use arithmetic progression as our example.
a_n = a + (n – 1)d

where d = common difference, in this case we put d = 3
           a= first term of progression, in this case we put a = 5
           n = number of terms
           and n>0.

To form basis step, we prove that P (1) is true.
for a_n = a + (n – 1)d
a₁ = a + (1 – 1)d
a₁ = 5 + ( 0 ) 3 
    = 5 m
Now, for inductive step we need to prove that a_n+1 = a + (n+1 – 1)d.
And thus,
a₂ = a + (1 + 1 – 1) 3
    = 8
and
a₃ = a + (2 + 1 – 1) 3
     = 11
Since we proved that the basis step, P(1) and the inductive step P (n+1) is true we can conclude that the formula is true for n>0.

QUESTION 2.

PROVING A DIVISIBILITY PROPERTY:

Using mathematical induction, prove that for any value of n≥1, 9^{n _} 4ⁿ  is divisible by 5.

Solution:

Let P (n) = 9^{n _} 4ⁿ is divisible by 5, for value of n≥1.

Basis      : Proof that P (1) is valid for the statement

P (1) = 9^{n _} 4ⁿ 

    = 9 - 4

    = 5 (which is divisible by 5)

Hence, the statement is true.

Inductive: We proof that if P (n) is true, then P (n+1) is true for integer k≥1,

Inductive Hypothesis

P (n) = 9^{n _} 4ⁿ   / 5 = m

         = 9^{n _} 4ⁿ = 5 m
(In this case m is an integer)

P (n+1) = 9 ⁿ⁺¹ -   4 ⁿ⁺¹ 

                = 9. 9ⁿ - 4. 4ⁿ 

                = 5. 9ⁿ + 4. 9ⁿ  - 4.4ⁿ

                        = 5. 9ⁿ + 4 ( 9^{n _} 4ⁿ  )

                = 5. 9ⁿ + 4 (5 m)

                = 5. 9ⁿ + 5 (4 m)

                = 5 ( 9ⁿ + 4m)
So, since ( 9ⁿ + 4m) is an integer valid for n and m is an integer we can conclude that the statement is true by proving P (n) = 1 is true and P (n+1) is also true.

QUESTION 3.
PROVING INEQUALITIES Mathematical induction can be used to prove a variety of inequalities that hold for all positive integers greater than a particular positive integer.

Example: Prove 5n+5 <= n² for all positive integers n>=6.

                Proof = Let P(n) be the statement  5n+5 <=n²

                Basis step : n=6, Since 5n+5= 5(6)+5 <= 6² = n² , 35 <= 36

            Inductive step : Assume P(n) : 5n+5<= n², for some integer n>=6. 

Use the induction hypothesis to prove 5(n+1) +5 <=(n+1)².

                First rewrite 5(n+1)+5 so that it uses 5n+5 =

                5(n+1)+5=(5n+5)+5

   By induction hypothesis we know:

                (5n+5)+5 <=n²+5

   Now we need to show

                n²+5 <=(n+1)²= n² +2n + 1

    to see this we note that when n>=2,

                2n+1 >= 2(2)+1 = 5

    (and so this is also valid for n >=6)

Thus, when n>=6,

                5(n+1)+5 = (5n+5)+5

                (5n+5)+5 <= n²+5

                n²+5 <= n²+2n+1

                n² +2n +1 =(n+1)²

which shows 5(n+1) +5 <= (n+1)² . By the principal of mathematical induction it follows that 5n+5<=n² for all integers n >=6 .

Sequence and Mathematical Induction

Sequences

Definition :

A sequence is an ordered list of numbers or object.A sequence is a function from subse of the set of integers (usually either the set {0,1,2,.......} or the set {1,2,3....} ) to a set S.We use the notation an to denote the image of the integer n.We call an a term of sequence.

Type of sequence

• Arithmetric progression
• Geometric progression
• Fibonacci sequence

Arithmetric progression

1. An arithmetric progression or arithmeric sequence is simply a sequence of number with a common difference and this common difference has to be constant.
2. In general,you can write a arithmetric sequence like this: 

                                   a ,a+d ,a+2d,a+3d ,......a+nd

                                a is the first term and d is the common difference.

 

Consider  a_n =2n + 1. Please write down the sequence of {a_n} starting from n = 1.

Solution:

a₁ = 2 (1) + 1= 3

a₂ = 2 (2) + 1= 5

a₃ = 2 (3) + 1= 7

a₄ = 2 (4) + 1= 9

a₅ = 2 (5) + 1= 11

Geometric progression

1. A geometric progression / sequence is a sequence of number where each term in the sequence is found by multiplying the previous ter with a unchanging number called the common ratio (r)
2. In general, you can write an geometric sequence like this:

                                         a is the first term and r is the common ratio
                                                            * r cannot be 0

 Let the initial term a = 3 and the common ratio is 2. Write a sequence of geometric progression starting from n = 0.

{ arⁿ }= 3, 3(2)¹, 3(2)², 3(2)³, 3(2)⁴, ……

Therefore, the geometrical progression { arⁿ } is 3, 6, 12, 24, 48, ……

Recurrence Relation

Recurrence relation is a way of expressing each term in a sequence by referring to its previous terms before the specified term.

Given that a_n is dictated by a_n-1 times 2. So, when a₁ is 1. The values for the sequence is
a₂ = 2 (a₁ ) = 2 (1) = 2.

a₃ = 2 (a₂ ) = 2 (2) = 4

a₄ = 2 (a₃ ) = 2 (4) = 8.

 So, the solution to the sequence is 1, 2, 4, 8, 16......

Initial condition

An initial condition of a sequence with recurrence relation states the first term that would occur as the starting point of the sequence. Refer to Example 5, as we can see that the question stated if a₀ = 1. The expression  a₀ = 1 is the initial condition for the sequence { a_n }. This means that the sequence { a_n } starts with the term a₀, which is 1. Then followed by a₁, a₂, a₃, a₄, …… We can also say that a₀ is the starting term of the sequence { a_n }

Special number sequences

Special number sequences are derived from arithmetic sequence or geometrical sequence, or sometimes both. The terms in a special number sequence are arranged in such a way it can indirectly represents a mathematical theorem or a formula.

Squared Number Sequence

As the name of the sequence has told, a squared number sequence consists of the list of squared terms. Each term is represented by the form of n² for any real number

Solution:

{ a_n } = { n² }

{ n² } = 1², 2², 3², 4², 5² ……

therefore the solution to this  sequence will be:

{ n² } = 1, 4, 9, 16, 25 ……

This special number sequence had indirectly showed us the theorem of squared numbers and showed the squared numbers starting from n = 1 in a sequence.

 

Fibonacci sequence

The fibonacci sequence , f0,f1,f2......, is defined by the initial conditions f0 = 0 , f1=1 and recurrence relation.

                                                                   fn = fn-1 + fn-2

for n = 0,1,1,2,3,5,8,13,21,34...

MATHEMATICAL INDUCTION

Let’s say in a can of Mister Potato, there is an immeasurable amount of potato chips inside. So,

Q(n) : We want to be able to reach all the potato chips in the can.

To prove that ∀n Q (n) is true, we will need to eat the all chip in the can to prove that we can reach all the chips in the can. Since the potato chips are too many to count, we can’t possible finish counting before getting ourselves diabetes and high blood pressure. Therefore, we say that if we need to eat through n number of chips if we want to reach the n^th piece of chips in the can.

For example, we have to eat 99 pieces of potato chips to reach the 100^th piece of potato chips.

So, we propose

P (n): we must finish n piece of potato chips before we can reach the (n+1)^th piece of potato chips.
Since P(n) is true for all values of n, then we can also conclude that Q(n) is true, which states that we can reach any number of chips as long as we finishes the chips before the target.

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

The Method of Proof by Mathematical Induction

Let a statement P be true with any natural number, n.

To prove the statement by induction, there are 2 steps that we need to do:

1.     The basis step:

Initially we assume n = 1. We prove P (1) is true.

2.     The inductive step:

After the basis step, we prove that if P (n) is true, then P (n + 1) is true. While n represents any natural numbers.