4회 실험 · 두 개의 합 공식#
이 실험
짝 서술 |
|
확인하는 것 |
두 개의 합 공식은 실제 값과 맞으며, 답을 모르는 상태에서 그 공식을 얻어 내는 방법은 망원합이다 |
서술 파트 4절에서 (4.6)과 (4.9)를 각각 두 가지 방법으로 유도하였다. 귀납법과 망원합이다. 두 방법은 같은 결과를 주지만 성격이 다르다. 귀납법은 공식을 먼저 적어 놓아야 시작할 수 있고, 망원합은 항등식 하나에서 공식을 계산해 낸다.
이 실험에서는 먼저 두 공식이 실제 값과 맞는지 정수 연산으로 확인한다. 그다음 귀납 단계가 결국 항등식 하나로 줄어든다는 것을 기호 계산으로 본다. 기저 단계를 빼면 무엇이 무너지는지는 서술 파트 2절의 오해 상자에 나온 명제로 직접 확인한다.
이어서 망원합의 항을 하나씩 늘어놓아 상쇄가 어디서 일어나는지 보고, (4.11)에서 \(\sum k^2\)을 미지수로 두고 풀어 본다. 마지막으로 sympy의 summation을 셋째 방법으로 놓고, 세 방법이 무엇을 할 수 있고 무엇을 할 수 없는지 정리한다.
서술 파트의 내용 |
여기서 확인하는 방법 |
|---|---|
항을 하나씩 더한 정수 값과 공식의 값을 |
|
정리 9의 귀납 단계 |
귀납 단계가 항등식 하나로 줄어드는 것을 기호 계산으로 확인한다 |
기저 단계를 생략하는 오해 |
\(n^2+n\)이 홀수라는 명제로 귀납 단계만 성립하는 경우를 만들어 본다 |
\((k+1)^3-k^3\)의 항을 늘어놓아 가운데가 지워지는 것을 본다 |
|
4절 방법 2 |
(4.11)에서 \(\sum k^2\)을 미지수로 두고 푼다 |
두 방법의 차이 표 |
|
0. 준비#
합을 구하는 함수는 전부 이 회차 안에서 직접 만든다. 색은 마지막 절의 그림에서 쓰는 세 가지만 정해 둔다.
1. 공식과 직접 더한 값을 맞춰 본다#
(4.6)과 (4.9)의 왼쪽은 항을 하나씩 더한 값이고 오른쪽은 \(n\)을 공식에 넣은 값이다. 두 값이 같은지 본다.
항이 모두 정수이고 공식의 값도 언제나 정수이므로 정수 나눗셈 //를 쓴다. 소수점을 쓰지 않으므로 반올림 오차가 없고, 일치 여부를 ==로 판정해도 된다.
# Compare term-by-term addition with the closed formulas (4.6) and (4.9)
def direct_sum(n, p):
total = 0
for k in range(1, n + 1):
total = total + k ** p
return total
def formula_k(n):
return n * (n + 1) // 2
def formula_k2(n):
return n * (n + 1) * (2 * n + 1) // 6
def compare_table(n_list):
head = f"{'n':>5} {'sum k':>9} {'(4.6)':>9} {'match':>6} {'sum k^2':>11} {'(4.9)':>11} {'match':>6}"
print(head)
print("-" * len(head))
for n in n_list:
s1 = direct_sum(n, 1)
f1 = formula_k(n)
s2 = direct_sum(n, 2)
f2 = formula_k2(n)
print(f"{n:>5} {s1:>9} {f1:>9} {str(s1 == f1):>6}"
f" {s2:>11} {f2:>11} {str(s2 == f2):>6}")
compare_table([5, 20, 100])
n sum k (4.6) match sum k^2 (4.9) match
---------------------------------------------------------------
5 15 15 True 55 55 True
20 210 210 True 2870 2870 True
100 5050 5050 True 338350 338350 True
첫 줄이 서술 파트 4절 끝에서 손으로 확인한 값이다. \(n=5\)에서 \(\sum k = 15\)이고 \(\sum k^2 = 55\)이다.
세 줄이 모두 맞았지만 이것으로 공식이 증명된 것은 아니다. 확인한 \(n\)은 세 개뿐이고 자연수는 무한히 많다. 유한한 확인과 증명 사이의 거리가 다음 절에서 귀납법이 메우는 부분이다.
2. 귀납 단계는 항등식 하나이다#
정리 9을 공식에 쓸 때 실제로 해야 하는 계산은 두 가지뿐이다.
기저 단계: 공식에 \(n=1\)을 넣은 값이 첫 항과 같은가
귀납 단계: 공식의 값에 다음 항을 더한 것이, 공식의 \(n\) 자리에 \(n+1\)을 넣은 값과 같은가
귀납 단계는 \(n\)에 대한 항등식 하나이다. 즉 어떤 식에서 다른 식을 뺀 것이 \(0\)인지 묻는 문제이다. 이런 판정은 sympy가 대신해 줄 수 있다.
# The induction step of (4.6) and (4.9) reduces to a single algebraic identity
k, n = sp.symbols("k n", integer=True, positive=True)
closed_k = n * (n + 1) / 2
closed_k2 = n * (n + 1) * (2 * n + 1) / 6
base_k = sp.simplify(closed_k.subs(n, 1) - 1)
base_k2 = sp.simplify(closed_k2.subs(n, 1) - 1)
step_k = sp.simplify(closed_k + (n + 1) - closed_k.subs(n, n + 1))
step_k2 = sp.simplify(closed_k2 + (n + 1) ** 2 - closed_k2.subs(n, n + 1))
print("base step (4.6) :", closed_k.subs(n, 1), " gap =", base_k)
print("base step (4.9) :", closed_k2.subs(n, 1), " gap =", base_k2)
print("step (4.6) : F(n) + (n+1) - F(n+1) =", step_k)
print("step (4.9) : F(n) + (n+1)^2 - F(n+1) =", step_k2)
print("both steps hold :", step_k == 0 and step_k2 == 0)
base step (4.6) : 1 gap = 0
base step (4.9) : 1 gap = 0
step (4.6) : F(n) + (n+1) - F(n+1) = 0
step (4.9) : F(n) + (n+1)^2 - F(n+1) = 0
both steps hold : True
네 값이 모두 \(0\)이다. 기저 단계에서 공식의 값과 첫 항의 차가 \(0\)이고, 귀납 단계에서 두 식의 차가 \(0\)이다. 서술 파트 정리 11의 증명 방법 1이 손으로 한 통분과 인수분해가 바로 이 차를 \(0\)으로 만드는 계산이었다.
여기서 sympy가 한 일은 확인이지 발견이 아니다. closed_k와 closed_k2는 우리가 미리 적어 넣은 것이다. 공식을 적어 넣지 않으면 이 절의 코드는 아무것도 계산하지 못한다.
3. 기저 단계를 빼 보면#
서술 파트 2절의 오해 상자에 나온 명제를 그대로 계산해 본다. \(P(n)\)은 “\(n^2+n\)이 홀수이다”이다.
# A claim whose induction step holds while its base step fails
def claim_value(m):
return m * m + m
def is_odd(value):
return value % 2 == 1
def show_claim(limit):
for m in range(1, limit + 1):
value = claim_value(m)
print(f"m = {m:>2} m^2 + m = {value:>4} odd = {is_odd(value)}")
show_claim(8)
gap = sp.expand(claim_value(n + 1) - claim_value(n))
print("P(n+1) value minus P(n) value =", gap)
print("that gap is even :", sp.simplify(gap / 2).is_integer)
m = 1 m^2 + m = 2 odd = False
m = 2 m^2 + m = 6 odd = False
m = 3 m^2 + m = 12 odd = False
m = 4 m^2 + m = 20 odd = False
m = 5 m^2 + m = 30 odd = False
m = 6 m^2 + m = 42 odd = False
m = 7 m^2 + m = 56 odd = False
m = 8 m^2 + m = 72 odd = False
P(n+1) value minus P(n) value = 2*n + 2
that gap is even : True
두 결과를 나란히 놓아야 한다. 아래쪽이 말하는 것은 두 값의 차가 \(2n+2\), 즉 짝수라는 것이다. 홀수에 짝수를 더하면 홀수이므로 \(P(n) \Rightarrow P(n+1)\)은 모든 \(n\)에서 참이다. 귀납 단계는 성립한다.
그런데 위쪽 표에서 odd는 여덟 줄 모두 False이다. \(P(1)\)이 거짓이므로 이어질 출발점이 없고, 실제로 \(P(n)\)은 모든 \(n\)에서 거짓이다. 귀납 단계가 참이라는 것과 명제가 참이라는 것은 별개의 일이다.
4. 망원합은 답을 몰라도 쓸 수 있다#
정리 10가 말하는 상쇄를 항 단위로 본다. \(a_k = k^3\)으로 두고 (4.5)의 왼쪽을 \(n=5\)까지 늘어놓는다.
# Watch the middle terms cancel in a telescoping sum with a_k = k**3
def telescope_report(n, power):
total = 0
for k in range(1, n + 1):
term = (k + 1) ** power - k ** power
total = total + term
print(f"k = {k} ({k}+1)^{power} - {k}^{power} = {term:>4}"
f" running total = {total:>4}")
print(f"sum of all terms = {total}")
print(f"(n+1)^{power} - 1^{power} = {(n + 1) ** power - 1}")
telescope_report(5, 3)
k = 1 (1+1)^3 - 1^3 = 7 running total = 7
k = 2 (2+1)^3 - 2^3 = 19 running total = 26
k = 3 (3+1)^3 - 3^3 = 37 running total = 63
k = 4 (4+1)^3 - 4^3 = 61 running total = 124
k = 5 (5+1)^3 - 5^3 = 91 running total = 215
sum of all terms = 215
(n+1)^3 - 1^3 = 215
마지막 두 줄이 같다. 각 항 안의 \(k^3\)은 다음 항의 \((k+1)^3\)과 부호가 반대여서 지워지고, 맨 뒤의 \(6^3\)과 맨 앞의 \(1^3\)만 남는다.
이제 서술 파트 방법 2를 그대로 따라간다. (4.10)을 전개하면 \(3k^2 + 3k + 1\)이 나오고, 이것을 \(k=1\)부터 \(n\)까지 더하면 (4.11)이 된다. (4.11)에서 \(\sum k^2\)을 미지수로 두고 푼다. 답을 모른다고 가정한 상태에서 답이 나오는지 보려는 것이다.
# Expand the identity (4.10) and solve (4.11) for the sum we do not know yet
print("(k+1)^3 - k^3 =", sp.expand((k + 1) ** 3 - k ** 3))
left = sp.simplify(sp.summation((k + 1) ** 3 - k ** 3, (k, 1, n)))
right = sp.expand((n + 1) ** 3 - 1)
print("sum of the left side =", left)
print("(n+1)^3 - 1 =", right)
print("telescoping holds :", sp.simplify(left - right) == 0)
unknown = sp.Symbol("S2") # this stands for the sum of k**2
known = n * (n + 1) / 2 # (4.6) is already proved
equation = sp.Eq(right, 3 * unknown + 3 * known + n)
solved = sp.factor(sp.solve(equation, unknown)[0])
print("solved sum k^2 =", solved)
print("same as (4.9) :", sp.simplify(solved - closed_k2) == 0)
(k+1)^3 - k^3 = 3*k**2 + 3*k + 1
sum of the left side = n*(n**2 + 3*n + 3)
(n+1)^3 - 1 = n**3 + 3*n**2 + 3*n
telescoping holds : True
solved sum k^2 = n*(n + 1)*(2*n + 1)/6
same as (4.9) : True
solve가 돌려준 식이 (4.9)와 같다. 이 계산에는 \(\sum k^2\)의 공식이 어디에도 들어가지 않았다. 들어간 것은 항등식 (4.10)과, 앞서 증명해 둔 (4.6)뿐이다.
여기에 서술 파트가 지적한 구조가 그대로 보인다. \(\sum k^2\)을 얻는 데 \(\sum k\)가 필요했다. 차수를 하나씩 올려 가며 순서대로 얻어야 한다.
5. sympy는 답을 주고 증명은 주지 않는다#
summation은 공식을 몰라도 합을 \(n\)의 식으로 돌려준다. 서술 파트에서 유도한 두 공식이 실제로 나오는지 보고, 아직 유도하지 않은 차수까지 밀어 본다.
# Ask sympy for a closed form of the sum of k**p, p = 1..4
for power in (1, 2, 3, 4):
closed = sp.factor(sp.simplify(sp.summation(k ** power, (k, 1, n))))
print(f"sum k^{power} =", closed)
sum k^1 = n*(n + 1)/2
sum k^2 = n*(n + 1)*(2*n + 1)/6
sum k^3 = n**2*(n + 1)**2/4
sum k^4 = n*(n + 1)*(2*n + 1)*(3*n**2 + 3*n - 1)/30
차수 1과 2가 (4.6), (4.9)와 같다. 차수 3은 \(n^2(n+1)^2/4\), 즉 \(\left(\frac{n(n+1)}{2}\right)^2\)이며 처음 \(n\)개 자연수의 합을 제곱한 것이다. 차수 4에서는 앞의 세 인수 \(n\), \(n+1\), \(2n+1\)이 그대로 남고 \(3n^2+3n-1\)이 더 붙는다. 이 마지막 인수는 유리수 범위에서 더 이상 인수분해되지 않는다.
같은 공식을 이제 세 가지 방법으로 얻었다. 세 방법은 할 수 있는 일이 다르다.
방법 |
답을 모를 때 쓸 수 있는가 |
증명이 되는가 |
|---|---|---|
귀납법 |
아니다 |
그렇다 |
망원합 |
그렇다 |
그렇다 |
|
그렇다 |
아니다 |
세 번째 열이 요점이다
summation이 돌려준 식은 어떤 알고리즘의 출력이다. 그 알고리즘이 옳다는 것은 이 화면 밖의 문제이며, 화면에는 근거가 남지 않는다.
그러므로 기호 계산은 답을 짐작하는 데 쓴다. 짐작한 답을 이 실험 2절처럼 귀납법으로 확인하거나, 4절처럼 망원합으로 다시 유도하는 것이 증명이다.
서술 파트가 같은 공식을 두 번 유도한 이유가 여기에 있다. 망원합은 답을 몰라도 쓸 수 있으면서 동시에 증명이 되는 방법이다.
6. 이 공식이 필요해지는 곳#
두 공식은 이후 계산에서 계속 쓰인다. 쓰이는 형태는 합 자체가 아니라 합을 \(n\)의 거듭제곱으로 나눈 것이다. 넓이를 구할 때 구간을 \(n\)등분하면 밑변이 구간 길이의 \(1/n\)이 되고, 그 몫이 남기 때문이다.
\(\sum k\)를 \(n^2\)으로, \(\sum k^2\)을 \(n^3\)으로 나눈 값이 \(n\)이 커질 때 어디로 가는지 본다.
# Divide each sum by the next power of n and watch where the ratio settles
def ratio_sequence(n_max, p):
ratios = []
total = 0
for m in range(1, n_max + 1):
total = total + m ** p
ratios.append(total / m ** (p + 1))
return np.array(ratios)
n_max = 200
grid = np.arange(1, n_max + 1)
ratio_1 = ratio_sequence(n_max, 1)
ratio_2 = ratio_sequence(n_max, 2)
limit_1 = sp.limit(sp.summation(k, (k, 1, n)) / n ** 2, n, sp.oo)
limit_2 = sp.limit(sp.summation(k ** 2, (k, 1, n)) / n ** 3, n, sp.oo)
print("exact limit of (sum k) / n^2 =", limit_1)
print("exact limit of (sum k^2) / n^3 =", limit_2)
print(f"value at n = {n_max} : {ratio_1[-1]:.6f} and {ratio_2[-1]:.6f}")
fig, ax = plt.subplots()
ax.axhline(float(limit_1), color=C_SYM, linestyle="--", linewidth=1)
ax.axhline(float(limit_2), color=C_SYM, linestyle="--", linewidth=1)
ax.plot(grid, ratio_1, color=C_LOWER, label="(sum k) / n^2")
ax.plot(grid, ratio_2, color=C_UPPER, label="(sum k^2) / n^3")
ax.set_xlabel("n")
ax.set_ylabel("ratio")
ax.set_title("normalized sums approach 1/2 and 1/3")
ax.legend(loc="center right")
plt.show()
exact limit of (sum k) / n^2 = 1/2
exact limit of (sum k^2) / n^3 = 1/3
value at n = 200 : 0.502500 and 0.335838
두 수열이 각각 \(1/2\)와 \(1/3\)에 붙는다. 초록 점선은 sympy가 준 정확한 값이다. 위에서 접근하는 이유는 공식의 최고차항 다음에 오는 항이 양수이기 때문이다. \(\dfrac{n(n+1)}{2n^2} = \dfrac{1}{2} + \dfrac{1}{2n}\)이고 \(\dfrac{n(n+1)(2n+1)}{6n^3} = \dfrac{1}{3} + \dfrac{1}{2n} + \dfrac{1}{6n^2}\)이다.
\(1/3\)이라는 값은 뒤에 다시 나온다. 포물선 아래의 넓이를 구할 때 나오는 값이 바로 이것이다.
마치며#
두 공식이 실제 값과 맞는지 정수 연산으로 확인하였다. 다만 세 개의 \(n\)에서 맞았다는 것은 증명이 아니다. 귀납 단계는 항등식 하나로 줄어들고, 그 차가 \(0\)임을 기호 계산으로 확인하였다. 반대로 기저 단계를 빼면 귀납 단계가 모두 성립하는데도 명제가 모든 \(n\)에서 거짓일 수 있다는 것을 \(n^2+n\)으로 보았다.
망원합은 항등식 하나에서 시작해 답을 계산해 냈다. \(\sum k^2\)을 미지수로 두고 풀었을 때 (4.9)가 그대로 나왔고, 그 과정에 \(\sum k\)의 공식이 필요하였다. 차수를 하나씩 올려 가며 순서대로 얻는 구조이다.
sympy의 summation은 답을 가장 빨리 주지만 근거를 남기지 않는다. 세 방법을 나란히 놓았을 때 남는 것은 이 차이이다. 마지막 절에서 본 \(1/2\)와 \(1/3\)은 넓이를 구할 때 다시 만나게 된다.
서술 파트가 주장한 것과 그것을 확인한 이 노트북의 코드를 짝지어 둔다.
더 해 볼 것#
1절의
compare_table에10 ** 6을 넣어 보자. 값이 여전히 일치하는가. 직접 더하는 쪽은 덧셈을 몇 번 하고 공식 쪽은 몇 번 하는지 세어 보자. \(n\)을 열 배로 키우면 그 개수는 각각 몇 배가 되는가.2절의
closed_k2에+ 1을 붙여 보자. 귀납 단계는 그대로 \(0\)이 나오는데 기저 단계만 깨진다. 두 식의 차를 잡을 때 상수항이 왜 사라지는지 생각해 보자. 3절에서 본 상황과 같은 구조이다.4절의
telescope_report에서power를4로 바꾸어 보자. 그리고 같은 방식으로 (4.11)에 해당하는 식을 세워 \(\sum k^3\)을 풀어 보자. 이번에는 미지수 하나를 풀기 위해 어떤 공식들이 필요한가.6절의
ratio_sequence를p = 3으로 돌려 보자. \(\sum k^3 / n^4\)이 붙는 값은 얼마인가. 그 값이 \(1/(p+1)\) 꼴이라는 규칙이 보이는가.
짝이 되는 서술