VocaloidEX: Chap 3: Mathematical Induction (I)

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 verify that P(1) is true @ show that an initial value is true for all Z⁺ of the propositional function.

Inductive : We show that the conditional statement∀k (P(k) → P(k+1)) is true for all Z⁺ of k.

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

P(1)^∀k(P(k) → P(k+1))) → ∀nP(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

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

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

PROBLEM SOLVING:

Example 1

Using Mathematical Induction, prove that

1+2+…+n = for all integers n≥1

Solution: We know that the property P(n) is the equation shown at the previous page. Hence, we need to prove it using BASIS and INDUCTION steps.

BASIS: Show that P(1) is true for LHS and RHS of the equation.

INDUCTIVE: we need to show that the equation can take any value k and it’s successive value (k+1) by

defining P(k) [the inductive hypothesis] and P(k+1) for k≥1. If P(k) is true then P(k+1) is true.

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

∴Since we have proven the BASIS and INDUCTIVE part, we have shown that the statement is valid for all positive integers n≥1.

PROVING A DIVISIBILITY PROPERTY:

Prove that for any integer n≥1, 7ⁿ-2ⁿ is divisible by 5 using mathematical induction.

Solution:

Let P(n) = 7ⁿ-2ⁿ is divisible by 5, for any integer n≥1.

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

P(1) = 7¹-2¹

= 7-2

= 5 (5 is divisible by 5)

Hence, the statement is true

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

(Assume that the inductive hypothesis is true for any particular but arbitrarily chosen integer k≥1.)

By the definition of division, we can define the statement 7ⁿ-2ⁿ is divisible by 5 as

(7ⁿ-2ⁿ )/5= a

7ⁿ-2ⁿ=5a, where ‘a’ is an integer.

Inductive Hypothesis

P(k): 7^k-2^k=5a

where ‘a’ is an integer.

P(k+1): 7^k+1-2⁺¹=7¹.7^k-2¹.2^k

= (5+2) .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+5(2a)

= 5(7^k+2a)

Since 7^k+2a is an integer as k and a is an integer P(k+1) is true.

∴ We have proven the BASIS and INDUCTIVE step and show that the statement is true.

PROVING A PROPERTY OF SEQUENCE

1)Show that if n is a positive integer

Solution:

Let P(n) be the proposition that the sum of the first n positive

integer,

is 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=