부분수열

어떤 수열의 부분수열(Subsequence)이란, 말 그대로 원 수열의 항의 일부분만을 딴 수열을 말한다. 유한 수열에서의 부분수열은 수학적인 큰 의미를 갖지 않기에 고려하지 않는다. 부분수열의 정확한 정의는 다음과 같다.

수열 [math]\displaystyle{ \left\{a_n\right\}_{n=1}^{\infty} }[/math]이 존재한다 가정하자. [math]\displaystyle{ n_1\lt n_2\lt n_3\lt \cdots }[/math]를 만족하는 자연수 [math]\displaystyle{ n_k }[/math]에 대해, [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]인 모든 자연수 [math]\displaystyle{ n }[/math]에 대해 [math]\displaystyle{ a_n\leq a_m }[/math]이면, [math]\displaystyle{ m }[/math]을 peak index라 부르기로 하자. 그럼, peak index가 무한히 많은 경우와 유한한 경우, 두 가지 경우가 존재한다.
    1. peak index가 유한한 경우: 가장 큰 peak index를 [math]\displaystyle{ N }[/math]이라 하자. 먼저, [math]\displaystyle{ n_1=N+1 }[/math]이라고 정의하자. 그리고 [math]\displaystyle{ n_2 }[/math]를, [math]\displaystyle{ n_1 }[/math]보다 크고 [math]\displaystyle{ a_{n_1}\lt a_{n_2} }[/math]를 만족하는 수로 정의한다. 이게 가능한 이유는, [math]\displaystyle{ n_1\gt N }[/math]이기 때문에 [math]\displaystyle{ n_1 }[/math]는 peak index기 때문. 만약 [math]\displaystyle{ a_{n_1}\lt a_{n_2} }[/math]를 만족하는 [math]\displaystyle{ n_2 }[/math]가 존재하지 않는다면 [math]\displaystyle{ n_1 }[/math]은 peak index가 되어 [math]\displaystyle{ N }[/math]이 가장 큰 peak index라는 가정에 모순이다. 마찬가지 방법으로 [math]\displaystyle{ n_2\lt n_3 }[/math]이고 [math]\displaystyle{ a_{n_2}\lt a_{n_3} }[/math]인 [math]\displaystyle{ n_3 }[/math]을 찾을 수 있다. 이를 반복하면 부분수열 [math]\displaystyle{ \left\{a_{n_k}\right\} }[/math]를 얻고, 이 수열은 강증가 한다.
    2. peak index가 무한한 경우: 자연수 [math]\displaystyle{ k }[/math]에 대해, [math]\displaystyle{ n_k }[/math]를 [math]\displaystyle{ k }[/math]번째 peak index라 정의하자. 그럼, [math]\displaystyle{ \left\{a_{n_k}\right\} }[/math]는 [math]\displaystyle{ \left\{a_n\right\} }[/math]의 부분수열이고, 강감소한다.
  • 아래 정리와는 달리, 수열이 굳이 유계일 필요가 없다는 점에 주의하자.
• 볼차노-바이어슈트라스 정리: 유계인 모든 수열은 수렴하는 부분수열을 갖는다.
  • 항목에서는 폐구간 수렴 정리를 이용하지만, 여기서는 다른 방법을 사용해 증명해보자. 먼저, 모든 수열은 단조 부분수열을 갖는다. 또한, 원 수열이 유계이므로, 부분수열도 유계이다. 단조이고 유계인 수열은 단조 수렴 정리에 의해 수렴한다. 즉, 저 부분수열은 수렴한다.
• 유계인 수열의 수렴하는 부분수열의 극한값들의 집합을 [math]\displaystyle{ S }[/math]라 하면, 볼차노-바이어슈트라스 정리에 의해 [math]\displaystyle{ S }[/math]는 공집합이 아니며, [math]\displaystyle{ S }[/math]의 상한과 하한을 각각 수열의 상극한(limit superior), 하극한(limit inferior)이라고 한다. 자세한 내용은 상극한과 하극한을 참조하라.
• 수렴하는 수열의 부분수열은 모두 같은 값으로 수렴한다. 즉, 어떤 수열의 부분수열이 수렴하지 않거나 두 수렴하는 부분수열의 극한값이 일치하지 않으면 수열이 발산함을 보일 수 있다.
  • 얽힌수열정리(intertwining sequence theorem): 수열 [math]\displaystyle{ (a_n) }[/math]이 수렴할 필요충분조건은 두 부분수열 [math]\displaystyle{ \{a_{2n}\} }[/math], [math]\displaystyle{ \{a_{2n+1}\} }[/math]이 같은 값으로 수렴하는 것이다. 일반적으로, 수열 [math]\displaystyle{ \{p_n\},\{q_n\},\dots, \{s_n\} }[/math]이 쌍마다 서로소이고 [math]\displaystyle{ \mathbb{N} }[/math]을 분할하는 순증가수열이며, [math]\displaystyle{ S,S_p,S_q,\dots, S_s }[/math]를 [math]\displaystyle{ \{a_n\} }[/math]의 부분수열 [math]\displaystyle{ \{a_n\}, \{a_{p_n}\},\{a_{q_n}\},\dots,\{a_{s_n}\} }[/math]의 모든 극한점의 집합이라 하면 [math]\displaystyle{ S=S_p\cup S_q \cup \cdots \cup S_s }[/math]이다. 따라서 [math]\displaystyle{ \{a_{p_n}\},\{a_{q_n}\},\dots,\{a_{s_n}\} }[/math]이 같은 값으로 수렴하면 [math]\displaystyle{ (a_n) }[/math]은 수렴한다.^{:40-41, Problem 2.4.3}