(이름공간을 뺀) 문서 제목 (page_title) | '선형점화식' |
전체 문서 제목 (page_prefixedtitle) | '선형점화식' |
편집 전 과거 문서의 위키텍스트 (old_wikitext) | '' |
편집 후 새 문서의 위키텍스트 (new_wikitext) | '{{학술}}
{{작성중}}
== 정의 ==
[[수열]] \((a_n)\)의 [[점화식]]이
: <math>a_{n+d}=\sum_{i=0}^{d-1}c_i a_{n+i}+f(n)</math>
꼴로 표현될 때, 이 식을 차수(degree) \(d\)인 '''선형점화식(linear recurrence relation)'''이라고 한다. 이때 \(c_0,c_1,\cdots, c_{d-1}\)은 상수이고 \(f\)는 [[산술적 함수]]이다.
== 예시 ==
* \(a_{n+1}=a_n+3\): [[등차수열]]의 일종으로, 이 수열의 일반항은 \(a_n=3n+c\)이며 \(c\)는 임의의 상수이다.
* \(a_{n+1}=2a_n\): [[등비수열]]의 일종으로, 이 수열의 일반항은 \(a_n= c \cdot 2^n\)이며 \(c\)는 임의의 상수이다.
* \(a_{n+2}=a_{n+1}+a_n\): [[피보나치 수열]]와 [[루카스 수]]의 점화식이다. \(a_0=0,a_1=1\)이면 피보나치 수열, \(a_0=2,a_1=1\)이면 루카스 수가 된다.
* \(a_{n+2}=2a_{n+1}-a_n\): 이 수열의 일반항은 \(a_n = c_1+c_2n\)이며, \(c_1,c_2\)는 임의의 상수이다.
* \(a_{n+1}=3a_n + 2n\): 이 수열의 일반항은 \(a_n=-n-\frac{1}{2}+c \cdot 3^n\)이다.
이들의 일반적인 해법은 아래에서 다룬다.
== 동차선형점화식의 풀이 ==
수열 \((a_n)\)의 선형점화식에서 \(f(n)=0\)일 경우, 그 점화식은 동차선형점화식(homogeneous linear recurrence relation)이라고 한다. \(f(n)\ne 0\)이면 비동차선형점화식(nonhomogeneous linear recurrence relation)이라고 한다.
일반적인 등비수열의 점화식이
: <math>a_{n+1} = ra_n</math> (단, \(r\)은 상수)
로 주어졌을 경우, 일반항은
: <math>a_n=cr^n</math>
으로 주어진다. 이제 좀 더 복잡한 점화식
: <math>a_{n+2}=r_0 a_n+r_1 a_{n+1}</math>
을 생각하자. \(a_n=t^n\)이 점화식을 만족한다고 가정하고 위의 점화식에 대입하면
: <math>t^{n+2}=r_0t^n+r_1t^{n+1}</math>
을 얻고 식을 간단히 하여
: <math>t^2 - r_1 t -r_0=0</math>
을 얻는다. [[이차방정식]]의 근의 공식에 의해
: <math>t=\frac{r_1\pm \sqrt{r_1^2 + 4r_0}}{2}</math>
이다. \(\alpha,\beta\)를
: <math>\alpha=\frac{r_1+ \sqrt{r_1^2 + 4r_0}}{2},\beta=\frac{r_1- \sqrt{r_1^2 + 4r_0}}{2}</math>
로 정의하자. 그러면 \((\alpha^n)\)와 \((\beta^n)\)은 점화식을 만족하는 수열임을 안다.
일반적으로
== 비동차선형점화식의 풀이 ==
== 같이 보기 ==
* [[미분방정식]]' |
편집 전후의 차이 (edit_diff) | '@@ -1 +1,39 @@
+{{학술}}
+{{작성중}}
+== 정의 ==
+[[수열]] \((a_n)\)의 [[점화식]]이
+: <math>a_{n+d}=\sum_{i=0}^{d-1}c_i a_{n+i}+f(n)</math>
+꼴로 표현될 때, 이 식을 차수(degree) \(d\)인 '''선형점화식(linear recurrence relation)'''이라고 한다. 이때 \(c_0,c_1,\cdots, c_{d-1}\)은 상수이고 \(f\)는 [[산술적 함수]]이다.
+== 예시 ==
+* \(a_{n+1}=a_n+3\): [[등차수열]]의 일종으로, 이 수열의 일반항은 \(a_n=3n+c\)이며 \(c\)는 임의의 상수이다.
+* \(a_{n+1}=2a_n\): [[등비수열]]의 일종으로, 이 수열의 일반항은 \(a_n= c \cdot 2^n\)이며 \(c\)는 임의의 상수이다.
+* \(a_{n+2}=a_{n+1}+a_n\): [[피보나치 수열]]와 [[루카스 수]]의 점화식이다. \(a_0=0,a_1=1\)이면 피보나치 수열, \(a_0=2,a_1=1\)이면 루카스 수가 된다.
+* \(a_{n+2}=2a_{n+1}-a_n\): 이 수열의 일반항은 \(a_n = c_1+c_2n\)이며, \(c_1,c_2\)는 임의의 상수이다.
+* \(a_{n+1}=3a_n + 2n\): 이 수열의 일반항은 \(a_n=-n-\frac{1}{2}+c \cdot 3^n\)이다.
+이들의 일반적인 해법은 아래에서 다룬다.
+
+== 동차선형점화식의 풀이 ==
+수열 \((a_n)\)의 선형점화식에서 \(f(n)=0\)일 경우, 그 점화식은 동차선형점화식(homogeneous linear recurrence relation)이라고 한다. \(f(n)\ne 0\)이면 비동차선형점화식(nonhomogeneous linear recurrence relation)이라고 한다.
+일반적인 등비수열의 점화식이
+: <math>a_{n+1} = ra_n</math> (단, \(r\)은 상수)
+로 주어졌을 경우, 일반항은
+: <math>a_n=cr^n</math>
+으로 주어진다. 이제 좀 더 복잡한 점화식
+: <math>a_{n+2}=r_0 a_n+r_1 a_{n+1}</math>
+을 생각하자. \(a_n=t^n\)이 점화식을 만족한다고 가정하고 위의 점화식에 대입하면
+: <math>t^{n+2}=r_0t^n+r_1t^{n+1}</math>
+을 얻고 식을 간단히 하여
+: <math>t^2 - r_1 t -r_0=0</math>
+을 얻는다. [[이차방정식]]의 근의 공식에 의해
+: <math>t=\frac{r_1\pm \sqrt{r_1^2 + 4r_0}}{2}</math>
+이다. \(\alpha,\beta\)를
+: <math>\alpha=\frac{r_1+ \sqrt{r_1^2 + 4r_0}}{2},\beta=\frac{r_1- \sqrt{r_1^2 + 4r_0}}{2}</math>
+로 정의하자. 그러면 \((\alpha^n)\)와 \((\beta^n)\)은 점화식을 만족하는 수열임을 안다.
+
+일반적으로
+
+== 비동차선형점화식의 풀이 ==
+
+== 같이 보기 ==
+* [[미분방정식]]
' |
편집 중 추가된 줄 (added_lines) | [
0 => '{{학술}}',
1 => '{{작성중}}',
2 => '== 정의 ==',
3 => '[[수열]] \((a_n)\)의 [[점화식]]이',
4 => ': <math>a_{n+d}=\sum_{i=0}^{d-1}c_i a_{n+i}+f(n)</math>',
5 => '꼴로 표현될 때, 이 식을 차수(degree) \(d\)인 '''선형점화식(linear recurrence relation)'''이라고 한다. 이때 \(c_0,c_1,\cdots, c_{d-1}\)은 상수이고 \(f\)는 [[산술적 함수]]이다.',
6 => '== 예시 ==',
7 => '* \(a_{n+1}=a_n+3\): [[등차수열]]의 일종으로, 이 수열의 일반항은 \(a_n=3n+c\)이며 \(c\)는 임의의 상수이다.',
8 => '* \(a_{n+1}=2a_n\): [[등비수열]]의 일종으로, 이 수열의 일반항은 \(a_n= c \cdot 2^n\)이며 \(c\)는 임의의 상수이다.',
9 => '* \(a_{n+2}=a_{n+1}+a_n\): [[피보나치 수열]]와 [[루카스 수]]의 점화식이다. \(a_0=0,a_1=1\)이면 피보나치 수열, \(a_0=2,a_1=1\)이면 루카스 수가 된다.',
10 => '* \(a_{n+2}=2a_{n+1}-a_n\): 이 수열의 일반항은 \(a_n = c_1+c_2n\)이며, \(c_1,c_2\)는 임의의 상수이다.',
11 => '* \(a_{n+1}=3a_n + 2n\): 이 수열의 일반항은 \(a_n=-n-\frac{1}{2}+c \cdot 3^n\)이다.',
12 => '이들의 일반적인 해법은 아래에서 다룬다.',
13 => false,
14 => '== 동차선형점화식의 풀이 ==',
15 => '수열 \((a_n)\)의 선형점화식에서 \(f(n)=0\)일 경우, 그 점화식은 동차선형점화식(homogeneous linear recurrence relation)이라고 한다. \(f(n)\ne 0\)이면 비동차선형점화식(nonhomogeneous linear recurrence relation)이라고 한다.',
16 => '일반적인 등비수열의 점화식이',
17 => ': <math>a_{n+1} = ra_n</math> (단, \(r\)은 상수)',
18 => '로 주어졌을 경우, 일반항은',
19 => ': <math>a_n=cr^n</math>',
20 => '으로 주어진다. 이제 좀 더 복잡한 점화식',
21 => ': <math>a_{n+2}=r_0 a_n+r_1 a_{n+1}</math>',
22 => '을 생각하자. \(a_n=t^n\)이 점화식을 만족한다고 가정하고 위의 점화식에 대입하면',
23 => ': <math>t^{n+2}=r_0t^n+r_1t^{n+1}</math>',
24 => '을 얻고 식을 간단히 하여',
25 => ': <math>t^2 - r_1 t -r_0=0</math>',
26 => '을 얻는다. [[이차방정식]]의 근의 공식에 의해',
27 => ': <math>t=\frac{r_1\pm \sqrt{r_1^2 + 4r_0}}{2}</math>',
28 => '이다. \(\alpha,\beta\)를',
29 => ': <math>\alpha=\frac{r_1+ \sqrt{r_1^2 + 4r_0}}{2},\beta=\frac{r_1- \sqrt{r_1^2 + 4r_0}}{2}</math>',
30 => '로 정의하자. 그러면 \((\alpha^n)\)와 \((\beta^n)\)은 점화식을 만족하는 수열임을 안다.',
31 => false,
32 => '일반적으로',
33 => false,
34 => '== 비동차선형점화식의 풀이 ==',
35 => false,
36 => '== 같이 보기 ==',
37 => '* [[미분방정식]]'
] |