점화식 솔버

점화식 솔버 정보

점화식 솔버는 특성 방정식을 풀어 상수 계수를 갖는 모든 선형 동차 점화식의 폐쇄형 해(Closed-form solution)를 계산하고, 복소평면에 근을 표시하며, 시퀀스의 첫 N개 항을 생성합니다. 점화식을 순서가 지정된 계수 목록으로 입력하거나 a(n) = 3·a(n−1) − 2·a(n−2)와 같은 자연스러운 수학 수식으로 입력하면, 도구가 서로 다른 실근, 중근 및 켤레 복소수 쌍을 자동으로 처리합니다.

선형 점화식이란 무엇입니까?

차수가 k인 상수 계수를 갖는 선형 동차 점화식은 다음과 같은 형태를 가집니다.

여기서 c₁, c₂, …, c_k는 고정된 실수이고 k는 차수입니다. k개의 초깃값 a(0), a(1), …, a(k−1)과 함께 이 점화식은 이후의 모든 항을 고유하게 정의합니다. 대표적인 예는 다음과 같습니다.

• 피보나치(Fibonacci): a(n) = a(n−1) + a(n−2), 초깃값 0, 1 → 0, 1, 1, 2, 3, 5, 8, 13, …
• 루카스(Lucas): a(n) = a(n−1) + a(n−2), 초깃값 2, 1 → 2, 1, 3, 4, 7, 11, 18, 29, …
• 펠 수(Pell numbers): a(n) = 2·a(n−1) + a(n−2), 초깃값 0, 1 → 0, 1, 2, 5, 12, 29, 70, …
• 트리보나치(Tribonacci): a(n) = a(n−1) + a(n−2) + a(n−3), 초깃값 0, 0, 1 → 0, 0, 1, 1, 2, 4, 7, 13, 24, …

특성 방정식 방법

a(n)에 대한 폐쇄형 공식을 찾기 위해 a(n) = rⁿ 형태의 해를 찾습니다. 이를 점화식에 대입하고 r^n−k로 나누면 다음과 같습니다.

이것이 특성 방정식이며, r에 대한 k차 다항식입니다. 대수학의 기본 정리에 의해, 이 방정식은 정확히 k개의 복소수 근(중근 포함)을 가집니다. 점화식의 일반해는 이 근들의 구조에 따라 달라집니다.

사례 1: 서로 다른 실근 r₁, …, r_k

상수 A₁, …, A_k는 n = 0, 1, …, k−1을 대입하고 초깃값에 대한 선형 시스템을 풀어 고정됩니다.

사례 2: 중복도가 m인 근 r

각 중근은 m개의 선형 독립적인 기저 시퀀스 rⁿ, n·rⁿ, n²·rⁿ, …, n^m−1·rⁿ에 기여합니다.

사례 3: 켤레 복소수 근 r = ρ·e^iθ, r̄ = ρ·e^−iθ

점화식의 계수가 실수일 때, 복소수 근은 항상 켤레 쌍으로 나타납니다. 각 쌍은 기하학적 포락선 ρⁿ과 주파수 θ를 갖는 실수 진동 항으로 결합됩니다.

주근에 의한 성장 분류

ρ = max|r_i|를 가장 큰 근의 크기(스펙트럼 반경)라고 합시다. a(n)의 장기적인 거동은 다음에 의해 결정됩니다.

피보나치 — 풀이 예제

a(0) = 0 및 a(1) = 1인 피보나치 점화식 a(n) = a(n−1) + a(n−2)를 고려해 봅시다.

1. 특성 방정식: r² − r − 1 = 0
2. 근 (이차 방정식의 풀이): r = (1 ± √5) / 2, 따라서 φ ≈ 1.6180 및 ψ ≈ −0.6180
3. 일반 형태: a(n) = A·φⁿ + B·ψⁿ
4. 초기 조건 적용: A + B = 0 및 A·φ + B·ψ = 1을 풀면 A = 1/√5, B = −1/√5를 얻습니다.
5. 비네의 공식: a(n) = (φⁿ − ψⁿ) / √5

