2장. 수열_수학적 귀납법

실습_2. 수열_수학적 귀납법

수열의 정의

수열이란?

• 숫자의 나열
• 음수, 실수, 복소수 포함

정해져 있어 끝이 있는 수열을 유한수열 끝이 없이 이어지는 수열은 무한수열

---

• 표기법 a(n) n은 자연수

등차수열

• 각 항 사이에 일정한 수가 더해지는 수열
• 일반 항 = a + (n-1)d
• a 초항 d 공차

---

• 공차가 양수: 증가수열
• 공차가 음수: 감소수열

등비수열

• 각 항 사이에 일정한 수가 곱해지는 수열
• 일반 항 = a * r^(n-1)
• a 초항 r 공비

---

• r > 1: r이 1보다 크므로 곱해질때마다 수열이 증가

• r = 1: 1은 아무리 곱해도 그 값이 변하지 않으므로 제자리에 머문다. 등차수열에서 d=0일 때와 동일

• 0 < r < 1: r이 곱해짐에 따라 점차 수가 작아짐. a=32, r=½ 라면 an = 32, 16, 8, 4, 2, 1, ½, ¼, ⅛, … 같이 계속해서 줄어들어 0에 가깝게 된다

• -1 < r < 0: r이 음수이기 때문에 수열의 부호가 양수와 음수가 번갈아 나타난다. 예를 들어 a=32, r=-½ 라면 32, -16, 8, -4, 2, -1, … 같이 부호가 왔다갔다하면서 그 절대값은 계속 줄어들기 때문에 0에 가까워지는 모습을 한다. 등비의 부호가 음수인 경우에는 이렇게 값이 커졌다 줄어들었다를 반복하기 때문에 증가수열이나 감소수열이 되지 않는다.

• r = -1: 절대값은 같으면서 부호만 번갈아 나타나는 이른바 “진동수열”이 된다. 1, -1, 1, -1, … 처럼 2개의 값이 반복적으로 나타난다

• r < -1: 절대값이 계속 커지면서 진동하는 수열

계차수열

• 일정한 규칙을 가진 값들이 더해지는 수열

급수

• 수열의 각 항의 합

• 표기법 s(n), 시그마(Σ) 표기법

점화식

• 항들 간의 관계를 나타낸 식

• n번째 항이 바로 앞 항인 n-1번째 항에 의해서 정해질 수 있다

• 대표적인 점화식을 사용하는 수열은 피보나치 수열
• a1부터 차근차근 계산해서 올라가야 한다는 단점

수학적 귀납법

• 연쇄 반응을 이용한 등식의 증명법
• 모든 자연수 n에 대해 성립함을 보이는 증명법

---

1. n=1 일 때 주어진 등식이 성립함을 보인다
2. n=1 일 때 성립하면 n=2 일 때고 성립한다
3. 위를 반봅하며 범위확장
4. 모든 n에 대해서 등식 성립

분할정복

• 어려운 하나의 문제를 여러개의 쉬운 문제로 나누어 해결