점화식이란

recurrence relation · 漸化式

 

수학에서 점화식(漸化式) 또는 재귀식(再歸式, 영어: recurrence relation)이란 수열에서 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식이다.

 

어떤 수열의 각각의 항들의 관계를 나타낸 식이다. 점화식을 만족하는 수열을 점화식의 해라 하고, 이 해를 찾는 것을 점화식을 푼다고 말한다. 벡터, 행렬 등 다른 수학적 대상의 열을 묘사하는 점화식들도 생각할 수 있고, 마치 파스칼의 삼각형 항등식처럼 2개 이상의 변수를 갖는 수열에 대해서 생각할 수도 있다.

보통 점화식은 n번째의 항을 이전에 나온 항들로 나타내는 공식으로 나타나고, 이 점화식을 만족하는 수열은 초깃값에 따라 유일하게 결정된다. 이렇게 수열을 정의하는 것을 수열의 귀납적 정의(recursive definition)라 한다. 이 방법을 사용하면 일반항으로 수열을 나타내는 것보다 훨씬 다양한 수열을 나타낼 수 있다. 다만 모든 점화식이 n번째 항을 명확한 형태로 묘사하는 것은 아니고, 이런 경우에는 둘 이상의 해가 존재할 수 있으며 만족하는 수열을 모두 구하는 것이 목표가 될 수도 있다. 물론 명시적인 점화식의 경우에도 항을 찾을 수 있을 뿐이지 수열의 일반항을 정리해서 점화식을 푸는 건 쉬운 일이 아니다. 상수 계수 선형점화식을 비롯한 교과서의 몇몇 예외를 제외하면 점화식의 대수적인 일반항(closed form)은 웬만해선 존재하지 않는다고 보아도 좋다.

조합론에서 n에 따라 변화하는 어떤 대상의 개수를 구하고 싶지만 직접 일반항 계산이 어려울 때, 점화식을 먼저 만들어놓고 그 다음 점화식을 풀어 개수를 구하는 방식이 많이 쓰인다. 피보나치 수열이나 카탈란 수 등등의 예시가 있다. 물론 이런 쉬운 경우를 제외하면 현실적으로는 점화식만을 세우는 것도 컴퓨터 프로그램으로 nn번째 항을 계산할 수 있게 해 주기 때문에 위업이며(동적 계획법과 연관된다), 점근적 성장(asymptotic)을 알아내는 것이 최종목표로 간주된다.

 

 

<출처>

 

점화식 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

점화식 - 나무위키 (namu.wiki)