계차수열

이산수학 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. 개요2. 상세3. 성질4. 계차수열로 원래 수열의 합 구하기5. 교육과정

1. 개요

階差數列 / difference sequence(progression)

수열의 인접한 두 항에 대하여, 뒤 항에서 앞 항을 뺀 값을 계차(階差 / difference)라고 한다. 계차수열은 원래 수열의 계차들을 항으로 하는 수열이다. 따라서 계차수열은 그 자체로는 성립하지 않고, 별도로 원래 수열의 존재를 전제해야만 성립하는 개념이다.

원래 수열의 계차수열의 계차수열을 원래 수열의 제2계 계차수열이라 하고, 제[math(m)]계 계차수열의 계차수열을 제[math((m+1))]계 계차수열이라 한다. 이런 맥락에서, 원래 수열의 계차수열을 제1계 계차수열이라 할 수 있다.

2. 상세

수열 [math(\{a_n\})]의 일반항 [math(a_n)]에 대해 계차 [math(b_n)]은 다음과 같이 정의되며

[math(
b_n = a_{n+1} -a_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_k&=\displaystyle\sum_{j=1}^{k-1}c_j+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}\Biggl(\sum_{j=1}^{k-1}c_j+b_1\Biggr)\!+a_1\;(k,\,n\geq 2)\end{aligned})]

제3계, 제4계 계차수열에 대해서도 같은 방식을 얼마든지 적용할 수 있다. 따라서 제[math(m)]계 계차수열의 일반항을 알기 어렵다면 제[math((m+1))]계 계차수열의 일반항을 구해 보는 것이 하나의 방법이다.

3. 성질

수열 [math(\{a_n\})]의 일반항이 [math(r)]차 다항식 (단, [math(r)]은 자연수이고 [math(c_r)]은 [math(r)]차항의 계수)

[math(\begin{aligned}
a_n = c_rn^r +c_{r-1}n^{r-1} +\cdots +c_1n +c_0
\end{aligned} )]}}}||

이면, [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 \} \\
&\quad -( 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((r-1))]차 이하의 다항식이 된다(정확하게는 원래 다항식의 차분이 된다). 마찬가지로 계차수열을 구하는 과정을 반복하면 결국에는 일반항이 일차식인 등차수열이 나오며, 그 다음에는 모든 항이 그 등차수열의 공차인, 다시 말해 수열의 일반항이 상수인 수열이 나온다. 한번 항의 값이 일정한 수열이 나왔으므로 이후에는 계속해서 모든 항이 0인 수열만 나온다. 다음 예시를 통해 직관적으로 확인해 보라.

수열	항	일반항	비고
원래 수열	[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)]

수열 [math(\{a_m\})]의 제[math(p)]계 계차수열을 [math(\{a_{p,m}\})]이라 하자. (단, [math(p)]는 자연수) 제1~4계 계차수열을 나타내보면

[math(\displaystyle \begin{aligned}
a_{1,m} &= a_{m+1} -a_m \\
a_{2,m} &= a_{1,m+1} -a_{1,m} \\
&= (a_{m+2}-a_{m+1}) - (a_{m+1}-a_m) \\
&= a_{m+2} -2a_{m+1} +a_m \\
a_{3,m} &= a_{2,m+1} -a_{2,m}\\
& = (a_{m+3} -2a_{m+2} +a_{m+1}) - (a_{m+2} -2a_{m+1} +a_m) \\
&= a_{m+3} -3a_{m+2} +3a_{m+1} -a_m \\
a_{4,m} &= a_{3,m+1} -a_{3,m} \\
&= (a_{m+4} -3a_{m+3} +3a_{m+2} -a_{m+1}) - (a_{m+3} -3a_{m+2} +3a_{m+1} -a_m) \\
&= a_{m+4} -4a_{m+3} +6a_{m+2} -4a_{m+1} +a_m
\end{aligned} )]}}}||

위와 같이 규칙이 보인다. 이 규칙에 착안해서 [math(\{a_{p,m}\})]을 [math(\{a_m\})]으로만 나타내면 다음과 같다.

[math(\displaystyle \begin{aligned}
a_{p,m} = \sum_{i=0}^p (-1)^{p-i} \binom pi a_{m+i}
\end{aligned} )]}}}||

수학적 귀납법을 사용하여 증명하자.

우선 [math(p=1)]일 때의 증명은 다음과 같다.
{{{#!wiki style="text-align:center"

[math(\displaystyle \begin{aligned}
a_{1,m} &= \sum_{i=0}^1 (-1)^{1-i} \binom1i a_{m+i} = (-1)^1 \binom10 a_m +(-1)^0 \binom11 a_{m+1} \\
&= a_{m+1} -a_m
\end{aligned} )]}}}