|ψ| < 1이기 때문에 n → ∞일 때 두 번째 항은 사라지며, 따라서 a(n)은 φⁿ / √5에 근사합니다. 이것이 피보나치 수가 단계별로 약 φ의 비율로 커지는 이유입니다.

이 솔버를 사용하는 방법

1. 입력 모드 선택: 가이드 모드에서는 차수를 선택하고 쉼표로 구분된 계수를 입력할 수 있습니다. 자유 형식 수식 모드에서는 a(n) = a(n-1) + 6*a(n-2) - 8*a(n-3)와 같은 전체 점화식을 입력할 수 있습니다.
2. 계수 또는 수식 입력. 소수(0.5)와 분수(1/2) 모두 입력 가능합니다.
3. 초깃값 제공. 점화식 차수와 일치하는 정확히 k개의 값(a(0), a(1), …, a(k−1))을 입력해야 합니다.
4. 표시할 항의 개수를 선택하세요 (최대 60개).
5. 점화식 풀기 클릭. 결과 페이지에 특성 방정식, 복소평면상의 근 위치, 폐쇄형 공식 및 시퀀스의 애니메이션 막대 차트가 표시됩니다.

지원 사례 및 제한 사항

• 차수: 1에서 6까지 (차수가 3 이상인 특성 다항식은 Durand–Kerner 반복법을 통해 수치적으로 풀이됩니다).
• 실수 상수 계수: 복소수 계수는 지원되지 않으며, 반드시 실수 c_i를 입력해야 합니다.
• 동차식 전용: 이 도구는 동차 점화식만 풉니다 (+ n 또는 + 2ⁿ과 같은 강제항 없음). 비동차 점화식의 경우, 여기서 동차 부분의 해를 구하고 별도로 특수해를 추가하세요.
• 수치 정밀도: 결과는 IEEE-754 배정밀도로 계산됩니다. 근의 크기 차이가 매우 큰 불안정한 점화식의 경우, 검증 배너에 폐쇄형과 반복 계산값 사이의 편차가 표시될 수 있습니다.

활용 분야

• 알고리즘 분석: 분할 정복 알고리즘의 실행 시간은 종종 선형 점화식을 따릅니다 (마스터 정리).
• 조합론: 카탈랑 수, 교란 순열, 타일링과 같은 시퀀스 계산은 빈번하게 점화식으로 주어집니다.
• 신호 처리: 피드백이 있는 이산 시간 LTI 시스템은 선형 점화식입니다. 시스템의 안정성은 근의 위치(단위 원 내부 여부)에 의해 결정됩니다.
• 인구 역학 및 금융: 복리 계산, 연령 구조 인구 모델, 자기 회귀 AR(p) 시계열 모델.
• 물리학: 1차원 격자 모델, 강결합(tight-binding) 해밀토니안, 전이 행렬 방법.

자주 묻는 질문

상수 계수를 갖는 선형 점화식이란 무엇입니까?

상수 계수를 갖는 선형 점화식은 a(n) = c₁·a(n−1) + c₂·a(n−2) + … + c_k·a(n−k) 형태의 방정식으로, 여기서 c₁, c₂, …, c_k는 고정된 실수이고 k는 차수입니다. 시퀀스의 각 항은 이전 k개 항의 선형 결합입니다. 일반적인 예로는 피보나치 점화식 a(n) = a(n−1) + a(n−2)와 초깃값이 다른 루카스 점화식이 있습니다.

점화식의 특성 방정식이란 무엇입니까?

점화식 a(n) = c₁·a(n−1) + c₂·a(n−2) + … + c_k·a(n−k)가 주어졌을 때, 그 특성 방정식은 r^k − c₁·r^k−1 − c₂·r^k−2 − … − c_k = 0입니다. 이 다항 방정식은 정확히 k개의 복소수 근(중근 포함)을 가지며, 점화식의 모든 해는 r이 근이고 j가 근의 중복도 마이너스 1까지인 n^j·rⁿ 형태의 시퀀스들의 선형 결합입니다.

a(n)의 폐쇄형 공식을 어떻게 얻습니까?

