일반항

카탈란 수의 점화식

다음 글 이 글의 마지막 부분에서 카탈란 수는 (0, 0)에서 (n, n)까지 $y=x$ 그래프보다 위에 있는 점을 통과하지 않고, 격자점만을 지나며 이동하는 경우의 수라고 하였다. 카탈란 수는 다음 일반항으로 정의되는 수열이다. $C_n=\frac{1}{n+1}{}_{2n}\mathrm{C}_n$ 이 일반항이 어떻게 유도되었는지는 이전 글을 찾아보기 바란다. 이번에는 이 수열의 성질을 응용하는데 초점을 맞출 것이다. 카탈란 수는 다음 점화식을 가지고 있다. $C_{n+1}$$=\displaystyle\sum_{i+j=n}C_i C_j$$=C_0C_n+C_1C_{n-1}$$+\cdots$$+C_{n-1}C_1+C_nC_0$ 이는 카탈란 수가 경로의 수 문제와 대응됨을 생각하면 어렵지 않게 설명할 수 있..

동차점화식의 일반항

개요 수열에서 점화식이란 이전항을 이용해 다음 항을 알아내는 식이다. 예를 들어 어떤 수열 $a$에 대해 다음 식은 모두 점화식이다. $a_{n+1}=2a_n$ $a_{n+1}=a_n+4$ $a_{n+1}=3a_n+4$ $a_{n}=2a_{n-1}+3a_{n-2}$ 이 중 식 1, 2, 3 꼴의 점화식에서 일반항을 유도하는 방법은 이미 이 글에서 다루었다. 이번 글에서는 4번 형식의 점화식에서 일반항을 구하는 방법에 대해 알아보자. 동차점화식과 비동차점화식 점화식은 꼴에 따라 2가지 형태로 나눌 수 있다. 1번 식과 같은 꼴의 점화식을 "동차점화식"이라고 하고 2번 식과 같은 꼴의 점화식을 비동차점화식이라고 한다. $a_n=k_1 a_{n-1}+k_2 a_{n-2}+\cdots$$+k_m a_{n-m}$..

일반항과 점화식

< 등비수열과 등차수열 수열에는 일반항과 점화식이라는 개념이 있다. 이전 글을 보았으면 알겠지만 일반항은 수열의 항의 값을 항의 번호로 구하는 일반적인 식이며, 점화식은 구하고자 하는 항의 이전항들로 항의 값을 구하는 식이다. 그 글에서는 일반항과 점화식에 대해 자세히 알아본다. 등차수열과 등비수열의 일반항과 점화식 한 줄로 정리하자면 다음과 같다. ($a$: 일반항, $n$: 항의 번호, $d$: 공차, $r$: 공비) 일반항 점화식 등차수열 $S_n=a+(n-1)d$ $S_n=S_{n-1}+d$ 등비수열 $S_n=ar^{n-1}$ $S_n=rS_{n-1}$ 이미 이전 글에서 유도에 대해 설명했지만 이번에는 그냥 규칙을 찾는 것이 아니라 수학적으로 접근해보겠다. 점화식은 수열의 정의에서 당연하게 유도되..