Scribd
Upload
58 views15 pages

Mathematical Induction

The document discusses mathematical induction and provides examples of proving divisibility statements. It illustrates how to use induction to show that expressions like 7n - 1 and 2n > n2 are divisible by certain numbers or hold true for specific integers. The document also includes various mathematical inequalities and properties related to induction.

Uploaded by

Aze
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
58 views15 pages

Mathematical Induction

The document discusses mathematical induction and provides examples of proving divisibility statements. It illustrates how to use induction to show that expressions like 7n - 1 and 2n > n2 are divisible by certain numbers or hold true for specific integers. The document also includes various mathematical inequalities and properties related to induction.

Uploaded by

Aze
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 15

≤

https://commons.wikimedia.org/wiki/File:Wallpaper kartu domino.png

2
a1 (1 — rn)
,
—

a—
1(1 r1 )
a1 S1
1 —r

a—
1 (1 rk )
1—r

a1(1 —rk+1)

1—r
| {z }
. Σ
a1 1 —rk
=
.1 — r Σ
a1 1 — rk a1rk (1 — r)
1—r Σ
1 — r r k— r k+1
k

1 —Σ r
1—
rk+1 1
—r

a1(1 — rn)
1—r

6 6

Part 2

6
6

6 6

Part 2

6
integers n.
2.3.2. Proving Divisibility Statements
f We now prove some divisibility statements using mathematical induction.

Example 2.3.4. Use mathematical induction to prove that, for every positive integer n,
7n — 1 is divisible by 6.

Part 1
— ·
71 — 1 is divisible by 6.

Part 2
Assume: 7k — 1 is divisible by 6. To
show: 7k+1 — 1 is divisible by 6.
7k+1 — 1 = 7 · 7k — 1 = 6 · 7k 7k — 1 = 6 · 7k (7k — 1)
By definition of divisibility, 6 · 7k is divisible by 6. Also, by the hypothesis
(assumption), 7k — 1 is divisible by 6. Hence, their sum (which is equal to
7k+1 — 1) is also divisible by 6.
—

— — ·
—
03 — 0+3 is divisible by 3.

Part 2. We assume that k3 — k +3 is divisible by 3. By definition of divisibility, we


can write k3 — k +3 3a for some integer a.

—
—

Part 1

72(0) — 3 · 50 +2 is divisible by 12

Part 2
Assume: 72k — 3 · 5k +2 is divisible by 12
To show: 72(k+1) — 3 · 5(k+1) +2 is divisible by 12

72(k+1) — 3 · 5(k+1) +2
7272k — 3 · 5 · 5k +2
49 · 72k — 15 · 5k +2
72k 48 · 72k — 3 · 5k — 12 · 5k +2
. Σ
— · ·
. 2k Σ Σ
7 — 3 ·—5k 2 · 12 · 72k — 5k

12 4 · 72k — 5k , is divisible by 12 because 4 · 72k — 5k is an integer. Hence

— ·

Part 1

Part 2

Example 2.3.6. Use mathematical induction to prove that 2n > 2n for every integer n ≤
3.
Part 1

Part 2

Alternative 1. We double both sides.


Since 2k > 2k, by the multiplication property of inequality, we have 2 · 2k >
2 · 2k.

Alternative 2. We increase both sides by 2.

. Σ

Therefore, by the Principle of Math Induction, 2n > 2n for every integer


n ≤ 3. 2
Part 1

Part 2

. Σ
3 3k < 3 [(k 2)!] .

. Σ
3 3k < 3 [(k 2)!] < (k 3) [(k 2)!] , since k > 0,

3k+1 < (k 3)!.

3
Part 1

Part 2

3n n
(1) (3i — 1)
2
1 1 1 1 n

X
2 · 3i—1 3n —1

k+1 k

n [2a1 (n — 1)d]
(n — 1)d] =

(6) 1 (1!) 2 (2!) ·· · n (n!) (n 1)! — 1


k+1 k
· · —
i=1 i=1

7n — 4n is divisible by 3
Hint: 7k+1 — 4k+1 = 7 · 7k — 4 · 4k (3 4)7k — 4 · 4k = 3 · 7k (7k — 4k)
xn — yn is divisible by x — y for any positive integer n
Hint: xk+1 — yk+1 x · xk — y · xk y · xk — y · yk (x — y)xk y(xk — yk)

y 2 yk — y 2 yk
— —
If 0 < a < 1, then 0 < an < 1 for any positive integer n

2n > n2 for every integer n > 4

For k> 4, (k — 1)2 > 2


2n < n! for every integer n > 3

You might also like