"상수계수 선형점화식"의 두 판 사이의 차이

수학노트
둘러보기로 가기 검색하러 가기
잔글 (찾아 바꾸기 – “ * 구글 블로그 검색<br> ** http://blogsearch.google.com/blogsearch?q=” 문자열을 “” 문자열로)
 
(같은 사용자의 중간 판 26개는 보이지 않습니다)
1번째 줄: 1번째 줄:
−
==이 항목의 스프링노트 원문주소==
 
−
 
−
* [[선형점화식]]<br>
 
−
 
−
 
 
−
 
−
 
 
−
 
 
==개요==
 
==개요==
  
−
* 선형점화식은 선형 미분방정식의 이론과 유사한 점이 많다.<br>
+
* 선형점화식은 선형 미분방정식의 이론과 유사한 점이 많다
−
* [[선형대수학]]이 배경이 되는 이론이다<br>
+
* [[선형대수학]]의 도구들을 사용할 수 있다
 +
** [[점화식, 미분방정식, 선형대수학]] 항목 참조
  
−
 
 
  
−
 
+
==기본 정리==
 +
;정리
 +
복소수열 <math>\{a_n\}_{n=0}^\infty</math>과 생성함수 <math>A(x)=\sum_{n=0}^{\infty}a_nx^n</math>에 대하여 다음은 동치이다
  
−
==이계 선형점화식==
+
(1) 충분히 큰 <math>n</math>에 대하여 다음 형태의 점화식이 성립한다
 +
:<math>
 +
a_n+q_1a_{n-1}+q_2a_{n-2}+\cdots+q_ka_{n-k}=0 \label{lin}
 +
</math>
 +
(2) 생성함수 <math>A(x)</math>는 유리함수이다. 즉, 서로 소인 다항식 <math>P(x),Q(x)</math>가 존재하여, <math>A(x)=P(x)/Q(x)</math>이 성립한다.
  
−
* <math>pa_{n+2} + qa_{n+1} + ra_n = 0</math> 꼴의 점화식<br>
+
(3) 복소수 <math>\alpha_1,\cdots, \alpha_r</math>과 다항식 <math>f_1(n),\cdots, f_r(n)</math>이 존재하여, 충분히 큰 <math>n</math>에 대하여 다음이 성립한다
−
** <math>p+q+r =0</math> 일 때<br>
+
:<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> 을 구한다.
+
a_n=\sum_{i=1}^{r}f_i(n)\alpha_i^n \label{asym}
−
*** 계차수열을 알 때 일반항을 구하는 건 할 수 있지?
+
</math>
−
** <math>p+q+r \ne 0 </math> 일 때 : (교육 과정 외, 이 점화식만은 외우는 것을 권장함. 유도 과정이 너무 길다.)<br>
+
===관계===
−
***  결론부터 말하자면,<br>
+
* 생성함수가 <math>A(x)=P(x)/Q(x)</math>, <math>Q(x)=1+q_1x+\cdots+q_k x^k</math>인 경우, 선형점화식 \ref{lin}을 얻는다
−
**** <math>px^2 + qx + r = 0 </math> 의 두 근을 <math>\alpha, \beta</math> 라 하면, <math>a_n = A\alpha^{n-1} + B\beta^{n-1}</math> 꼴이며, 초기항 두 개를 아는 경우 상수를 찾을 수 있다.
+
* 다항식 <math>Q(x)=\prod_{i=1}^{r}(x-\alpha_i^{-1})^{d_i}</math>일 때, \ref{asym}에서 <math>\deg f_i=d_i-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> 이다. (근과 계수와의 관계) 그러므로<br><math>a_{n+2} - (\alpha + \beta)a_{n+1} + \alpha \beta a_n = 0</math> 라고 쓸 수 있다.<br> 이제 <math>a_{n+2} - \alpha a_{n+1} = \beta(a_{n+1} -\alpha a_n)</math> 으로 쓸 수 있다. <math>(a_{n+1} -\beta a_n)</math> 에 대한 등비수열을 풀기.<br><math>a_{n+2} - \beta a_{n+1} = \alpha (a_{n+1} -\beta a_n)</math> 로도 쓸 수 있다. <math>(a_{n+1} -\alpha a_n)</math> 에 대한 등비수열을 풀기.<br> 연립해서 <math>a_{n+1}</math> 을 소거하면 끝! 중근을 가지는 경우에 대한 유도는 독자에게 맡긴다.<br> 이 점화식을 <math>p+q+r=0</math> 인 점화식에 적용해서 풀지 말라는 법도 없다. 한 근이 무조건 1 이 나와서, (등비수열) + (상수) 꼴의 일반항이 나온다.<br>
 
−
*** ex) 피보나치 수열 <math>a_{n+2} =  a_{n+1} + a_n</math> 의 일반항을 구하시오. (<math>a_1 = a_ 2 = 1</math>)
 