특성 방정식을 풀어 근 r₁, r₂, …, r_k를 찾습니다. 모든 근이 서로 다른 경우 폐쇄형은 a(n) = A₁·r₁ⁿ + A₂·r₂ⁿ + … + A_k·r_kⁿ이며, 여기서 상수 A_i는 초깃값을 대입하고 선형 시스템을 풀어 결정됩니다. 근 r의 중복도가 m인 경우, rⁿ, n·rⁿ, n²·rⁿ, …, n^m−1·rⁿ의 m개 기저 항이 기여합니다. 이 계산기는 이 전체 과정을 자동으로 수행합니다.

복소수 근은 시퀀스에서 무엇을 의미합니까?

점화식의 계수가 실수일 때, 복소수 근은 항상 켤레 쌍 r = ρ·e^iθ 및 r̄ = ρ·e^−iθ로 나타납니다. 이러한 쌍은 진동 동작을 생성합니다. 폐쇄형에는 2·ρⁿ·[α·cos(nθ) − β·sin(nθ)] 항이 포함됩니다. ρ가 1이면 시퀀스는 일정한 진폭으로 진동하고, ρ가 1보다 작으면 진동이 감쇄하며, ρ가 1보다 크면 진폭이 기하급수적으로 커집니다.

주근(Dominant root)이 시퀀스의 성장 방식을 어떻게 알려줍니까?

n이 커짐에 따라 절대값 |r|이 가장 큰 항이 다른 모든 항보다 우세해집니다. 그 크기가 더 빨리 커지기 때문입니다. 따라서 ρ = max|r_i|라면, |a(n)|은 점근적으로 ρⁿ에 비례합니다(주근이 중근인 경우 다항식 인자가 추가됨). 솔버는 이 원리에 따라 시퀀스를 분류합니다. ρ < 1이면 0으로 수렴, ρ = 1이면 유계, ρ > 1이면 기하급수적 성장으로 분류합니다.

이 도구로 피보나치 수열을 풀 수 있습니까?

네. 초깃값 0, 1과 함께 점화식 a(n) = a(n−1) + a(n−2)를 입력하세요. 계산기는 근 φ = (1 + √5)/2 및 ψ = (1 − √5)/2를 갖는 특성 방정식 r² − r − 1 = 0을 도출하고 비네의 공식 a(n) = (φⁿ − ψⁿ) / √5를 반환합니다. 입력 폼 위의 피보나치 빠른 예제를 클릭하여 전체 풀이 과정을 확인해 보세요.

a(n) = a(n−1) + n과 같은 비동차 점화식도 처리하나요?

아니요. 이 도구는 동차 점화식(강제항이 없는 형태)만 처리합니다. 비동차 점화식의 경우, 일반해를 동차 부분(여기서 풀이 가능)과 강제항에 대응하는 특수해의 합으로 분해해야 합니다. 일반적인 특수해 추측값은 다음과 같습니다. 다항식 강제항에는 동일 차수의 다항식, 지수 강제항에는 C·rⁿ, 삼각함수 강제항에는 A·cos(nθ) + B·sin(nθ)를 사용합니다.

추가 참고 자료

• 점화식 — 위키백과
• 상수 계수 선형 점화식 (영문) — 위키백과
• 특성 방정식 — 위키백과
• 피보나치 수열 — 위키백과
• Durand–Kerner 방법 (영문) — 위키백과

기타 관련 도구:

순서 관련 도구:

• 산술 시퀀스 계산기 높은 정밀도
• 큐빅 리스트
• 처음 n개의 소수
• 기하학적 시퀀스 계산기
• 피보나치 수 목록
• 소수의 목록
• 제곱수 목록
• 콜라츠 추측 계산기 새로운
• 행복한 수 계산기 새로운
• 마방진 생성기 새로운
• 카탈란 수 생성기 새로운
• 시그마 표기법 계산기 (합산) 새로운
• 곱 표기법 계산기 (Pi Notation) 새로운
• 파스칼의 삼각형 생성기 새로운
• 쌍둥이 소수 찾기 새로운
• 분할 함수 계산기 새로운
• 점화식 솔버 새로운