7. 심화 단원: 군수열과 수학적 귀납법

[도입부] 학습 목표 (Learning Objectives)

데이터들을 무리(Group) 지어 하나의 덩어리로 바라보는 ‘군수열’의 원리를 배웁니다.
도미노 게임처럼 연쇄적으로 뻗어나가는 ‘수학적 귀납법’의 증명 과정을 파악합니다.
파이썬(Python)의 다차원 배열(2D Array/Lists)과 재귀함수(Recursive Function)를 통해 군수열과 귀납법의 원리를 코드로 입증합니다.

1. 덩어리들의 수열, 군수열(Group Sequence)

어떤 수열은 개별적인 숫자들로 나열되지 않고 괄호( )를 입수한 채로 묶음 단위의 패턴을 가집니다.

\[(1), (1, 2), (1, 2, 3), (1, 2, 3, 4), \dots\]

이처럼 나열된 수열을 규칙성이 비슷한 것끼리 하나로 다시 묶어(Group) 낸 것을 군수열이라고 부릅니다.

제 1군: $(1)$ -> 항의 개수(size) 1개
제 2군: $(1, 2)$ -> 항의 개수(size) 2개
제 3군: $(1, 2, 3)$ -> 항의 개수(size) 3개

이 개념은 현대 빅데이터나 표(Table)로 되어있는 스프레드시트를 구성할 때 매우 긴요하게 쓰입니다.

2. 수학적 귀납법: 영원히 쓰러지는 도미노

수학에서 어떤 거대한 공식을 증명할 때 쓰는 가장 파괴력 있는 무기가 바로 수학적 귀납법(Mathematical Induction)입니다. 이 증명 방식은 마치 도미노 게임과 단 1%의 틀림도 없이 동일합니다.

수많은 도미노를 끝없이 무너뜨리려면 다음 2가지 조건만 완벽하게 달성되면 됩니다.

(시작 지점 확인) 첫 번째 도미노를 내가 손가락으로 툭 친다. ($n=1$일 때 성립)
(전달력 확인) 만약 어떤 $k$번째 도미노가 쓰러진다면, 부딪히는 간격이 맞물려 있어서 그 다음 녀석인 $(k+1)$번째 도미노도 반드시 쓰러지게 세팅되어 있다. ($n=k$ 일때 성립하면 $n=k+1$도 성립함을 증명)

이 2단계 논리만 글로 완벽하게 썼다면? $1$번째가 쓰러지면 아까의 규칙으로 $2$번째가 쓰러지고, $2$번째가 쓰러지면 $3$번째가 쓰러지고… 무한대($\infty$)까지 모든 방정식이 사실임이 영원토록 증명되어 버립니다.

3. 💻 파이썬(Python)으로 느끼는 군수열과 귀납법의 향기

🐍 파이썬 예제 1: 군수열을 2차원 리스트(2D Array)로 만들기

프로그래밍에서 배열 안에 또 배열을 넣는 것을 다차원 배열(리스트)이라고 하는데, 군수열은 이것의 원조입니다.

# 1군, 2군, 3군, 4군... 군수열 생성하기 (다차원 리스트)
group_sequence = []

# 제 1군부터 제 5군까지 생성
for g_num in range(1, 6):
    group = list(range(1, g_num + 1))
    group_sequence.append(group)

print(group_sequence)
# 출력: [[1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 3, 4, 5]]

🐍 파이썬 예제 2: 수학적 귀납법과 똑같은 ‘재귀 함수(Recursion)’

$n=k$ 일때 공식을 믿고, 그것을 불러와서 $n=k+1$ 공식을 깨우는 도미노 논리는, 컴퓨터에서 함수가 자기 자신을 또 호출하는 지능적인 방식인 재귀 함수(Recursive Function)와 그 궤를 같이합니다.

# 귀납법 설계 방식이 똑같이 들어간 파이썬의 재귀 팩토리얼(n!) 함수
def factorial(n):
    # Base Case (도미노 1번 툭 치기: 귀납법 1번 조건)
    if n == 1:
        return 1
    
    # Recursive Case (도미노 전달 효과: 앞의 결과를 믿고 돌리기: 귀납법 2번 조건)
    # factorial(n-1)이 정상적으로 돈다고 가정! 
    # n = k 일 때를 믿고, k+1 을 완성시킨다.
    return n * factorial(n - 1)

print("5 팩토리얼 값:", factorial(5)) # 도미노가 5번 연속 쓰러짐! 결과: 120

함수 안에서 자기 자신(factorial())을 계속해서 불러오는 이 강력한 무한루프 설계는 수학적 귀납법의 사상 없이는 결코 이해할 수 없습니다. 컴퓨터 공학자들은 수학자들의 뇌구조를 고스란히 훔쳐와서 현대 IT 시스템과 알고리즘을 구축한 것입니다.

[결론] 학습 정리 (Summary)

군수열 (Group Sequence): 숫자들을 낱개가 아니라 비슷한 묶음으로 괄호를 치고 덩어리(차원) 단위로 취급하는 수열로서, 코딩의 다차원 배열과 같습니다.
수학적 귀납법 증명: 수많은 명제를 $n=1$의 성립 확인과 $n=k$의 가정 하에 $n=k+1$ 성립 확인이라는 “도미노 논리” 2단계로 끝내버리는 증명법입니다.
스스로를 호출하는 재귀함수: 귀납법에서 이전 단계의 값을 딛고 일어서는 논리는 현대 코딩 알고리즘에서 return n * func(n-1) 처럼 무한히 연쇄작용하는 재귀(Recursion) 함수로 완벽히 흡수되었습니다.

서브목차