이산수학 요점정리 (4/5)

Sequences, Recurrence relations, Induction - Overview

(시퀀스, 재귀관계식, 유도 - 개요)

---

목차

1. Sequences (시퀸스)

• Definitions (정의)
• Recurrence relation (재귀 관계)
• Arithmetic and geometric sequences (산술 및 기하학적 시퀸스)
• Problems (문제)

2. Inductive proof (귀납적 증명)

---

1. Sequences (시퀸스)

1.1 Definitions (정의)

• A set of elements written in a row.
• 시퀸스란 아래 예제처럼 요소들의 집합.

Examples:

1, 2, 3, 4, 5, 6, 7, …
2, 4, 6, 8, …
1, 3, 5, 7, 9, ….
1, 4, 9, 16, 25, ….
1, 2, 4, 8, 16, 32, ….

• Sequences are used to describe certain regular patterns.
• 시퀸스는 특정 규칙 패턴을 설명하는 데 사용됩니다.
• Term: each individual element in a sequence.
• 용법 : 시퀀스의 각 개별 요소.
• General notation: a1, a2, …. an, ….
• 일반적인 표기법은 a1, a2, ... an, ...
• Explicit (general) formula for a sequence: a rule that shows how the values of ak depend on k
• 시퀀스에 대한 명시적인 (일반) 식 : k에 의존적인 ak값을 어떻게 보여줄지를 나타내는 규칙

Examples:

Sequence	Explicit formula
1, 2, 3, 4, 5, 6, 7, …	ak = k, k = 1, 2, 3, …
2, 4, 6, 8, …	ak = 2k, k = 1, 2, 3, …
1, 3, 5, 7, 9, ….	ak = 2k -1, k = 1, 2, 3, … or ak = 2k + 1, k = 0, 1, 2, 3, …
1, 4, 9, 16, 25, ….	ak = k2, k = 1, 2, 3, …
1, 2, 4, 8, 16, 32, ….	ak = 2k, k = 0, 1, 2, 3, …
2, -2, 2, -2, ….	ak = 2 (-1) k, k = 0, 1, 2, 3,

 

1.2 Recurrence relation

• Recurrence relation is a formula that relates two or more (but finite number) successive terms in a sequence.
• Any recurrence relation is accompanied by initial condition 
• (sometimes called terminating condition) which specifies the first term of the sequence.

Examples:

a) 1, 3, 5, …. ak,…      ak = 2k -1, k =1,2,3,…
ak = 2k - 1
ak+1 = 2(k+1) - 1 = 2k + 2 - 1 = 2k -1 + 2 = ak +2
recurrence relation: ak+1 = ak +2, k = 1, 2, 3, …
initial condition: a1 = 1

b) 1, 2, 4, 8, 16, ….      ak = 2k , k = 0, 1, 2, 3, …
ak = 2k
ak+1 =2k+1 = 2 . 2k = 2ak
recurrence relation: ak+1 = 2ak, k = 0, 1, 2, 3, …
initial condition: a0 = 1

c) 1, 1/2, 1/3, 1/4, 1/ 5, ….      ak,… ak = 1/k, k =1,2,3,…
ak = 1/k
ak+1 = 1/(k+1) = k/(k(k+1)) = ak (k/(k+1))
recurrence relation: ak+1 = ak (k/(k+1)) , k = 1, 2, 3, …
initial condition: a1 = 1

 

1.3 Arithmetic and geometric sequences

• Look closely at the examples (a), (b), and (c) above.
• In (a) each term is equal to the previous one plus a fixed number
• i.e. each next term is obtained from the previous by adding a constant.
• Such sequence is called arithmetic sequence
• In (b) each next term is obtained from the previous one multiplied by a constant.
• Such sequence is called geometric sequence.
• In (c) ak+1 = ak (k/(k+1))
• Here we multiply by k/(k+1) - this changes with k, it is not a constant, so this is not a geometric sequence. It is not arithmetic either, because we do not add a constant in the recurrence relation

 

1.4 Problems

1.4.1 Find the 5 terms of the sequences given by explicit formula

Formula	Sequence
ak = k2, k = 1, 2, 3, …	1, 4, 9, 16, 25
ak = - 4k, k = 1, 2, 3, …	-4, -8, -12, -16, -20
ak = (k+1) / k, k = 1, 2, 3, …	2, 3/2, 4/3, 5/4, 6/5

1.4.2 Find an explicit formula that fits given initial terms

Initial terms	explicit formula
-2, 2, -2, 2, ….	ak = (-1)k * 2,     k =1, 2, 3, …
1/2, 1/3, 1/4, …	ak = 1/(k+1),      k = 1, 2, 3, …
1, 3, 9, 27, 81, ….	ak = 3(k-1),         k = 1, 2, 3, …

1.4.3 Given the recurrence relation and the first term of a sequence, write the next 4 terms: (주어진 반복 관계와 시퀀스의 첫번째 항을 보고, 그 다음 5번째 항까지 작성하시오.)

문제

a1 = 1, ak+1 = ak /k, k = 1, 2, 3, …

답

a1 = 1
a2 = 1/1 = 1
a3 = 1/2
a4 = (1/2)/3 = 1/6
a5 = (1/6)/4 = 1/24

문제

a1 = 1, ak+1 = k ak, k = 1, 2, 3, …

답

a1 = 1
a2 = 1 *1 = 1
a3 = 2 * 1 = 2
a4 = 3 * 2 = 6
a5 = 4 * 6 = 24

 

---

2. Inductive proof (귀납적 증명)

• Consider the sequence
• 1, 3, 5, 7, ….ak,…      ak = 2k-1, k = 1, 2, 3, …
• Prove that the sum of the first n terms is n2
• Notation Sk = the sum of the first k terms
• 첫 번째 n항의 합이 n2 임을 증명하십시오. 기호 Sk = 첫 번째 k 항의 합

2.1 Inductive proof:

• Inductive base: Proof for n = 1:

S1 = a1 = 1 = 12
Hence for n = 1, Sn = n2

• Inductive step: We shall show that

If Sk = k2 then Sk+1 = (k+1)2

• We use here the recurrence relation between the sums:

Sk+1 = Sk + ak+1

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

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

• By the principle of mathematical induction it follows that for any k, the sum is k2

Hence Sn = n2

2.2 Other problems:

• Find the sum of the natural numbers 1, 2, 3, 4, 5, 6,…, n
• Let Sn be the sum of 1, 2, 3, 4…, n

Sn = n(n+1)/2

• Find the sum of 2 + 4 + …..+ 2n

Sn = n(n+1)