[이산수학] 조합이론 - Part 4. 점화식

점화식이란? 

점화식(Reccurence relation)은 수열에서 항과 항 사이의 규칙을 수식으로 표현한 것이다.
즉, 수열의 어떤 항 a_n​을 앞에 있는 항들 a_n−1,a_n−2,…을 이용해서 나타낼 수 있다면, 이 식을 점화식이라고 한다.

점화식을 사용하면 수열의 구조를 간단하게 나타낼 수 있고, 반복되는 계산을 체계적으로 처리할 수 있다.

예를 들어 수열 1, 4, 7, 10, 13, …은 각 항이 앞 항보다 3만큼 커지는 규칙을 갖고 있다. 이 수열의 점화식은 다음과 같다.

이 식은 “첫째 항은 1이고, 그 다음 항은 앞 항에 3을 더해서 만든다”는 뜻이다.

***점화식에서 n은 수열의 항 번호를 뜻함.

 

"점화식을 푼다"는 것은?

점화식을 푼다는 것은 반복적으로 항을 계산하지 않고,
n만 입력해도 곧바로 값을 구할 수 있는 일반항 a_n​을 구하는 것이다.

예를 들어, 위에 예로 든 점화식을 생각해보자.

이 규칙에 따라 앞 몇 개 항을 직접 계산해보면 다음과 같다.

 

위 계산 결과를 수학적으로 전개해 보면 다음과 같다. 

 

이를 통해 각 항이 위와 같은 구조를 갖고 있다는 것을 알 수 있으며, 이 점화식의 해를 이와 같이 나타낼 수 있다.

 

✅ 예제  : 점화식    C_n = 2C_n-1 + 1,    C₁ = 1 의 해를 구하라. 

위 점화식은 각 항이 앞 항의 두 배에 1을 더하는 구조이다. 

C_n을 구하려면, C_n-1을 알아야 하고,
C_n-1을 알려면 C_n-2​를 알아야 하고... 계속 앞 항으로 들어가야 한다. (마치 마트료시카 인형처럼...) 

우선 하나씩 대입해가면서 전개해보자.

 

🔹 첫 번째 대입

여기서 C_n-1을 다시 점화식으로 풀면 다음과 같다.

다시 C_n에 대입해 보면 다음과 같다. 

🔹 두 번째 대입

이번에는 C_n-2를 풀어보자. 

이걸 C_n에 다시 대입하면 다음과 같다. 

이런 식으로 하다보면 패턴이 보이기 시작한다.

 

🔹 패턴을 식으로 정리하기

위 식은 다음과 같은 패턴을 갖는 것을 알 수 있다.

 

이제 초항 C₁에 도달할 때까지(마지막까지) 전개를 하면 다음과 같이 된다.

🔹 초항 대입하기

다시 문제로 돌아가 보면, 초항 C₁ = 1 이었다.

위 식에 C₁ = 1을 대입해 보면 다음과 같다. 

여기서 괄호 안의 식을 보면 등비수열의 합인 것을 알 수 있다. 

공비가 2이고 첫항이 1, 항의 개수는 n−1개인 등비수열의 합은:

따라서 전체 합은 다음과 같다. 

 

🔹 위 문제에 n = 4로 예를 들어 보면:

 

 

조합 이론에서 점화식을 다루는 이유?

점화식은 단순히 수열의 규칙을 나타내는 도구를 넘어,
조합 문제를 해결하는 데 자주 등장하는 수학적 도구이기도 하다. 그 이유는 다음과 같다.

1. 조합 문제는 반복 구조를 가진다.
   경우의 수가 앞 단계 결과를 바탕으로 계산되는 경우가 많다. 예: 계단 오르기, 타일 배치 문제
2. 조합 문제의 해를 수열로 정리하면 점화식이 자연스럽게 생긴다.
   예: 자연수의 합을 만드는 방법 수, 피보나치 수열
3. 조합 수식 자체가 점화식을 따른다.
   대표적으로 다음 조합 공식은 점화식이다.

n개 중 r개를 선택하는 경우의 수는 특정 원소 A를 선택한 경우의 수와 A를 선택하지 않은 경우의 수를 더한 것과 같다.

🔹 경우 1: 원소 A를 선택

 

• A를 이미 선택한 상태이므로
  남은 원소 n-1개 중에서 r−1개만 더 선택하면 됨.
• 경우의 수:

 

🔹 경우 2: 원소 A를 선택하지 않음

 

• 전체 n개 중에서 A를 제외한 n−1개 중에서
  r개를 전부 골라야 함
• 경우의 수: