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

(2020-06-19)

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. 하노이의 탑
  1.   기술공통
  2.   기초과학
        1. 과학
    1.   수학
          1. 수학
      1.   기초수학
        1.   수학 용어
        2.   비교 (같음/닮음/다름)
        3.   지수,로그
        4.   복소수
        5.   수열,급수
          1.   수열
            1.   1. 수열
                2. 수열 용어
                3. 수열 종류
                4. 점화식
                5. 피보나치 수열
                6. 하노이의 탑
          2.   급수
        6.   좌표계
        7.   기하학
      2.   집합,논리
      3.   해석학(미적분 등)
      4.   대수학
      5.   확률/통계
      6.   수치해법
    2.   물리
    3.   화학
    4.   지구,천체 과학
    5.   생명과학
    6.   뇌과학
  3.   진동/파동
  4.   방송/멀티미디어/정보이론
  5.   전기전자공학
  6.   통신/네트워킹
  7.   정보기술(IT)
  8.   공학일반(기계,재료등)
  9.   표준/계측/품질
  10.   기술경영

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