−
* <math>pa_{n+2} + qa_{n+1} + ra_n = b_n</math> 꼴의 점화식<br>
 
−
** 양변에 적당히 <math>n</math> 에 대한 식을 더해서 공비 <math>r</math> 에 대한 등비수열 꼴로 만들 수 있는 경우가 많다.
 
  
−
 
 
  
−
 
+
==선형점화식의 예==
 +
===등비수열===
 +
* 점화식 <math>a_n=r a_{n-1}, a_0=1</math>
 +
* 일반항은 <math>a_n=r^n</math>
 +
* 생성함수는 다음과 같다
 +
:<math>
 +
A(x)=\sum _{n=0}^{\infty } a_n x^n=\sum _{n=0}^{\infty } r^n x^n=\frac{1}{1-r x}
 +
</math>
 +
* [[등비수열]] 항목 참조
  
−
==재미있는 사실==
 
  
−
 
+
===피보나치 수열===
 +
* 점화식 <math>a_{n+2} =  a_{n+1} + a_n</math>, <math>a_0 = a_ 1 = 1</math>
 +
* 생성함수는 다음과 같이 주어진다
 +
:<math>
 +
A(x)=\sum_{n=0}^{\infty} a_n x^n=\frac{1}{1-x-x^2}
 +
</math>
 +
* 분모 <math>Q(x)=1-x-x^2</math>의 해는 <math>\alpha_1^{-1}=\frac{1}{2} \left(-1-\sqrt{5}\right),\alpha_3^{-1}=\frac{1}{2} \left(\sqrt{5}-1\right)</math>이다
 +
* 피보나치 수열의 일반항은 다음과 같이 주어진다
 +
:<math>
 +
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
 +
</math>
 +
여기서
 +
:<math>
 +
A= \frac{1}{10} \left(5-\sqrt{5}\right),B= \frac{1}{10} \left(5+\sqrt{5}\right)
 +
</math>
 +
* [[피보나치 수열]] 항목 참조
  
−
* Math Overflow http://mathoverflow.net/search?q=
+
===다항식으로 주어진 수열===
−
* 네이버 지식인 http://kin.search.naver.com/search.naver?where=kin_qna&query=
+
* 일반항이 <math>a_n=\frac{1}{6} (n+1) (n+2) (n+3)</math>으로 주어진 수열
 +
* <math>1,4,10,20,35,56,84,120,\cdots</math>
 +
* 다음의 선형점화식을 만족시킨다
 +
:<math>
 +
a_n-4 a_{n-1}+6 a_{n-2}-4 a_{n-3}+a_{n-4}=0
 +
</math>
 +
* 생성함수는 다음과 같다
 +
:<math>
 +
A(x)=\sum _{n=0}^{\infty } a_n x^n=\sum _{n=0}^{\infty } \left(\frac{1}{6} (n+1) (n+2) (n+3)\right) x^n=\frac{1}{(1-x)^4}=\frac{1}{x^4-4 x^3+6 x^2-4 x+1}
 +
</math>
  
−
 
+
==이계 상수계수 선형점화식==
 +
===동차인 경우===
 +
* <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> 에 대한 등비수열 꼴로 만들 수 있는 경우가 많다.
  
−
* http://www.google.com/search?hl=en&tbs=tl:1&q=
 
−
* [[수학사연표 (역사)|수학사연표]]
 
−
*  
 
  
−
 
 
−
 
−
 
 
−
 
−
==메모==
 
−
 
−
 
 
−
 
−
 
 
  
 
==관련된 항목들==
 
==관련된 항목들==
 +
* [[선형점화식과 점근 급수]]
 +
* [[홀로노믹 수열]]
 +
* [[점화식]]
 +
* [[상수계수 이계 선형미분방정식]]
 +
* [[점화식, 미분방정식, 선형대수학]]
 +
* [[유리함수의 부분 분수 분해]]
 +
* [[스콜렘-말러-레흐 정리]]
  
−
* [[07 점화식]]<br>
+
==매스매티카 파일 및 계산 리소스==
−
* [[상수계수 이계 선형미분방정식]]<br>
+
* https://docs.google.com/file/d/0B8XXo8Tve1cxRmxDNTdQT1FRV0E/edit?usp=drivesdk
−
 
+
* http://fusharblog.com/solving-linear-recurrence-for-programming-contest/
−
 
 
−
 
 
−
 
 
−
 
 
−
==수학용어번역==
 
−
 
 
−
* 단어사전 http://www.google.com/dictionary?langpair=en|ko&q=
 
−
* 발음사전 http://www.forvo.com/search/
 
