구체수학 02.합.05.일반적인 방법들
상위 문서: {{ item.title }} -
02.SUMS.05.GENERAL METHODS
- 개요
- 방법 0: 답을 찾아본다
- 방법 1: 답을 추측하고 귀납법으로 증명한다
- 방법 2: 합을 어지럽힌다(섭동)
- 방법 3: 레퍼토리를 구축한다
- 방법 4: 합을 적분으로 대체한다
- 그 외의 방법들 (방법 6, 7)
- Links
이 문서는 [[CONCRETE-MATH]] 2장.합 - 5.일반적인 방법들을 공부한 노트입니다.
개요
이번 장의 목표는 한 가지 문제를 다양한 방법으로 풀어보며 배운 바를 정리하는 것이다.
그리고 그 문제는 0
부터 n
까지의 거듭제곱의 합이다.
위의 합 식은 python 코드로 생각하자면 다음과 같다.
def box(n):
sum = 0
for k in range(n+1):
sum += k**2
return sum
앞으로 쭉 참고하게 될 것이므로 0~12
사이의 n
과 n^2
, Box(n)
값을 다음과 같이 구하였다.
for n in range(12 + 1):
print(n, n**2, box(n))
- 결과를 다음과 같이 표로 정리해 보았다.
- 가장 오른쪽 열은 표를 정리하다가, 점화식 구조를 떠올리게 되어 추가한 것이다.
0 | 0 | 0 | 0 |
1 | 1 | 1 | = 1 + 0 |
2 | 4 | 5 | = 4 + 1 |
3 | 9 | 14 | = 9 + 5 |
4 | 16 | 30 | = 16 + 14 |
5 | 25 | 55 | = 25 + 30 |
6 | 36 | 91 | = 36 + 55 |
7 | 49 | 140 | = 49 + 91 |
8 | 64 | 204 | = 64 + 140 |
9 | 81 | 285 | = 81 + 204 |
10 | 100 | 385 | = 100 + 285 |
11 | 121 | 506 | = 121 + 385 |
12 | 144 | 650 | = 144 + 506 |
방법 0: 답을 찾아본다
Method 0: You could look it up.
이런 문제는 아마도 옛날 사람들이 다 풀어 놨을 것이다.
따라서 책이나 인터넷에서 답을 찾아본다.
- 교재에서는 CRC Standard Mathematical Tables에서 답을 찾았다고 한다.
- 나는 그냥 Wolfram Alpha에서 찾았다.
이 문제의 닫힌 형식은 다음과 같다. 고등학교에서 배웠던 익숙한 공식이다.
이 식을 python으로 옮기면 다음과 같을 것이다. 최적화되어 시간 복잡도가 선형 시간에서 상수 시간이 된 것 같다.
def Box(n):
return n * (n+1) * (2*n+1) / 6
한편, 식을 전개하면 이 되므로 다음과 같이 표현하는 것도 가능하다.
def Box(n):
return (2*(n**3) + 3*(n**2) + n) / 6
방법 1: 답을 추측하고 귀납법으로 증명한다
Method 1: Guess the answer, prove it by induction.
일단 위에서 얻은 답은 잊어버리자.
그리고 이 책을 읽고 있는 내가 열심히 생각해서 다음과 같은 답을 추측했다고 치자.
- 여기에서 중요한 것은 열심히 생각해서 떠올려 추측하는 것.
- 별 생각이 안 난다면 이 방법은 사용할 수 없다.
- 주관식 답을 찍는 것과 비슷하다. 그러나 그것보다는 조금 더 열심히 생각해야 한다.
이 답이 맞을 수도 있고, 틀릴 수도 있다.
그러니 수학적 귀납법으로 맞는지를 확인하면 된다.
수학적 귀납법으로 위의 추측을 검증하는 방법은 다음과 같다.
- 점화식을 준비한다.
- 점화식에 추측한 답을 대입해 모순이 없는지를 확인하면 된다.
그렇다면 주어진 문제를 통해 점화식을 만들어 보자.
- 재귀 함수를 만드는 과정과 똑같다.
- 재귀가 멈추는 조건인
n = 0
일 때부터 만들자.
- 이제 과 의 관계를 찾아주면 된다.
따라서 점화식은 다음과 같이 꾸밀 수 있을 것이다.
def box(n):
if n == 0:
return 0
return Box(n-1) + n**2
이제 점화식에 추측한 식을 넣어보고, 모순이 없는지를 확인하면 된다.
따라서 추측이 맞다고 볼 수 있다.
그리고 추측한 값은, 다음과 같이 변형해보면 방법 0에서 알아낸 식과 똑같다.
닫힌 형식을 구했다!
방법 2: 합을 어지럽힌다(섭동)
Method 2: Perturb the sum.
섭동법은 다음과 같은 방법이다.
- 합 을 다음 두 가지 방법으로 표현한다.
- 첫번째: 합의 마지막 항을 뽑아낸다.
- 예:
- 두번째: 합의 첫 항을 뽑아낸다.
- 예:
- 첫번째: 합의 마지막 항을 뽑아낸다.
- 첫번째 식과 두번째 식을 같다고 놓고, 적절히 조작해서 으로 표현한다.
섭동법을 적용해보자.
- 첫번째: 합의 마지막 항을 뽑아낸다.
- 두번째: 합의 첫 항을 뽑아낸다.
- 이제 둘을 조합한다.
0 = 0
모양이 나와 작업이 실패하였다.
그렇다면 조금 더 머리를 굴려서 모양이 남도록 조작을 할 궁리를 해야 한다.
방금 양 변이 의 모양이 되어 이 소거되었는데, 혹시 을 사용하면 양 변이 이 되고 가 남을 가능성은 없을까? 궁금하니 시도해 보자.
일단 다음과 같이 세제곱의 합을 정의하자.
그렇다면 다음과 같이 섭동법을 적용해 보자.
- 첫번째: 합의 마지막 항을 뽑아낸다.
- 두번째: 합의 첫 항을 뽑아낸다.
- 이제 둘을 조합한다.
닫힌 형식을 구했다!
방법 3: 레퍼토리를 구축한다
Build a repertoire.
일단 점화식은 다음과 같다.
레퍼토리법을 적용하려면 이를 일반화해야 한다.
그 다음, 일반식에 위의 점화식을 적용하여 답을 구하면 된다.
일반식 만들기
을 사용하는 점화식이므로 일반식은 다음과 같다.
그리고 닫힌 형태의 해가 다음과 같다고 하자.
- 는 초항이고, 항을 거듭해가며 더해도 딱 한 번만 더해지므로 이다.
- 는 항을 거듭해가며 더해가는 상수이므로 이다.
- 는 항을 거듭해가며
n
을 몇 번 더해가는지이므로 이다. - 는 항을 거듭해가며
n^2
을 몇 번 더해가는지… 인데 아직 모른다.- 만 구하면 되겠다.
참고: 1, 2, 3 항목이 잘 이해가지 않으면 [[c-m-02-Sums-02]]{02.합.02.합과 점화식} 문서를 다시 읽고 레퍼토리법을 복습하자.
는 쉽게 구했지만 는 아직 구하지 못했다.
이라면
변수가 셋, 식이 셋이니 이제 연립 방정식을 풀 수 있다.
를 써서 나머지 두 식을 심플하게 바꿔보자.
이제 을 구하기 위해 다음과 같이 식을 꾸밀 수 있다.
이제 D(n)
까지 다 구했다.
따라서 이 된다.
문제를 해결하기
일반식은 다음과 같다.
그리고 A(n)
, B(n)
, C(n)
, D(n)
는 다음과 같다.
그리고 일반화한 점화식은 다음과 같다.
마지막으로 해결해야 하는 점화식은 다음과 같았다!
일반 점화식과 비교해 보자.
모양이 심플해서 각 변수를 다음과 같이 설정하면, 이 된다는 것을 알 수 있다.
따라서 일반식을 적용하면 다음과 같이 된다.
닫힌 형식을 구했다!
방법 4: 합을 적분으로 대체한다
Replace sums by integrals.
- 이산수학이 아니라 미적분을 배운 사람들은 보다 이 더 익숙할 것이다.
- 교재의 목표는 독자가 에 익숙해지는 것이다.
- 두 방식의 아이디어는 아주 비슷하다.
이를 밑변의 길이가 1
이고 높이가 k^2
인 직사각형들의 넓이의 합으로 생각할 수 있다.
- 위의 그래프에서 곡선 아래쪽 면적의 넓이는 다음과 같다.
- 그런데 은 직사각형들의 넓이의 총합이므로, 곡선 아래쪽의 면적을 확인해야 할 필요가 있다.
즉, 다음과 같이 생각할 수 있다.
그리고 곡선 아래쪽의 넓이는 적분을 통해 구할 수 있다.
그렇다면 곡선 위쪽의 넓이만 구하면 된다.
곡선 위쪽의 넓이를 구하자
곡선 위쪽의 넓이 은 다음과 같이 표현할 수 있다.
이므로, 의 닫힌 형식은 다음과 같이 구할 수 있을 것이다.
결과를 정리해 보자.
이제 답을 구할 수 있을 것 같다.
닫힌 형식을 구했다!
곡선 위쪽의 넓이를 적분으로 구하자
문제는 풀었지만, 곡선 위쪽의 넓이를 적분으로 구하는 것도 연습할 가치가 있을 것 같다.
이것도 해보자.
곡선 위쪽의 넓이 을 다음과 같이 표현하는 것도 가능할 것이다.
윗 절에서 구한 과 똑같다.
책에 있는 학생 주석엔 “미적분에 중독된 사람들을 위한 방법이다.(This is for people addicted to calculus.)” 라고 되어 있었지만, 이 방법이 더 쉽고 간편한 것 같다.
그 외의 방법들 (방법 6, 7)
다음 방법들은 이번 챕터에서 배우지 않고 다음 챕터에서 배운다.
- 방법 6: 유한 미적분을 사용한다. (Method 6: Use finite calculus.)
- [[c-m-02-Sums-06]]{2.6 유한-무한 미적분}에서 배운다.
- 방법 7: 생성함수를 사용한다. (Method 7: Use generating functions.)
- [[c-m-05-Binomial-Coefficients-04]]{5.4 생성함수}에서 배운다.
Links
- [[CONCRETE-MATH]]