알티수학 쌤 수학 노트 센텀 알티수학 학원 · 부산 센텀 · 해운대

하키스틱 정리 증명 (5가지) 이항계수의 대각선 합 항등식 (feat. 파스칼의 삼각형, 더블카운팅, 생성함수)

글·그림 알티수학 쌤 · · 알티수학 인벤토리

파스칼의 삼각형에서 대각선 방향으로 이항계수를 더하면 깔끔한 닫힌 식(closed form)이 됩니다. 이 결과를 하키스틱 정리라 하는데, 오늘은 이 항등식의 증명 다섯 가지를 써 보겠습니다.

글 - 알티수학 쌤＠센텀 알티수학 학원

0. 하키스틱 정리

먼저 참고로, 이항계수를 나타내는 표기법은 아래 두 가지인데, 완전히 같은 것입니다.

nCr=(nr)_nC_r=\binom{n}{r}

파스칼의 삼각형에서 한 대각선을 따라 연속된 이항계수를 더하면, 그 합이 하나의 이항계수로 닫히는 항등식이 있습니다. 이것을 하키스틱 정리(Hockey Stick Identity)라 합니다. 파스칼의 삼각형에서 해당 항들을 연결하면 하키스틱 모양이 되기 때문에 붙여진 이름입니다.

하키스틱 정리 증명 (5가지) 이항계수의 대각선 합 항등식 (feat. 파스칼의 삼각형, 더블카운팅, 생성함수) — 그림 1

이 정리는 "크리스마스 양말 정리"라고 되어 있는 책도 있습니다. 제가 출간했던 KMO용 조합책 "조합의 원리와 기법" 에도 "크리스마스..." 라고 되어 있습니다.

하키스틱 정리 증명 (5가지) 이항계수의 대각선 합 항등식 (feat. 파스칼의 삼각형, 더블카운팅, 생성함수) — 그림 2
하키스틱 정리 증명 (5가지) 이항계수의 대각선 합 항등식 (feat. 파스칼의 삼각형, 더블카운팅, 생성함수) — 그림 3

그리고, 대각선 방향에 따라 두 가지 형태가 있습니다.

하키스틱 정리 증명 (5가지) 이항계수의 대각선 합 항등식 (feat. 파스칼의 삼각형, 더블카운팅, 생성함수) — 그림 4

n≥r≥0 인 정수에 대해,

형태 A (r 고정):

