부분 수열 (subsequence)이란?

$(x_n)$이 수열이고

$(n_k)$가 강한 증가 수열이고 자연수 수열이면

(즉 $n_1<n_2<\cdots<n_k<\cdots$이고 $n_1,~n_2,~\cdots\in$ )

$(x_{n_k})$는 수열 $(x_n)$의 부분수열이라고 합니다.

간단하게 수열 $(x_n):=(x_1,~x_2,~x_3,~\cdots,~x_n,~\cdots)$의 일부를 뽑았다고 생각하시면 됩니다.

예를들어 아래 그림과 같이 $(x_1,~x_3,~x_5,~\cdots)$는 수열 $(x_n)$의 부분수열이 됩니다.