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

(2023-06-13)

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. 하노이의 탑  


Copyrightⓒ written by 차재복 (Cha Jae Bok)       편집이력      기술용어해설후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"