Subsequence
정의
어떤 수열의 부분수열이란, 말 그대로 원 수열의 항의 일부분만을 딴 수열을 말한다. 유한 수열에서의 부분수열은 수학적인 큰 의미를 갖지 않기에 고려하지 않는다. 부분수열의 정확한 정의는 다음과 같다.
- 수열 [math]\displaystyle{ \left\{a_n\right\}_{n=1}^{\infty} }[/math]이 존재한다 가정하자. [math]\displaystyle{ n_1\lt n_2\lt n_3\lt \cdots }[/math]를 만족하는 자연수 \(n_k\)에 대해, [math]\displaystyle{ \left\{a_{n_k}\right\}_{k=1}^{\infty} }[/math]를 [math]\displaystyle{ \left\{a_n\right\} }[/math]의 부분수열이라 정의한다.
위 정의에서 주의깊게 봐야하는 것은 바로 [math]\displaystyle{ n_1\lt n_2\lt n_3\lt \cdots }[/math]라는 점이다. 즉,부분수열은 원 수열의 지표의 크기도 보존해야 한다. 예를들어, [math]\displaystyle{ \left\{a_n\right\}=1,\,2,\,3,\,\cdots }[/math]라는 수열이 있다고 가정하자. 그럼, [math]\displaystyle{ \left\{a_{n_k}\right\}=1,\,3,\,6,\,8,\,\cdots }[/math]은 부분수열이지만, [math]\displaystyle{ \left\{a_{n_k}\right\}=1,\,3,\,2,\,6,\,7,\,\cdots }[/math]은 부분수열이 아니다. 원 수열에서 2의 지표는 1의 지표와 3의 지표 사이인데, 새롭게 만든 수열에서의 2의 지표는 1의 지표와 3의 지표의 사이가 아니기 때문. 또한, 부분수열 역시 무한 수열이라는 점에 주의하자.
성질
- 모든 무한 수열은 단조 부분수열을 갖는다.
- 무한 수열 [math]\displaystyle{ \left\{a_n\right\} }[/math]이 있다 가정하자. 만약, [math]\displaystyle{ n\geq m }[/math]인 모든 자연수 \(n\)에 대해 [math]\displaystyle{ a_n\leq a_m }[/math]이면, \(m\)을 peak index라 부르기로 하자. 그럼, peak index가 무한히 많은 경우와 유한한 경우, 두 가지 경우가 존재한다.
- peak index가 유한한 경우: 가장 큰 peak index를 \(N\)이라 하자. 먼저, [math]\displaystyle{ n_1=N+1 }[/math]이라고 정의하자. 그리고 \(n_2\)를, \(n_1\)보다 크고 [math]\displaystyle{ a_{n_1}\lt a_{n_2} }[/math]를 만족하는 수로 정의한다. 이게 가능한 이유는, [math]\displaystyle{ n_1\gt N }[/math]이기 때문에 \(n_1\)는 peak index기 때문. 만약 [math]\displaystyle{ a_{n_1}\lt a_{n_2} }[/math]를 만족하는 \(n_2\)가 존재하지 않는다면 \(n_1\)은 peak index가 되어 \(N\)이 가장 큰 peak index라는 가정에 모순이다. 마찬가지 방법으로 [math]\displaystyle{ n_2\lt n_3 }[/math]이고 [math]\displaystyle{ a_{n_2}\lt a_{n_3} }[/math]인 \(n_3\)을 찾을 수 있다. 이를 반복하면 부분수열 [math]\displaystyle{ \left\{a_{n_k}\right\} }[/math]를 얻고, 이 수열은 강증가 한다.
- peak index가 무한한 경우: 자연수 \(k\)에 대해, \(n_k\)를 \(k\)번째 peak index라 정의하자. 그럼, [math]\displaystyle{ \left\{a_{n_k}\right\} }[/math]는 [math]\displaystyle{ \left\{a_n\right\} }[/math]의 부분수열이고, 강감소한다.
- 아래 정리와는 달리, 수열이 굳이 유계일 필요가 없다는 점에 주의하자.
- 무한 수열 [math]\displaystyle{ \left\{a_n\right\} }[/math]이 있다 가정하자. 만약, [math]\displaystyle{ n\geq m }[/math]인 모든 자연수 \(n\)에 대해 [math]\displaystyle{ a_n\leq a_m }[/math]이면, \(m\)을 peak index라 부르기로 하자. 그럼, peak index가 무한히 많은 경우와 유한한 경우, 두 가지 경우가 존재한다.
- 볼차노-바이어슈트라스 정리: 유계인 모든 수열은 수렴하는 부분수열을 갖는다.