logo

점화식 📂보조정리

점화식

정의

수열 {an}\left\{ a_{n} \right\}이 주어졌다고 하자. 이때, ana_{n}을 an−1a_{n-1}, an−2a_{n-2}, ⋯\cdots, a1a_{1}의 함수로 나타낸 식을 점화식recurrence relation이라 한다.

설명

가령 자연수의 수열 {1,2,3,4,… }\left\{ 1, 2, 3, 4, \dots \right\}는 다음과 같은 점화식으로 표현할 수 있다.

an=an−1+1,a1=1 a_{n} = a_{n-1} + 1, \qquad a_{1} = 1

르장드르 다항식의 계수는 아래와 같은 점화식으로 나타난다. 따라서 a0a_{0}와 a1a_{1}만 알 고 있으면 모든 계수를 구할 수 있다.

an+2=−(ℓ+n+1)(ℓ−n)(n+1)(n+2)an a_{n+2} = -\dfrac{(\ell + n + 1)(\ell - n)}{(n+1)(n+2)} a_{n}