Recurrence Formula, Recurrence Relation   점화식, 점화 관계

(2020-01-23)

Generating Function, 생성 함수

1. 점화식 (Recurrence Formula) / 점화관계 (Recurrence Relation) 이란?수열의 각 항 간에 관계를 표현한 관계식
     - 수열의 n번째 항(일반항)을,                             ☞ 수열 용어 참조
     - 그 앞의 항들에 의해 규칙적(종속적)으로 표현한 관계식


2. 점화식 例등차 수열 : an = an-1 + d
  ㅇ 등비 수열 : an = a rn-1피보나치 수열 : an = an-1 + an-2계승(n!) 수열 : fn = n fn-1하노이의 탑 : T1 = 1, Tn = 2Tn-1 + 1
     - 일반항 : Tn = 2n -1


3. 점화식 특징

  ㅇ 점화식의 구성 형태
     - 등식 또는 관계식 형태를 갖춤 
        . 단, 문제 제시 때는, 초기값 또는 경계값이 반드시 필요

  ㅇ 점화식이 주는 정보
     - 점화식 자체는, 간접적이고 부분적인 정보 만 줌
     - 따라서, 일반항을 구할 필요 있음

  ㅇ 점화식을 풀기
     - 수열일반항(general term)을 구하는 것
        . 대부분, 수열의 초기값과 점화식을 이용하여 일반항(점화식 해)을 구할 수 있으나,
        . 그러나, 수열일반항을 구할 수 없거나, 적절한 점화식으로 표현 못하는 경우도 많음
     - 수열일반항을 구하는 일반화된 방법론은, => 생성 함수에 의함

  ㅇ 점화식의 해(解) : 일반항
     - 점화관계를 만족시키는 닫힌 형식수열 공식 (즉, 일반항)

  ㅇ 점화식의 응용
     - 주로, 수열재귀적 정의에 이용됨


4. 생성 함수 (Generating Function)수열 { an } (n ≥ 0) 에 대한 생성 함수는 다음과 같이 정의 함
       
[# f(x) = a_0 + a_1x + a_2x^2 + \dots = \displaystyle\sum_{k=0}^{\infty} a_kx^k #]
수열정보(수열의 일반항, 크기 등)를 담고있는 급수 형태의 함수


[수열] 1. 수열 2. 수열 용어 3. 수열 종류 4. 점화식 5. 피보나치 수열 6. 하노이의 탑

 
        최근수정     요약목록     참고문헌