|
이산수학 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. 개요
[math(n)]번째 항을 그 이전 항들의 관계식으로서 '귀납적( 歸 納 的, inductive)'으로 수열( 數 列)로써 정의( 定 義)하는 것. 수열을 자기 자신의 항들로 정의한다고 해서 '재귀적( 再 歸 的) 정의'라고도 한다. 이렇게 나타낸 식을 점화식이라고 한다.수열의 귀납적 정의에서는 한 수열의 여러 항이 동시에 등장하는데, 수열의 모든 항을 유일하게 결정하려면 처음 몇 개 항의 값을 밝혀주어야 한다. 예를 들어 수열 [math(a_n)]을 [math(a_n=a_{n-1}+2)]로 정의하고 싶다면, [math(a_1)]에 값을 줘야 모든 항의 값을 결정할 수 있다. 반면, [math(a_n=a_{n-1}+a_{n-2})]의 경우에는 [math(a_1)]과 [math(a_2)]에 값을 줘야 한다.
점화식으로부터 일반항을 구하는 것은 경우에 따라서 매우 어렵다. 쉽게 말해 미적분학의 상미분방정식 위치에 있다고 보면 되지만, 난이도는 심지어 미분방정식보다 더 어렵다. 이 문서에서는 구하기 쉬운 것들을 모아 그 과정을 설명한다.
2. 점화식을 일반항으로 바꾸기
2.1. 기본
2.1.1. 등차수열
등차수열의 점화식은 [math(a_{n+1}=a_n+d)] 꼴이다. [math(n)]에 [math(1)]부터 [math(n-1)]까지의 자연수를 차례로 대입하면[math( \begin{aligned}
\cancel{a_2}&=a_1+d \\
\cancel{a_3}&=\cancel{a_2}+d \\
&\quad \; \; \vdots \\
\cancel{a_{n-1}}&=\cancel{a_{n-2}}+d \\+\qquad a_n&=\cancel{a_{n-1}}+d \\
\hline
\therefore a_n&=a_1+(n-1)d
\end{aligned})]
등차중항을 이용하여 [math(2a_{n+1}=a_n+a_{n+2})]로 정의할 수도 있다.
2.1.2. 등비수열
등비수열의 점화식은 [math(a_{n+1}=ra_n)] 꼴이다. [math(n)]에 [math(1)]부터 [math(n-1)]까지의 자연수를 차례로 대입하면[math( \begin{aligned}
\cancel{a_2}&=ra_{1} \\
\cancel{a_3}&=r\cancel{a_{2}} \\
& \; \; \vdots \\
\cancel{a_{n-1}}&=r\cancel{a_{n-2}} \\\times\qquad a_n&=r\cancel{a_{n-1}} \\
\hline
\therefore a_n&=a_1r^{n-1}
\end{aligned})]
등비중항을 이용하여 [math({a_{n+1}}^2=a_na_{n+2})]로 정의할 수도 있다.
2.2. 심화
2.2.1. 형태 1
[math(pa_{n+2}+qa_{n+1}+ra_n=0)](단, [math(p+q+r=0)])에서 [math(a_n)]의 일반항을 도출해 보자.[math(\begin{aligned} pa_{n+2}-pa_{n+1}+ra_n-ra_{n+1}&=0 \\ p(a_{n+2}-a_{n+1})&=r(a_{n+1}-a_n) \\a_{n+2}-a_{n+1}&=\dfrac{r}{p}(a_{n+1}-a_n) \quad (\because q=-(p+r))\end{aligned})]
이때, [math(b_{n})]을 아래와 같이 놓으면,
[math(b_n=a_{n+1}-a_n \quad \to \quad b_n=\dfrac{r}{p}b_{n-1})]
이는 수열 [math(b_n)]에 대한 귀납적 정의이다. 앞서 알아본 대로 [math(b_n)]은 공비가 [math(r/p)]인 등비수열이 되며 일반항은
[math(b_n=b_1\left(\dfrac{r}{p}\right)^{n-1}=(a_2-a_1)\left(\dfrac{r}{p}\right)^{n-1})]
한편,
[math( \begin{aligned}
b_1&=\cancel{a_2}-a_1 \\
b_2&=\cancel{a_3}-\cancel{a_2} \\
&\quad \; \; \vdots \\
b_{n-2}&=\cancel{a_{n-1}}-\cancel{a_{n-2}}\\+\qquad b_{n-1}&=a_{n}-\cancel{a_{n-1}} \\
\hline
\displaystyle \sum_{k=1}^{n-1} b_k&=a_n-a_1 \quad \to \quad a_n=\sum_{k=1}^{n-1} b_k+a_1
\end{aligned})]
2.2.2. 형태 2
[math(a_{n+1}=pa_n+q)](단, [math(p \neq 0)], [math(p \neq 1)], [math(q \neq 0)])에서 [math(a_n)]의 일반항을 도출해 보자. 우선 적당한 [math(\alpha)]를 찾아,[math(a_{n+1}-α=p(a_n-α))]
의 꼴로 변환한다.
[math(b_n=a_n-\alpha)]
로 놓으면 [math(b_{n+1}=pb_n)]이므로 [math(b_n)]은 공비가 [math(p)]인 등비수열이다. 이에 따라 [math(a_n)]의 일반항은 다음과 같다.
[math(\begin{aligned} b_n &=b_1⋅p^{n-1}\\a_n-\alpha&=(a_1-\alpha)p^{n-1}\\\\\rightarrow a_n&=(a_1-\alpha)p^{n-1}+\alpha \end{aligned})]
일반적으로 [math(\alpha)]의 값은 다음과 같다.
[math(\alpha =\dfrac{q}{1-p} )]
2.2.3. 형태 3
[math(a_{n+1}={pa_n}/{(qa_n+r)})]의 일반항을 도출해 보자. 양변에 역수를 취하면[math(\dfrac{1}{a_{n+1}}=\dfrac{qa_n+r}{pa_n} \quad \to \quad \dfrac{1}{a_{n+1}}=\dfrac{q}{p}+\dfrac{r}{p}⋅\dfrac{1}{a_n})]
[math(b_n=1/{a_n})]로 놓으면
[math(b_{n+1}=\dfrac{q}{p}+\dfrac{r}{p}b_n)]
이 형태는 [math(q\neq 0)]이면 앞서 설명한 [math(a_{n+1}=pa_n+q)](단, [math(p \neq 0)], [math(p \neq 1)], [math(q \neq 0)])와 같으며, [math(q=0)]이면 [math(b_n)]은 공비가 [math(r/p)]인 등비수열이 된다.
3. 일반항을 구하기 어려운 경우
앞서 설명한 것들은 그래도 풀이가 매우 단순하고 정형화된 축에 속하며, 점화식이 교육과정에서는 삭제되었을지언정 고등학생들도 내신과 수능을 위해 공부하면 좋을 내용이다. 그러나 수열을 귀납적으로 정의하는 방법은 얼마든지 다양하며, 그 한없이 다양한 정의에 대하여 정형화된 일반항 도출 방법을 얼른 얻어낼 수가 없기 때문에, 비슷한 특성이 있는 미분방정식과 함께 종종 거론된다. 당장 수능 수열 문제를 보면 수열을 구간별로 정의해서 일반항 도출이 사실상 불가능하다.단적인 예로 피보나치 수열이 있다. 피보나치 수열은 두 개의 [math(1)]로 시작하여 앞 두 항을 더하여 새로운 항을 계속 얻어내는 수열이므로 점화식 도출이야 일도 아니다. 그러나 피보나치 수열의 일반항을 구하기란 쉽지 않은데, 상당히 일반항이 복잡하다. 자세한 사항은 피보나치 수열 문서를 참고하라.
그 외에, 완전 순열도 점화식까지는 어느 정도 머리를 쓰면 도출해낼 수 있지만 그를 바탕으로 일반항을 구하기란 역시 까다롭다. 완전 순열 참고.