[이산수학] 수열, 문자열 ,점화관계를 푸는 법 ( 반복 )

수열이란?

일정한 규칙에 따라 한 줄로 배열된 수의 열. a₁, a₂, a₃,…, aₙ의 꼴로 배열한 것으로, ｛aₙ｝로 나타냄. 

 

문자열(String) 이란?

문자열의 유한 sequence입니다. 그런데 항상 순서있는 유한 sequence입니다. 이것을 우리가 string이라고 합니다. 집합 X를 공집합이 아닌 집합이라고 하고 집합 X 상에서의 String은 유한 수열입니다. 

 

집합 X가 {a, b, c}  로 이루어져 있을 때 a = bbaccc 이랗게 표현된 수열이라면 연속적으로 중복된 문자들은 지수승으로 인해서 표현을 할 수 있습니다. b^2 * a* c^3으로 표현할 수 있습니다. 

 

|a| 은 길이를 나타냅니다. |a|의 개수를 의미하며 bbaccc로 총 6개의 문자가 나열되어 있기 때문에 길이는 6이 됩니다. null 문자열은 (null string)이라고 하며 아무런 원소를 가지지 않는 string입니다. 기호로 lambda 사람인과 같은 기호를 씁니다. 

 

-X* 이렇게 집합에 별표가 있으면 null string을 포함해서 집합 x의 모든 string으로 구성된 것입니다. 

-X+  이것은 X * - NULL 즉 X의 모든 집합에서 null string을 제외한 것입니다. 

 

두 문자열 A와 B의 연접이라는 것이 존재합니다. 연접은 A가 나오고 그 다음에 B가 표현이 되면 A와 B의 연접이라고 합니다. 

 

 

점화관계

점화관계, 재귀적 관계

이것은 수열 a에서 n번째 요소를 그 이전의 선행 요소들의 특정한 몇몇 요소들에게 관련시키는 식을 말합니다. 즉 n번째 수열요소 값을 이전 수열요소들과 관련시키는 하나의 식으로 볼 수 있습니다. 

 

수열을 정확하게 표현하기 위해서 수열의 초기조건(initial condition)을 명시적으로 제공을 해야 합니다. 이것은 하나의 값이 제공될 수도 있고 여러개의 값이 적용이 될 수도 있습니다. 

 

EX) 

-Initial condition a0 = 1

-Recursion formula : an = 1 + 2an-1 for n>=1 

-First few terms are : 1, 3, 7, 15, 31, 63 ... 

 

점화 관계의 대표적인 예 : 피보나치의 수열

 

Initial conditions: f1 = 1, f2 = 1

Recursion formula : fn = fn-1 + fn-2 (for n>=3)

First few terms :  1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89. .... 이런 식으로 계산이 됩니다. 

 

수열의 점화관계를 푼다는 것은 일반 항 an에 대한 명시적 공식을 찾는 것을 말합니다.   

 

점화관계를 푸는 법

1) 반복

2) 상계수 선형 동차 점화 관계

 

반복법

ex1 ) an = an-1 +3으로 정의되었을 때 a1 = 2

이 점화관계를 풀기 위해서

 

an = an-1 + 3

     = an-2 + 3 + 3 (an-1 = an-2 + 3)

     = an-3 + 3 + 2*3 (an-2 = an-3 + 3)

     = .......

     = a1 + (n-1) * 3

    = 2 + 3(n-1)

 

ex2) an = 2an-1 for n>=1 , with initial condition a0 = 1

-solution : an = 2an-1 = 2(2an-2) = ... = 2^na0 = 2^n

 

ex3) Deer Population growth

-Deer Population dn , at time n

-Initial condition : d0 = 1000

-Increase from time n-1 to time n is 10% 

 

Therefore the recursive function is

dn -dn-1 = 0.1dn-1

dn = 1.1dn-1

 

Solution : dn = 1000(1.1)^n 

 

복리

P : initial amount

n = number of years

r = annual interest rate

An = amount of money at the end of n years

= An-1  r An-1

 

At the end of : 

0 year : A0 = p   = p(1+r)^0

1 year : A1 = A0 + rA0 = A0(1+r)  = p(1+r)^1

2 year : A2 = A1 + rA1 = A1(1+r)  = p(1+r)^2

...

An = P(a+r)^n

 

이것이 복리에 관한 점화관계입니다. 

 

수열의 합 곱 합은 시그마를 이용하고 곱은 파이를 이용하여 표현합니다.