따라서 [math(p=1)]일 때 주어진 등식이 성립한다.

i. 이제 자연수 [math(l)]에 대하여 [math(p=l)]일 때 다음 식이 성립한다고 가정하자.
{{{#!wiki style="text-align:center"

[math(\displaystyle \begin{aligned}
a_{l,m} = \sum_{i=0}^l (-1)^{l-i} \binom li a_{m+i}
\end{aligned} )]}}}

그러면 [math(p=l+1)]일 때에 대한 증명은 아래와 같다.
{{{#!wiki style="text-align:center"

[math(\displaystyle \begin{aligned}
a_{l+1,m} &= a_{l,m+1}-a_{l,m} \\
&= \sum_{i=0}^l (-1)^{l-i} \binom li a_{m+1+i} -\sum_{i=0}^l (-1)^{l-i} \binom li a_{m+i} \\
&= \sum_{i=1}^{l+1} (-1)^{l-i+1} \binom l{i-1} a_{m+i} -\sum_{i=0}^l (-1)^{l-i} \binom li a_{m+i}
\end{aligned} )]}}}

여기서 [math(i=l+1)]인 경우와 [math(i=0)]인 경우는 분리하고, 나머지 경우들인 [math(\displaystyle\sum_{i=1}^l)]만 묶어보자.
{{{#!wiki style="text-align:center"

[math(\displaystyle \begin{aligned}
a_{l+1,m} &= \sum_{i=1}^{l+1} (-1)^{l-i+1} \binom l{i-1} a_{m+i} -\sum_{i=0}^l (-1)^{l-i} \binom li a_{m+i} \\
&= (-1)^0 \binom ll a_{m+l+1} +\sum_{i=1}^l \biggl[ (-1)^{l-i+1} \binom l{i-1} \!-(-1)^{l-i} \binom li \biggr] a_{m+i} -(-1)^l \binom l0 a_m \\
&= (-1)^0 \binom ll a_{m+l+1} +\sum_{i=1}^l \biggl[ (-1)^{l-i+1} \binom l{i-1} \!+(-1)^{l-i+1} \binom li \biggr] a_{m+i} -(-1)^l \binom l0 a_m \\
&= (-1)^0 \binom ll a_{m+l+1} +\sum_{i=1}^l (-1)^{l-i+1} \biggl[ \binom l{i-1} \!+\!\binom li \biggr] a_{m+i} -(-1)^l \binom l0 a_m
\end{aligned} )]}}}

한편, 조합의 성질에 의해 [math(\dbinom l{i-1} \!+\!\dbinom li \!= \!\dbinom{l+1}i)]이므로
{{{#!wiki style="text-align:center"

[math(\displaystyle \begin{aligned}
a_{l+1,m} &= (-1)^0 \binom ll a_{m+l+1} +\sum_{i=1}^l (-1)^{l-i+1} \biggl[ \binom l{i-1} \!+\!\binom li \biggr] a_{m+i} -(-1)^l \binom l0 a_m \\
&= (-1)^0 \binom ll a_{m+l+1} +\sum_{i=1}^l (-1)^{l-i+1} \binom{l+1}i a_{m+i} -(-1)^l \binom l0 a_m \\
&= (-1)^0 \binom{l+1}{l+1} a_{m+l+1} +\sum_{i=1}^l (-1)^{l+1-i} \binom{l+1}i a_{m+i} +(-1)^{l+1} \binom{l+1}0 a_m \\
&= \sum_{i=0}^{l+1} (-1)^{l+1-i} \binom{l+1}i a_{m+i}
\end{aligned} )]}}}

따라서 [math(p=l+1)]일 때도 주어진 등식이 성립한다.

(i)과 (ii)에 의해서 모든 자연수 [math(p)]에 대해 주어진 등식이 성립한다.
}}}||

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 개정 교육과정에서 삭제된 이래로 교육과정에 등장하지 않고 있다. 다만 수열의 귀납적 정의 문제 유형으로서는 계속 모습을 비추고 있다. 수열의 귀납적 정의 단원의 특성상 활용 가능성이 매우 무궁무진하기 때문. 조화수열, 계비수열 등과 함께 단골로 출제되기에 어지간해선 공부해놓는 학생들이 많다. 공부해놓으면 귀납적 정의 문제를 상당히 빠르게 풀어낼 수 있기 때문에 유용하다.