∑k=rn(kr)=(n+1r+1)\textcolor{#ff0010}{\sum _{k=r}^n\binom{k}{r}=\binom{n+1}{r+1}}

형태 B (r 증가):

∑j=0r(n+jj)=(n+r+1r)\sum _{j=0}^r\binom{n+j}{j}=\binom{n+r+1}{r}

형태 A 와 형태 B 는 아래 대칭공식에 의해 서로 같아지므로, 이 글에서는 형태 A 를 증명해 보겠습니다.

(nr)=(nn−r)\binom{n}{r}=\binom{n}{n-r}

예를 들어, r=2 일 때,

(22)+(32)+(42)+(52)=1+3+6+10=20=(63)\binom{2}{2}+\binom{3}{2}+\binom{4}{2}+\binom{5}{2}=1+3+6+10=20=\binom{6}{3}

이 성립합니다.

아래 증명 1~3은 대수적 방법이고, 증명 4~5는 조합적 방법입니다.

1. 증명 1 — 망원급수 (Telescoping)

아래 합 공식을 이용합니다.

(kr)+(kr+1)=(k+1r+1)\binom{k}{r}+\binom{k}{r+1}=\binom{k+1}{r+1}

아래와 같이 이항하여 뺄셈의 형태를 만듭니다.

(kr)=(k+1r+1)−(kr+1)\binom{k}{r}=\binom{k+1}{r+1}-\binom{k}{r+1}

양변을 k=r 부터 k=n 까지 더하면,

∑k=rn(kr)=∑k=rn{(k+1r+1)−(kr+1)}\sum _{k=r}^n\binom{k}{r}=\sum _{k=r}^n\left\{\binom{k+1}{r+1}-\binom{k}{r+1}\right\}

우변을 전개하면,

={(r+1r+1)−(rr+1)}+{(r+2r+1)−(r+1r+1)}+⋯+{(n+1r+1)−(nr+1)}=\left\{\binom{r+1}{r+1}-\binom{r}{r+1}\right\}+\left\{\binom{r+2}{r+1}-\binom{r+1}{r+1}\right\}+\cdots +\left\{\binom{n+1}{r+1}-\binom{n}{r+1}\right\}

인데, 이웃한 항들이 소거(telescoping)되고, 양 끝만 남습니다. 그런데

(rr+1)=0\binom{r}{r+1}=0

이므로, 최종적으로

∑k=rn(kr)=(n+1r+1)\textcolor{#ff0010}{\sum _{k=r}^n\binom{k}{r}=\binom{n+1}{r+1}}

이 됩니다.

2. 증명 2 — 수학적 귀납법

n 에 대한 수학적 귀납법으로 증명합니다. (r 은 고정된 상수로 취급)

(i) 기초 단계 (n=r) :

좌변은

∑k=rr(kr)=(rr)=1\sum _{k=r}^r\binom{k}{r}=\binom{r}{r}=1

이고, 우변은

(r+1r+1)=1\binom{r+1}{r+1}=1

이므로 성립합니다.

(ii) 귀납 단계 :

n=m (m≥r) 일 때 성립한다고 가정합니다. 즉,

∑k=rm(kr)=(m+1r+1)\sum _{k=r}^m\binom{k}{r}=\binom{m+1}{r+1}

이 성립한다고 가정하면, n=m+1 일 때,

∑k=rm+1(kr)=(∑k=rm(kr))+(m+1r)\sum _{k=r}^{m+1}\binom{k}{r}=\left(\sum _{k=r}^m\binom{k}{r}\right)+\binom{m+1}{r}

귀납 가정에 의해

=(m+1r+1)+(m+1r)=\binom{m+1}{r+1}+\binom{m+1}{r}

이고, 합 공식에 의해

=(m+2r+1)=\binom{m+2}{r+1}

이므로 n=m+1 일 때도 성립합니다.

따라서 모든 정수 n≥r 에 대해 항등식이 성립합니다.

3. 증명 3 — 다항식 생성함수

이항정리에 의해, 이항계수

(kr)\binom{k}{r}

은 다항식

(1+x)k(1+x)^k

의 전개에서 x^r 의 계수입니다. 따라서, 구하고자 하는 합은

∑k=rn(1+x)k\sum _{k=r}^n(1+x)^k

에서 x^r 의 계수를 찾는 것과 같습니다.

이 합은 첫째항 (1+x)^r, 공비 (1+x) 인 등비급수이므로, 합 공식에 의해

S=∑k=rn(1+x)k=(1+x)n+1−(1+x)r(1+x)−1=(1+x)n+1−(1+x)rxS=\sum _{k=r}^n(1+x)^k=\frac{(1+x)^{n+1}-(1+x)^r}{(1+x)-1}=\frac{(1+x)^{n+1}-(1+x)^r}{x}

가 됩니다. 이 식에서 x^r 의 계수를 구하려면, 분자에서 x^{r+1} 의 계수를 찾으면 됩니다. (분모의 x 로 나누므로 차수가 1 낮아지기 때문이죠.)

• (1+x)^{n+1} 에서 x^{r+1} 의 계수는

(n+1r+1)\binom{n+1}{r+1}

입니다.

• (1+x)^r 은 최고차항이 x^r 이므로 x^{r+1} 의 계수는 0 입니다.

따라서, S 에서 x^r 의 계수는

(n+1r+1)\textcolor{#ff0010}{\binom{n+1}{r+1}}

이 됩니다.

4. 증명 4 — 격자경로 모델 (더블카운팅)

하키스틱 정리의 우변

(n+1r+1)\binom{n+1}{r+1}

을 '격자 위에서의 최단 경로의 수'로 해석해봅니다.

즉, 총 n+1번의 이동 중 오른쪽 이동을 r+1번 선택하는 경우의 수와 같습니다.

총 이동 횟수: n+1

오른쪽 이동 횟수: r+1

위쪽 이동 횟수: (n+1) - (r+1) = n-r

따라서 이 조합은 원점 (0,0)에서 출발하여 도착점 (r+1, n-r)까지 가는 최단 경로의 수와 일치합니다.

하키스틱 정리 증명 (5가지) 이항계수의 대각선 합 항등식 (feat. 파스칼의 삼각형, 더블카운팅, 생성함수) — 그림 5

이것을 마지막으로 오른쪽 이동이 일어난 위치에 따라 분류해서 세어보겠습니다.

즉, 모든 경로는 반드시 x=r 에서 x=r+1 로 넘어가는 '마지막 오른쪽 이동'을 언젠가 단 한 번 하게 됩니다. 이 이동이 일어나는 지점의 높이를 기준으로 경우를 나눕니다.

마지막 오른쪽 이동이 시작되는 점을 (r, j)라고 합시다. 이때 j는 0 ≤ j ≤ n-r입니다. 여기서 k를 해당 지점까지 이동한 '총 횟수'로 정의하면

k=(오른쪽 이동 r번)+(위쪽 이동 j번)=r+jk=(\text{오른쪽 이동 }r\text{번})+(\text{위쪽 이동 }j\text{번})=r+j

여기서, j의 범위가 0 ~ n-r이므로, k의 범위는 r ~ n이 됩니다.

특정 k값에 대해 경로는 다음과 같이 세 구간으로 나뉩니다.

(0,0) → (r, k-r): 총 k번의 이동 중 오른쪽으로 r번 이동하는 경로 수

(kr)\binom{k}{r}

(r, k-r) → (r+1, k-r): 마지막 오른쪽 이동 (한 가지로 확정)

(r+1, k-r) → (r+1, n-r): 이후에는 도착점까지 위로만 이동 (한 가지로 확정)

따라서 마지막 오른쪽 이동이 k번째(총 이동 횟수 기준)에 일어나는 경로의 수는

(kr)\binom{k}{r}

입니다.

각 k(r ≤ k ≤ n)에 따른 경로들은 서로 겹치지 않으므로(배반 사건), 이들을 모두 더하면 전체 경로의 수와 같습니다.

∑k=rn(kr)=(n+1r+1)\sum _{k=r}^n\binom{k}{r}=\binom{n+1}{r+1}

증명이 완료되었습니다.

5. 증명 5 — 부분집합 모델 (더블카운팅)

집합

A={1,2,3,⋯ ,n+1}A=\left\{{1,2,3,\cdots ,n+1}\right\}

에서 원소 r+1 개짜리 부분집합을 선택하는 경우의 수를 두 가지 방법으로 세겠습니다.

방법 1 (직접 세기):

크기가 n+1 인 집합에서 r+1 개를 고르는 경우의 수는

(n+1r+1)\binom{n+1}{r+1}

입니다.

방법 2 (최대 원소 기준 분류):

선택된 r+1 개의 원소 중 가장 큰 원소(최대 원소)를 기준으로 분류합니다. 최대 원소를 k+1 이라 하면,

• 부분집합의 크기가 r+1 이므로, 최대 원소 k+1 은 적어도 r+1 이상이어야 합니다. 즉, r≤k≤n 입니다.

• 최대 원소가 k+1 로 고정되었으면, 나머지 r 개의 원소는 k+1 보다 작은 1, 2, …, k (총 k개) 중에서 골라야 합니다. 이 경우의 수는

(kr)\binom{k}{r}

입니다.

가능한 모든 k 에 대해 합산하면

∑k=rn(kr)\sum _{k=r}^n\binom{k}{r}

이 됩니다.

동일한 부분집합 전체를 두 가지 방식으로 세었으므로,

∑k=rn(kr)=(n+1r+1)\textcolor{#ff0010}{\sum _{k=r}^n\binom{k}{r}=\binom{n+1}{r+1}}

이 성립합니다.

하키스틱 정리 증명 (5가지) 이항계수의 대각선 합 항등식 (feat. 파스칼의 삼각형, 더블카운팅, 생성함수) — 그림 6

#하키스틱정리 #이항계수 #파스칼의삼각형 #조합론 #더블카운팅 #생성함수 #수학적귀납법 #망원급수 #텔레스코핑 #격자경로

같은 분류의 글 — 알티수학 인벤토리