"상수계수 선형점화식"의 두 판 사이의 차이
둘러보기로 가기
검색하러 가기
Pythagoras0 (토론 | 기여) |
Pythagoras0 (토론 | 기여) |
||
| 6번째 줄: | 6번째 줄: | ||
| − | + | ==기본 정리== | |
| + | * 복소수열 $\{a_n\}_{n=0}^\infty$과 생성함수 $A(x)=\sum_{n=0}^{\infty}a_nx^n$에 대하여 다음은 동치이다 | ||
| + | * (1) 충분히 큰 $n$에 대하여 다음 형태의 점화식이 성립한다 | ||
| + | $$ | ||
| + | a_n+q_1a_{n-1}+q_2a_{n-2}+\cdots+q_ka_{n-k}=0 \label{lin} | ||
| + | $$ | ||
| + | * (2) 생성함수 $A(x)$는 유리함수이다. 즉, 서로 소인 다항식 $P(x),Q(x)$가 존재하여, $A(x)=P(x)/Q(x)$이 성립한다. | ||
| + | * (3) 복소수 $\alpha_1,\cdots, \alpha_r$과 다항식 $f_1(n),\cdots, f_r(n)$이 존재하여, 충분히 큰 $n$에 대하여 다음이 성립한다 | ||
| + | $$ | ||
| + | a_n=\sum_{i=1}^{r}f_i(n)\alpha_i^n \label{asym} | ||
| + | $$ | ||
| + | ===관계=== | ||
| + | * 생성함수가 $A(x)=P(x)/Q(x)$, $Q(x)=1+q_1x+\cdots+q_k x^k$인 경우, 선형점화식 \ref{lin}을 얻는다 | ||
| + | * 다항식 $Q(x)=\prod_{i=1}^{r}(x-\alpha_i^{-1})^{d_i}$일 때, \ref{asym}에서 $\deg f_i=d_i-1$. | ||
| + | |||
| + | |||
| + | ===예=== | ||
| + | * [[피보나치 수열]] <math>a_{n+2} = a_{n+1} + a_n</math>, <math>a_0 = a_ 1 = 1</math> | ||
| + | * 생성함수는 다음과 같이 주어진다 | ||
| + | $$ | ||
| + | A(x)=\sum_{n=0}^{\infty} a_n x^n=\frac{x}{1-x-x^2} | ||
| + | $$ | ||
| + | * 분모 $Q(x)=x^2+x-1$의 해는 $\alpha_1^{-1}=\frac{1}{2} \left(-1-\sqrt{5}\right),\alpha_3^{-1}=\frac{1}{2} \left(\sqrt{5}-1\right)$이다 | ||
| + | * 피보나치 수열의 일반항은 다음과 같이 주어진다 | ||
| + | $$ | ||
| + | a_n=A\alpha_1^n+B\alpha_2^n=A \left(\frac{1}{2} \left(1-\sqrt{5}\right)\right)^n+B \left(\frac{1}{2} \left(1+\sqrt{5}\right)\right)^n | ||
| + | $$ | ||
| + | 여기서 | ||
| + | $$ | ||
| + | A= \frac{1}{10} \left(5-\sqrt{5}\right),B= \frac{1}{10} \left(5+\sqrt{5}\right) | ||
| + | $$ | ||
==이계 상수계수 선형점화식== | ==이계 상수계수 선형점화식== | ||
| + | ===동차인 경우=== | ||
| + | * <math>pa_{n+2} + qa_{n+1} + ra_n = 0</math> 꼴의 점화식 | ||
| + | ====<math>p+q+r =0</math> 일 때==== | ||
| + | * 잘 정리하면 <math>a_{n+2} - a_{n+1} = r(a_{n+1} - a_n)</math> 의 형태로 만들 수 있다. 그러면 계차수열 <math>b_n = a_{n+1} - a_{n}</math> 에 대한 등차수열이라고 생각하고, <math>b_n</math> 을 구한다. | ||
| + | |||
| + | ====<math>p+q+r \ne 0 </math> 일 때==== | ||
| + | * 다항식 <math>px^2 + qx + r = 0 </math> 의 두 근을 <math>\alpha, \beta</math> 라 하면, <math>a_n = A\alpha^{n-1} + B\beta^{n-1}</math> 꼴이며, 초기항 두 개를 아는 경우 상수를 찾을 수 있다. | ||
| + | ** 중근 <math>\alpha</math> 를 가지는 경우에는 <math>a_n = A\alpha^{n-1} + Bn\alpha^{n-1}</math> 꼴이 된다. | ||
| + | * <math>px^2 + qx + r = 0 </math> 의 두 근 <math>\alpha, \beta</math> 에 대하여, <math>p(\alpha+ \beta) = -q,\quad p(\alpha \beta) = r</math> 이다. (근과 계수와의 관계) 그러므로:<math>a_{n+2} - (\alpha + \beta)a_{n+1} + \alpha \beta a_n = 0</math> 라고 쓸 수 있다. 이제 <math>a_{n+2} - \alpha a_{n+1} = \beta(a_{n+1} -\alpha a_n)</math> 으로 쓸 수 있다. <math>(a_{n+1} -\beta a_n)</math> 에 대한 등비수열을 풀기.:<math>a_{n+2} - \beta a_{n+1} = \alpha (a_{n+1} -\beta a_n)</math> 로도 쓸 수 있다. <math>(a_{n+1} -\alpha a_n)</math> 에 대한 등비수열을 풀기. 연립해서 <math>a_{n+1}</math> 을 소거하면 끝! 중근을 가지는 경우에 대한 유도는 독자에게 맡긴다. 이 점화식을 <math>p+q+r=0</math> 인 점화식에 적용해서 풀지 말라는 법도 없다. 한 근이 무조건 1 이 나와서, (등비수열) + (상수) 꼴의 일반항이 나온다. | ||
| + | |||
| − | + | ===동차가 아닌 경우=== | |
| − | + | * <math>pa_{n+2} + qa_{n+1} + ra_n = b_n</math> 꼴의 점화식 | |
| − | + | * 양변에 적당히 <math>n</math> 에 대한 식을 더해서 공비 <math>r</math> 에 대한 등비수열 꼴로 만들 수 있는 경우가 많다. | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | * <math>pa_{n+2} + qa_{n+1} + ra_n = b_n</math> | ||
| − | |||
| 31번째 줄: | 62번째 줄: | ||
* [[점화식, 미분방정식, 선형대수학]] | * [[점화식, 미분방정식, 선형대수학]] | ||
* [[유리함수의 부분 분수 분해]] | * [[유리함수의 부분 분수 분해]] | ||
| + | |||
| + | |||
| + | ==매스매티카 파일 및 계산 리소스== | ||
| + | * https://docs.google.com/file/d/0B8XXo8Tve1cxRmxDNTdQT1FRV0E/edit?usp=drivesdk | ||
2013년 10월 3일 (목) 16:20 판
개요
- 선형점화식은 선형 미분방정식의 이론과 유사한 점이 많다
- 선형대수학의 도구들을 사용할 수 있다
- 점화식, 미분방정식, 선형대수학 항목 참조
기본 정리
- 복소수열 $\{a_n\}_{n=0}^\infty$과 생성함수 $A(x)=\sum_{n=0}^{\infty}a_nx^n$에 대하여 다음은 동치이다
- (1) 충분히 큰 $n$에 대하여 다음 형태의 점화식이 성립한다
$$ a_n+q_1a_{n-1}+q_2a_{n-2}+\cdots+q_ka_{n-k}=0 \label{lin} $$
- (2) 생성함수 $A(x)$는 유리함수이다. 즉, 서로 소인 다항식 $P(x),Q(x)$가 존재하여, $A(x)=P(x)/Q(x)$이 성립한다.
- (3) 복소수 $\alpha_1,\cdots, \alpha_r$과 다항식 $f_1(n),\cdots, f_r(n)$이 존재하여, 충분히 큰 $n$에 대하여 다음이 성립한다
$$ a_n=\sum_{i=1}^{r}f_i(n)\alpha_i^n \label{asym} $$
관계
- 생성함수가 $A(x)=P(x)/Q(x)$, $Q(x)=1+q_1x+\cdots+q_k x^k$인 경우, 선형점화식 \ref{lin}을 얻는다
- 다항식 $Q(x)=\prod_{i=1}^{r}(x-\alpha_i^{-1})^{d_i}$일 때, \ref{asym}에서 $\deg f_i=d_i-1$.
예
- 피보나치 수열 \(a_{n+2} = a_{n+1} + a_n\), \(a_0 = a_ 1 = 1\)
- 생성함수는 다음과 같이 주어진다
$$ A(x)=\sum_{n=0}^{\infty} a_n x^n=\frac{x}{1-x-x^2} $$
- 분모 $Q(x)=x^2+x-1$의 해는 $\alpha_1^{-1}=\frac{1}{2} \left(-1-\sqrt{5}\right),\alpha_3^{-1}=\frac{1}{2} \left(\sqrt{5}-1\right)$이다
- 피보나치 수열의 일반항은 다음과 같이 주어진다
$$ a_n=A\alpha_1^n+B\alpha_2^n=A \left(\frac{1}{2} \left(1-\sqrt{5}\right)\right)^n+B \left(\frac{1}{2} \left(1+\sqrt{5}\right)\right)^n $$ 여기서 $$ A= \frac{1}{10} \left(5-\sqrt{5}\right),B= \frac{1}{10} \left(5+\sqrt{5}\right) $$
이계 상수계수 선형점화식
동차인 경우
- \(pa_{n+2} + qa_{n+1} + ra_n = 0\) 꼴의 점화식
\(p+q+r =0\) 일 때
- 잘 정리하면 \(a_{n+2} - a_{n+1} = r(a_{n+1} - a_n)\) 의 형태로 만들 수 있다. 그러면 계차수열 \(b_n = a_{n+1} - a_{n}\) 에 대한 등차수열이라고 생각하고, \(b_n\) 을 구한다.
\(p+q+r \ne 0 \) 일 때
- 다항식 \(px^2 + qx + r = 0 \) 의 두 근을 \(\alpha, \beta\) 라 하면, \(a_n = A\alpha^{n-1} + B\beta^{n-1}\) 꼴이며, 초기항 두 개를 아는 경우 상수를 찾을 수 있다.
- 중근 \(\alpha\) 를 가지는 경우에는 \(a_n = A\alpha^{n-1} + Bn\alpha^{n-1}\) 꼴이 된다.
- \(px^2 + qx + r = 0 \) 의 두 근 \(\alpha, \beta\) 에 대하여, \(p(\alpha+ \beta) = -q,\quad p(\alpha \beta) = r\) 이다. (근과 계수와의 관계) 그러므로\[a_{n+2} - (\alpha + \beta)a_{n+1} + \alpha \beta a_n = 0\] 라고 쓸 수 있다. 이제 \(a_{n+2} - \alpha a_{n+1} = \beta(a_{n+1} -\alpha a_n)\) 으로 쓸 수 있다. \((a_{n+1} -\beta a_n)\) 에 대한 등비수열을 풀기.\[a_{n+2} - \beta a_{n+1} = \alpha (a_{n+1} -\beta a_n)\] 로도 쓸 수 있다. \((a_{n+1} -\alpha a_n)\) 에 대한 등비수열을 풀기. 연립해서 \(a_{n+1}\) 을 소거하면 끝! 중근을 가지는 경우에 대한 유도는 독자에게 맡긴다. 이 점화식을 \(p+q+r=0\) 인 점화식에 적용해서 풀지 말라는 법도 없다. 한 근이 무조건 1 이 나와서, (등비수열) + (상수) 꼴의 일반항이 나온다.
동차가 아닌 경우
- \(pa_{n+2} + qa_{n+1} + ra_n = b_n\) 꼴의 점화식
- 양변에 적당히 \(n\) 에 대한 식을 더해서 공비 \(r\) 에 대한 등비수열 꼴로 만들 수 있는 경우가 많다.
관련된 항목들
매스매티카 파일 및 계산 리소스
사전 형태의 자료