이 문서는 [[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 사이의 nn^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.

이런 문제는 아마도 옛날 사람들이 다 풀어 놨을 것이다.

따라서 책이나 인터넷에서 답을 찾아본다.

이 문제의 닫힌 형식은 다음과 같다. 고등학교에서 배웠던 익숙한 공식이다.

이 식을 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.

일단 점화식은 다음과 같다.

레퍼토리법을 적용하려면 이를 일반화해야 한다.

그 다음, 일반식에 위의 점화식을 적용하여 답을 구하면 된다.

일반식 만들기

을 사용하는 점화식이므로 일반식은 다음과 같다.

그리고 닫힌 형태의 해가 다음과 같다고 하자.

  1. 는 초항이고, 항을 거듭해가며 더해도 딱 한 번만 더해지므로 이다.
  2. 는 항을 거듭해가며 더해가는 상수이므로 이다.
  3. 는 항을 거듭해가며 n을 몇 번 더해가는지이므로 이다.
  4. 는 항을 거듭해가며 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인 직사각형들의 넓이의 합으로 생각할 수 있다.

integral

  •  
  • 위의 그래프에서 곡선 아래쪽 면적의 넓이는 다음과 같다.
    •  
  • 그런데 은 직사각형들의 넓이의 총합이므로, 곡선 아래쪽의 면적을 확인해야 할 필요가 있다.

즉, 다음과 같이 생각할 수 있다.

그리고 곡선 아래쪽의 넓이는 적분을 통해 구할 수 있다.

그렇다면 곡선 위쪽의 넓이만 구하면 된다.

곡선 위쪽의 넓이를 구하자

곡선 위쪽의 넓이 은 다음과 같이 표현할 수 있다.

이므로, 의 닫힌 형식은 다음과 같이 구할 수 있을 것이다.

결과를 정리해 보자.

이제 답을 구할 수 있을 것 같다.

닫힌 형식을 구했다!

곡선 위쪽의 넓이를 적분으로 구하자

문제는 풀었지만, 곡선 위쪽의 넓이를 적분으로 구하는 것도 연습할 가치가 있을 것 같다.

이것도 해보자.

곡선 위쪽의 넓이 을 다음과 같이 표현하는 것도 가능할 것이다.

윗 절에서 구한 과 똑같다.

책에 있는 학생 주석엔 "미적분에 중독된 사람들을 위한 방법이다.(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]]