(→황금비) |
잔글 (→n번째 항 계산하기) |
||
| 39번째 줄: | 39번째 줄: | ||
<math>A_n = \left[ \begin{array}{cc} a_{n+2} & a_{n+1} \\ a_{n+1} & a_{n} \end{array} \right] </math>이라고 하면, <math>A_{n+1} = \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right] A_n </math>가 성립한다. <math>a_0 = 0</math>이라고 하면, <math>A_0</math>도 역시 <math> \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right] </math>가 된다. 이것들을 이용하면, <math>A_n = \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right]^{n+1}</math>가 성립함을 알 수 있다. | <math>A_n = \left[ \begin{array}{cc} a_{n+2} & a_{n+1} \\ a_{n+1} & a_{n} \end{array} \right] </math>이라고 하면, <math>A_{n+1} = \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right] A_n </math>가 성립한다. <math>a_0 = 0</math>이라고 하면, <math>A_0</math>도 역시 <math> \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right] </math>가 된다. 이것들을 이용하면, <math>A_n = \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right]^{n+1}</math>가 성립함을 알 수 있다. | ||
이 식이 요긴하게 쓸 수 있는데, 큰 <math>n</math>에 대해서 <math>a_n</math>을 구할 수 있기 때문이다. 물론 | 이 식이 요긴하게 쓸 수 있는데, 큰 <math>n</math>에 대해서 <math>a_n</math>을 구할 수 있기 때문이다. <math>n</math>제곱을 <math>O(\log n)</math>번의 곱셈만에 구할 수 있다는 걸 이용하면 된다. 물론 위에 있는 일반항에 대입해 버리면 되지만, 일반항 쪽은 소수점 계산이 필요하기 때문에 정확한 값을 구하기 쉽지 않지만, {{ㅊ|<math>\mathbb{Q} [\sqrt{5}]</math>를 구현하면 어떨까}} 이것을 이용하면 정확하고 빠르게 값을 계산할 수 있다. | ||
피보나치 수열 뿐만 아니라 | 피보나치 수열 뿐만 아니라 [[점화식]]이 그 전 항들의 어떤 선형 합, 즉, <math>a_{n+k} = \sum_{i=0}^{k-1} c_i a_{n+i} </math> 꼴로 나타날 때에는 이런 전개가 가능하다. {{ㅊ|그중 가장 간단한게 이거}} | ||
{{각주}} | {{각주}} | ||
[[분류:수열]] | [[분류:수열]] | ||
2015년 6월 4일 (목) 13:51 판
개요
피보나치 수열(Fibonacci sequence)은 다음과 같은 정수의 수열을 말한다.
첫항에 0을 포함시키기도 한다. 이것은 처음의 두 수를 0,1로 선택하냐 1,1로 선택하냐의 차이다.
점화식은 다음과 같다.
- [math]\displaystyle{ a_1 = 1, a_2 = 1 }[/math]
- [math]\displaystyle{ a_{n+2} = a_{n+1} + a_n }[/math]
일반항은 다음과 같다.
- [math]\displaystyle{ a_n = \frac{\phi^n - \psi^n}{\phi - \psi} }[/math]
- [math]\displaystyle{ \phi = \frac{1+\sqrt{5}}{2}, \psi = \frac{1-\sqrt{5}}{2} }[/math], [math]\displaystyle{ \phi, \psi }[/math]는 [math]\displaystyle{ x^2 - x - 1 = 0 }[/math]의 해로 큰 쪽이 [math]\displaystyle{ \phi }[/math], 작은 쪽이 [math]\displaystyle{ \psi }[/math]이다.
아이디어
피보나치는 다음과 같은 상황을 생각했다.
- 첫 달 처음에 갓 태어난 암수 토끼 한 쌍이 있다.
- 토끼는 한 달동안 자라 어른 토끼가 된다.
- 어른 토끼 한 쌍은 그 달 마지막에 암수 토끼 한 쌍을 낳는다.
심지어 안죽는다
그렇다면 매 달 처음에 토끼가 몇 마리나 있을까에 대해 답을 찾다가 발견한 수열이다.
특징
황금비
[math]\displaystyle{ \lim_{n \rightarrow \infty} \frac{a_{n+1}}{a_n} = \phi }[/math]이다. 여기의 [math]\displaystyle{ \phi }[/math]는 위의 그거. 황금비라고 부른다.
[math]\displaystyle{ \begin{align} \lim_{n \rightarrow \infty} \frac{a_{n+1}}{a_n} &= \lim_{n \rightarrow \infty} \frac{a_{n+1}+a_n}{a_{n+1}} &= 1 + \frac{1}{\lim_{n \rightarrow \infty} \frac{a_{n+1}}{a_n}} \end{align} }[/math]
를 이용하면, [math]\displaystyle{ x = 1+\frac{1}{x} }[/math] 방정식을 푸는 형태가 되어 구할 수 있다. [1]
n번째 항 계산하기
[math]\displaystyle{ A_n = \left[ \begin{array}{cc} a_{n+2} & a_{n+1} \\ a_{n+1} & a_{n} \end{array} \right] }[/math]이라고 하면, [math]\displaystyle{ A_{n+1} = \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right] A_n }[/math]가 성립한다. [math]\displaystyle{ a_0 = 0 }[/math]이라고 하면, [math]\displaystyle{ A_0 }[/math]도 역시 [math]\displaystyle{ \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right] }[/math]가 된다. 이것들을 이용하면, [math]\displaystyle{ A_n = \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right]^{n+1} }[/math]가 성립함을 알 수 있다.
이 식이 요긴하게 쓸 수 있는데, 큰 [math]\displaystyle{ n }[/math]에 대해서 [math]\displaystyle{ a_n }[/math]을 구할 수 있기 때문이다. [math]\displaystyle{ n }[/math]제곱을 [math]\displaystyle{ O(\log n) }[/math]번의 곱셈만에 구할 수 있다는 걸 이용하면 된다. 물론 위에 있는 일반항에 대입해 버리면 되지만, 일반항 쪽은 소수점 계산이 필요하기 때문에 정확한 값을 구하기 쉽지 않지만, [math]\displaystyle{ \mathbb{Q} [\sqrt{5}] }[/math]를 구현하면 어떨까 이것을 이용하면 정확하고 빠르게 값을 계산할 수 있다.
피보나치 수열 뿐만 아니라 점화식이 그 전 항들의 어떤 선형 합, 즉, [math]\displaystyle{ a_{n+k} = \sum_{i=0}^{k-1} c_i a_{n+i} }[/math] 꼴로 나타날 때에는 이런 전개가 가능하다. 그중 가장 간단한게 이거
각주
- ↑ 잘 보면 첫 항이 뭐냐에 상관없이 황금비로 수렴한다는 것을 알 수 있다.