점화식
정의
수열 $\left\{ a_{n} \right\}$이 주어졌다고 하자. 이때, $a_{n}$을 $a_{n-1}$, $a_{n-2}$, $\cdots$, $a_{1}$의 함수로 나타낸 식을 점화식recurrence relation이라 한다.
설명
가령 자연수의 수열 $\left\{ 1, 2, 3, 4, \dots \right\}$는 다음과 같은 점화식으로 표현할 수 있다.
$$ a_{n} = a_{n-1} + 1, \qquad a_{1} = 1 $$
르장드르 다항식의 계수는 아래와 같은 점화식으로 나타난다. 따라서 $a_{0}$와 $a_{1}$만 알 고 있으면 모든 계수를 구할 수 있다.
$$ a_{n+2} = -\dfrac{(\ell + n + 1)(\ell - n)}{(n+1)(n+2)} a_{n} $$