이산수학 Discrete Mathematics |
||
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all" |
이론 | |
<colbgcolor=#3CC> 기본 대상 | 수학기초론( 수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률 | |
다루는 대상과 주요 토픽 | ||
수열 | 등차수열( 뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의( 점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수 | |
조합 | 경우의 수( 공식) · 순열( 완전순열 · 염주순열) · 치환 · 분할( 분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론 | |
그래프 | 수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기( 해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제 | |
기타 | P-NP 문제미해결 · 4색정리 · 이항정리( 파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오 ( 예상과 확인) · 불 논리 · 브라에스 역설 | |
관련 문서 | 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학 | }}}}}}}}} |
1. 개요
階 差 數 列 / Difference sequence(progression)계차수열은 수열의 인접한 두 항에 대하여, 뒤 항에서 앞 항을 뺀 값을 계차( 階 差 / difference)라고 하는데, 원래 수열의 계차들을 항으로 하는 수열이다. 따라서 계차수열은 그 자체로 성립하지 않고 별도로 원래 수열의 존재를 전제해야만 성립하는 개념이다.
원래 수열의 계차수열의 계차수열을 원래 수열의 제2계 계차수열이라 하고, 제[math(m)]계 계차수열의 계차수열을 제[math((m+1))]계 계차수열이라 한다.
2. 상세
수열 [math(\{a_n\})]에 대하여[math(b_n=a_{n+1}-a_n)]
이면 [math(b_n)]은 계차이고, [math(\{b_n\})]은 [math(\{a_n\})]의 계차수열이다. 여기에서 다음이 성립한다.
[math(\begin{aligned}\cancel{a_2}-a_1&=b_1\\\cancel{a_3}-\cancel{a_2}&=b_2\\& \;\;\vdots\\\cancel{a_{n-1}}-\cancel{a_{n-2}}&=b_{n-2}\\+\qquad a_n-\cancel{a_{n-1}}&=b_{n-1}\\ \hline a_n-a_1&=\displaystyle\sum_{k=1}^{n-1}b_k\end{aligned})]
[math(a_{n})]에 대하여 정리하면 다음과 같이 [math(n)]은 2 이상이어야 한다.
[math(a_n=\displaystyle\sum_{k=1}^{n-1}b_k+a_1\;(n\geq 2) \, \cdots \, (\ast))]
따라서 계차수열의 일반항을 안다면 원래 수열의 일반항 역시 알 수 있다. 계차수열의 일반항을 모른다면 제2계 계차수열 [math(\{c_n\})]의 일반항을 구해 보는 것이 하나의 방법이다. 이 경우 위와 마찬가지로 다음이 성립한다.
[math(\begin{aligned}b_n&=\displaystyle\sum_{k=1}^{n-1}c_k+b_1\;(k\geq 2)\end{aligned})]
이것을 식 [math((\ast))]에 대입하면,
[math(\begin{aligned} a_n&=\displaystyle\sum_{k=1}^{n-1}b_k+a_1\\&=\sum_{k=1}^{n-1}\left(\sum_{j=1}^{k-1}c_j+b_1\right)+a_1\;(k,\,n\geq 2)\end{aligned})]
제3계, 제4계 계차수열에 대해서도 같은 방식을 얼마든지 적용할 수 있다. 따라서 제[math(m)]계 계차수열의 일반항을 알기 어렵다면 제[math((m+1))]계 계차수열의 일반항을 구해 보는 것이 하나의 방법이다.
3. 성질
수열 [math(\{a_n\})]의 일반항이 [math(r)]차 다항식[math(a_n=c_rn^r+c_{r-1}n^{r-1}+\cdots+c_1n+c_0\;(r\neq 0))]
이면 [math(\{a_n\})]의 계차수열 [math(\{b_n\})]의 일반항은
[math(\begin{aligned}b_n&=a_{n+1}-a_n\\&=\{c_r(n+1)^r+c_{r-1}(n+1)^{r-1}+\cdots+c_1(n+1)+c_0\} \\ &\qquad \qquad -(c_rn^r+c_{r-1}n^{r-1}+\cdots+c_1n+c_0)\\&=(\cancel{c_rn^r}+c_rrn^{r-1}+\cdots)-(\cancel{c_rn^r}+\cdots)\end{aligned})] |
수열 | 항 | 일반항 | 비고 |
원래 수열 | [math(3,\,17,\,55,\,129,\,251,\,433,\,\cdots)] | [math(2n^3+1)] | 삼차식 |
계차수열 | [math(14,\,38,\,74,\,122,\,182,\,\cdots)] | [math(6n^2+6n+2)] | 이차식 |
제2계 계차수열 | [math(24,\,36,\,48,\,60,\,\cdots)] | [math(12n+12)] | 일차식( 등차수열) |
제3계 계차수열 | [math(12,\,12,\,12,\,\cdots)] | [math(12)] | 상수식(일반항이 공차) |
제4계 계차수열 | [math(0,\,0,\,\cdots)] | [math(0)] | 상수식(일반항이 0) |
제5계 계차수열 | [math(0,\,0,\,\cdots)] | [math(0)] | 상수식(일반항이 0) |
[math(\vdots)] | [math(\vdots)] | [math(\vdots)] | [math(\vdots)] |
4. 계차수열로 원래 수열의 합 구하기
이 문단은
어떤 수열 [math(\{a_n\})]과 그의 계차수열 [math(\{b_n\})]에 대하여, 앞서 밝혔듯이
[math(a_n=a_1+\displaystyle\sum_{k=1}^{n-1}b_k\;(n\geq 2))]
이므로 다음이 성립한다.
[math(\begin{matrix}&a_1&\!\!\!=\!\!\!&a_1\\&a_2&\!\!\!=\!\!\!&a_1&\!\!+\!\!&\!\!\!\!\!\!\!b_1\!\!\!\!\!\!\!\\&a_3&\!\!\!=\!\!\!&a_1&\!\!+\!\!&\!\!\!\!\!\!\!\!\!b_1\!\!\!\!\!\!\!\!\!&\!\!+\!\!&\!\!b_2\!\!\\\;&\vdots&&\!\!\vdots&&\vdots&&\vdots\\&a_{n-1}&\!\!\!=\!\!\!&a_1&\!\!+\!\!&\!\!\!\!\!\!\!\!\!b_1\!\!\!\!\!\!\!\!\!&\!\!+\!\!&\!\!b_2\!\!&\!\!+\!\!&\cdots&\!\!+\!\!&b_{n-2}\\\!\!+&a_n&\!\!\!=\!\!\!&a_1&\!\!+\!\!&\!\!\!\!\!\!\!\!\!b_1\!\!\!\!\!\!\!\!\!&\!\!+\!\!&\!\!b_2\!\!&\!\!+\!\!&\cdots&\!\!+\!\!&b_{n-2}&\!\!+\!\!&b_{n-1}\\\hline&\displaystyle\sum_{k=1}^na_k&\!\!\!=\!\!\!&na_1&\!\!+\!\!&\!\!(n-1)b_1\!\!&\!\!+\!\!&\!\!(n-2)b_2\!\!&\!\!+\!\!&\cdots&\!\!+\!\!&2b_{n-2}&\!\!+\!\!&b_{n-1}\end{matrix})] |
[math(\displaystyle\sum_{k=1}^na_k=na_1+\sum_{k=1}^{n-1}(n-k)b_k\;(n\geq 2))]
혹은 다음과 같이 해석할 수도 있다.
[math(\begin{matrix}&{\color{dodgerblue}a_1}&\!\!\!\!=&\!\!\!\!\!{\color{dodgerblue}a_1}\!\!\!\!&&\!\!\!{\color{red}b_1}\!\!&\!\!\!\!\!\!\!{\color{red}+}\!\!&\!\!\!\!{\color{red}b_2}&\!\!\!\!\!\!\!\!{\color{red}+}\!\!&{\color{red}\cdots}&\!\!{\color{red}+}\!\!&\!\!\!\!{\color{red}b_{n-2}}&\!\!\!{\color{red}+}\!\!&\!{\color{red}b_{n-1}}\\&{\color{dodgerblue}a_2}&\!\!\!\!=&\!\!\!\!\!{\color{dodgerblue}a_1}\!\!\!\!&\!\!{\color{dodgerblue}+}\!\!&\!\!\!{\color{dodgerblue}b_1}\!\!&&\!\!\!\!{\color{red}b_2}&\!\!\!\!\!\!\!\!{\color{red}+}\!\!&{\color{red}\cdots}&\!\!{\color{red}+}\!\!&\!\!\!\!{\color{red}b_{n-2}}&\!\!\!{\color{red}+}\!\!&\!{\color{red}b_{n-1}}\\&{\color{dodgerblue}a_3}&\!\!\!\!=&\!\!\!\!\!{\color{dodgerblue}a_1}\!\!\!\!&\!\!{\color{dodgerblue}+}\!\!&\!\!\!{\color{dodgerblue}b_1}\!\!&\!\!\!\!\!\!\!{\color{dodgerblue}+}\!\!&\!\!\!\!{\color{dodgerblue}b_2}&&{\color{red}\cdots}&\!\!{\color{red}+}\!\!&\!\!\!\!{\color{red}b_{n-2}}&\!\!\!{\color{red}+}\!\!&\!{\color{red}b_{n-1}}\\\;&{\color{dodgerblue}\vdots}&&\!{\color{dodgerblue}\vdots}&&\!\!\!{\color{dodgerblue}\vdots}&&\!\!\!\!\!\!{\color{dodgerblue}\vdots}&&\vdots&&\!\!{\color{red}\vdots}&&{\color{red}\vdots}\\&{\color{dodgerblue}a_{n-1}}&\!\!\!\!=&\!\!\!\!\!{\color{dodgerblue}a_1}\!\!\!\!&\!\!{\color{dodgerblue}+}\!\!&\!\!\!{\color{dodgerblue}b_1}\!\!&\!\!\!\!\!\!\!{\color{dodgerblue}+}\!\!&\!\!\!\!{\color{dodgerblue}b_2}&\!\!\!\!\!\!\!\!{\color{dodgerblue}+}\!\!&{\color{dodgerblue}\cdots}&\!\!{\color{dodgerblue}+}\!\!&\!\!\!\!{\color{dodgerblue}b_{n-2}}&&\!{\color{red}b_{n-1}}\\\!\!+\!\!\;&{\color{dodgerblue}a_n}&\!\!\!\!=&\!\!\!\!\!{\color{dodgerblue}a_1}\!\!\!\!&\!\!{\color{dodgerblue}+}\!\!&\!\!\!{\color{dodgerblue}b_1}\!\!&\!\!\!\!\!\!\!{\color{dodgerblue}+}\!\!&\!\!\!\!{\color{dodgerblue}b_2}&\!\!\!\!\!\!\!\!{\color{dodgerblue}+}\!\!&{\color{dodgerblue}\cdots}&\!\!{\color{dodgerblue}+}\!\!&\!\!\!\!{\color{dodgerblue}b_{n-2}}&\!\!\!{\color{dodgerblue}+}\!\!&\!{\color{dodgerblue}b_{n-1}}\\\hline&{\color{dodgerblue}\displaystyle\sum_{k=1}^na_k}&\!\!\!\!=&\!\!\!\!\!na_n\!\!\!\!&\!\!-\!\!&\!\!\!{\color{red}\{b_1}&\!\!\!\!\!{\color{red}+}&\!\!\!\!{\color{red}2b_2}&\!\!\!\!\!\!{\color{red}+}&{\color{red}\cdots}&{\color{red}+}&\!{\color{red}(n-2)b_{n-2}}&\!{\color{red}+}&\!{\color{red}(n-1)b_{n-1}\}}\end{matrix})] |
[math({\color{dodgerblue}\displaystyle\sum_{k=1}^na_k}=na_n-{\color{red}\displaystyle\sum_{k=1}^{n-1}kb_k}\;(n\geq 2))]
어떤 방식으로 공식을 유도하든 값은 같다.
[math(\begin{aligned}na_1+\displaystyle\sum_{k=1}^{n-1}(n-k)b_k&=na_1+n\sum_{k=1}^{n-1}b_k-\sum_{k=1}^{n-1}kb_k\\&=na_1+n(a_n-a_1)-\sum_{k=1}^{n-1}kb_k \\&=na_n-\displaystyle\sum_{k=1}^{n-1}kb_k\end{aligned})]
5. 교육과정
- 대한민국: 계차수열은 원래 2007 개정 교육과정의 수학Ⅰ에서 고2~고3 때 인문·자연 공통으로 학습하던 내용이었으나, 2009 개정 교육과정에서 삭제된 이래로 교육과정에 등장하지 않고 있다. 다만 수열의 귀납적 정의 문제 유형으로서는 계속 모습을 비추고 있다. 수열의 귀납적 정의 단원의 특성상 활용 가능성이 매우 무궁무진하기 때문. 조화수열, 계비수열 등과 함께 단골로 출제되기에 어지간해선 공부해놓는 학생들이 많다. 공부해놓으면 귀납적 정의 문제를 상당히 빠르게 풀어낼 수 있기 때문에 유용하다.