작업중 !!

[TOC]

이산 수학

점화식 풀이 기법들

• 2차 선형동차점화식 (Linear homogenous recurrence)
  • 다음과 같은 형태: $a_k = \alpha \cdot a_k-1 + \beta \cdot b_k-2$.
  • $a_n=rⁿ$ 꼴이라고 생각하고 대입해 보면 $r² - \alpha\cdot r - \beta = 0$을 얻는다. 이 방정식의 해 $r$에 대해 $rⁿ$은 해가 됨.
  • 해가 둘 있을 경우, $a\cdot r₁ⁿ + b\cdot r₂ⁿ$ 꼴의 선형 결합도 해가 된다 (당연). 이 계수들을 초기상태에 맞도록 지정.
  • Application:
    • 피보나치 수열의 일반항은?
    • $p$의 확률로 이기는 bet을 한다. (승-패)가 $W$가 되거나 $-L$이 될 때까지 하는데, 이 때 $W$ 승으로 끝날 확률은? (ICPC WF '13 B)
  • 일반화: 3차, 4차, 5차.. 라도 같은 요령으로 풀 수 있다 (3차, 4차 방정식을 풀기 힘들어서 그렇지)
    • 중근이면 어떻게? 만약 $r$이 $m+1$번 중근으로 등장한다면 $rⁿ, n\cdot rⁿ, \cdots, n^m\cdot rⁿ$ 의 선형결합이 들어간다.

• 선형비동차점화식 (Linear non-homogenous recurrence)

  • $a_k = \alpha_k-1a_k-1 + \cdots + \alpha_k-na_k-n + f(n)$ (마지막의 $f(n)$에 주의!)
  • 해법
    • $a_n = b_n + h_n$으로 분해 ($b_n$은 점화식만 만족하고 초기상태는 만족하지 않는 답. 대개 $f(n)$과 비슷한 형태를 갖는다.
    • $h_n$을 찾고 $a_n$의 계수를 초기상태 성립하도록 맞춰 주면 됨.

• 간단한 정리