−
* [http://mathnet.kaist.ac.kr/mathnet/math_list.php?mode=list&ftype=&fstr= 대한수학회 수학 학술 용어집]<br>
 
−
** http://mathnet.kaist.ac.kr/mathnet/math_list.php?mode=list&ftype=eng_term&fstr=
 
−
* [http://www.nktech.net/science/term/term_l.jsp?l_mode=cate&s_code_cd=MA 남·북한수학용어비교]
 
−
* [http://kms.or.kr/home/kor/board/bulletin_list_subject.asp?bulletinid=%7BD6048897-56F9-43D7-8BB6-50B362D1243A%7D&boardname=%BC%F6%C7%D0%BF%EB%BE%EE%C5%E4%B7%D0%B9%E6&globalmenu=7&localmenu=4 대한수학회 수학용어한글화 게시판]
 
−
 
 
−
 
 
−
 
 
−
 
 
−
 
 
−
==사전 형태의 자료==
 
−
 
 
−
* http://ko.wikipedia.org/wiki/
 
−
* http://en.wikipedia.org/wiki/
 
−
* http://www.wolframalpha.com/input/?i=
 
−
* [http://dlmf.nist.gov/ NIST Digital Library of Mathematical Functions]
 
−
* [http://www.research.att.com/%7Enjas/sequences/index.html The On-Line Encyclopedia of Integer Sequences]<br>
 
−
** http://www.research.att.com/~njas/sequences/?q=
 
−
 
 
−
 
 
−
 
 
−
 
 
−
 
 
−
 
 
−
 
 
−
 
 
−
 
 
−
 
 
−
 
 
−
 
 
−
 
 
−
 
 
−
 
 
−
 
 
  
 +
==사전 형태의 자료==
 +
* http://en.wikipedia.org/wiki/Recurrence_relation#Linear_homogeneous_recurrence_relations_with_constant_coefficients
  
  
−
 
+
==리뷰논문, 에세이, 강의노트==
 +
* Speyer, [http://www.math.lsa.umich.edu/~speyer/LinearRecurrences.pdf Linear Recurrences and Rational Generating Functions]
  
−
 
 
  
−
==블로그==
+
[[분류:수열]]
  
−
* [http://navercast.naver.com/science/list 네이버 ]
+
==메타데이터==
 +
===위키데이터===
 +
* ID :  [https://www.wikidata.org/wiki/Q740970 Q740970]
 +
===Spacy 패턴 목록===
 +
* [{'LOWER': 'recurrence'}, {'LEMMA': 'relation'}]
 +
* [{'LOWER': 'recurrent'}, {'LEMMA': 'sequence'}]

2021년 2월 17일 (수) 05:48 기준 최신판

개요


기본 정리

정리

복소수열 \(\{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=r a_{n-1}, a_0=1\)
  • 일반항은 \(a_n=r^n\)
  • 생성함수는 다음과 같다

\[ A(x)=\sum _{n=0}^{\infty } a_n x^n=\sum _{n=0}^{\infty } r^n x^n=\frac{1}{1-r x} \]


피보나치 수열

  • 점화식 \(a_{n+2} = a_{n+1} + a_n\), \(a_0 = a_ 1 = 1\)
  • 생성함수는 다음과 같이 주어진다

\[ A(x)=\sum_{n=0}^{\infty} a_n x^n=\frac{1}{1-x-x^2} \]

  • 분모 \(Q(x)=1-x-x^2\)의 해는 \(\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) \]

다항식으로 주어진 수열

  • 일반항이 \(a_n=\frac{1}{6} (n+1) (n+2) (n+3)\)으로 주어진 수열
  • \(1,4,10,20,35,56,84,120,\cdots\)
  • 다음의 선형점화식을 만족시킨다

\[ a_n-4 a_{n-1}+6 a_{n-2}-4 a_{n-3}+a_{n-4}=0 \]

  • 생성함수는 다음과 같다

\[ A(x)=\sum _{n=0}^{\infty } a_n x^n=\sum _{n=0}^{\infty } \left(\frac{1}{6} (n+1) (n+2) (n+3)\right) x^n=\frac{1}{(1-x)^4}=\frac{1}{x^4-4 x^3+6 x^2-4 x+1} \]

이계 상수계수 선형점화식

동차인 경우

  • \(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\) 에 대한 등비수열 꼴로 만들 수 있는 경우가 많다.


관련된 항목들

매스매티카 파일 및 계산 리소스

사전 형태의 자료


리뷰논문, 에세이, 강의노트

메타데이터

위키데이터

Spacy 패턴 목록

  • [{'LOWER': 'recurrence'}, {'LEMMA': 'relation'}]
  • [{'LOWER': 'recurrent'}, {'LEMMA': 'sequence'}]
원본 주소 "https://wiki.mathnt.net/index.php?title=상수계수_선형점화식&oldid=52346"