피보나치 수열의 성질

 

 

 KMO 2차에 수열 관련해서 수학적 귀납법으로 증명하는 문제가 많이 보이는 것 같아서 가장 대표적인 수열인 피보나치 수열에 대해 정리해보려고 한다. PS에서도 자주 나오니까 도움이 될 것 같다.

 

 

2023 중캠 2차 3번 (AOPS링크)

Math Message Boards FAQ & Community Help | AoPS

  피보나치 수열 관련된 문제로 이런 문제가 있는데, $a_{n} = 4{F_{2n-1}}^2 + {F_{2n}}^2$임을 증명하는 (더러운)문제이다. (솔직히 사람이 이걸 어떻게 생각하는지 모르겠다)

 

 

정의

피보나치 수열은 자연수 $n$에 대해 아래와 같이 정의된다.

$$F_{1} = F_{2} = 1$$

$$F_{n} = F_{n-1} + F_{n-2}\space (n\geq 3)$$

 

정리 1.

$$\forall m,n\in\mathbb{N}, m\geq 2, n\geq 1\rightarrow  F_{m+n} = F_{m-1}F_{n}+F_{m}F_{n+1}$$

 

증명)

 $n$에 대한 수학적 귀납법

(1) $n=1\Rightarrow F_{m+n} =F_{m+1}= F_{m-1}+F_{m} = F_{m-1}F_{1} + F_{m}F_{2}$

 

(2) $n=k, n=k-1$일 때 성립 가정

 

(3) $n=k+1$일 때

$$F_{m+k-1} = F_{m-1}F_{k-1} + F_{m}F_{k}\space (by\space (2))$$

 

$$F_{m+k} = F_{m-1}F_{k} + F_{m}F_{k+1}\space (by\space (2))$$

 

$$\therefore F_{m+(k+1)}=F_{m+k}+F_{m+k-1} = F_{m-1}(F_{k-1}+F_{k})+F_{m}(F_{k}+F_{k-1})$$$$=F_{m-1}F_{k+1}+F_{m}F_{k+2}$$

 

정리 2. 

$$F_{2n-1} = {F_{n}}^2+{F_{n-1}}^2, F_{2n} = {F_{n+1}}^2-{F_{n-1}}^2\space (n\leq 2)$$

 

증명)

정리 1에서 $m\leftarrow n+1$

$$F_{2n+1} = {F_{n}}^2+{F_{n+1}}^2$$

$$\Rightarrow F_{2n-1} = {F_{n-1}}^2+{F_{n}}^2\space\space (n\leftarrow n-1)$$

 

정리 1에서 $m\leftarrow n$

$$F_{2n} = F_{n-1}F_{n} + F_{n}F_{n+1} = F_{n}(F_{n-1}+F_{n+1})$$

$F_{n} = F_{n+1} - F_{n-1}$이므로,

$$F_{2n} = (F_{n+1}-F_{n-1})(F_{n-1}+F_{n+1}) = {F_{n+1}}^2 - {F_{n-1}}^2$$

 

 

정리 3.

$$F_{5n+2} > 10^{n}\space\space (n\in \mathbb{N})$$

 

증명)

$n$에 대한 수학적 귀납법

(1) $n=1 \Rightarrow F_{7} = 13 > 10$

 

(2) $n=k$에 대해 성립 가정 $\rightarrow F_{5k+2} > 10^{k}$

 

(3) $n=k+1$일 때

$$F_{5k+7} = F_{5k+1}F_{5}+F_{5k+2}F_{6}=5F_{5k+1}+8F_{5k+2}> 2F_{5k+1} + 2F_{5k} + 8F_{5k+2} = 10F_{5k+2} > 10^{k+1}$$

 

 

정리 4.

$$F_{m}\space |\space F_{mn}\space\space (m,n\in \mathbb{N})$$

 

증명)

$n$에 대한 수학적 귀납법

(1) $n=1 \Rightarrow F_{m}\space |\space F_{m}$

 

(2) $n=k$일 때 성립 가정

 

(3) $n=k+1$일 때$$F_{m(k+1)} = F_{mk+m} = F_{mk-1}F_{m} + F_{mk}F_{m+1}$$

$F_{m}, F_{mk}$는 $F_{m}$으로 나누어떨어지므로

$$F_{m}\space |\space F_{m(k+1)}$$

 

 

정리 5.

$$gcd(F_{n},F_{n+1}) = 1\space\space (n\in\mathbb{N})$$

 

증명)

$F_{n+1} = F_{n} + F_{n-1}$이므로 $gcd(F_{n},F_{n+1}) = gcd(F_{n},F_{n-1})$

$i.s.w.\space\space gcd(F_{n},F_{n+1}) = gcd(F_{n},F_{n-1})=gcd(F_{n-2},F_{n-1})=\cdot\cdot\cdot=gcd(F_{1},F_{2}) = 1$

 

 

정리 6.

$$gcd(m,n) = d \Rightarrow gcd(F_{m},F_{n}) = F_{d}$$

 

증명) 

lemma) $m=nq+r \rightarrow gcd(F_{m},F_{n}) = gcd(F_{r},F_{n})$

p.f)

 $$gcd(F_{m},F_{n}) = gcd(F_{nq+r},F_{n}) = gcd(F_{nq-1}F{r},F_{nq}F{r+1},F_{n})$$

 $F_{n}\space |\space F_{nq}$이므로

 $$gcd(F_{m},F_{n}) = gcd(F_{nq-1}F_{r},F_{n})$$

 정리 5에서 $F_{nq-1}$과 $F_{nq}$이 서로소이므로 $F_{nq-1}$과 $F_{n}$도 서로소이다.

 $$\therefore gcd(F_{m},F_{n}) = gcd(F_{r},F_{n})$$

 

 lemma에서 피보나치 수열의 아래첨자끼리 유클리드 알고리즘을 만족시킨다는 것을 증명했으므로 정리 6이 쉽게 증명된다.

 

 

정리 7.

$$\sum_{k=1}^n F_{k} = F_{n+2} -1$$

 

증명)

$$F_{1} = F_{3} - F_{2}$$

 

$$F_{2} = F_{4} - F_{3}$$

 

$$F_{3} = F_{5} - F_{4}$$

 

$$.$$

$$.$$

$$.$$

 

$$F_{n} = F_{n+2} - F_{n+1}$$

 

$$\Rightarrow \sum_{k=1}^n F_{k} = F_{n+2} - F_{2} = F_{n+2} - 1$$

 

 

정리 8.

$$\sum_{k=1}^n {F_{k}}^2 = F_{n}F_{n+1}$$

 

증명)

$${F_{1}}^2 = F_{1}F_{2}$$

 

$${F_{2}}^2 = F_{2}(F_{3}-F_{1}) = F_{2}F_{3} - F_{1}F_{2}$$

 

$${F_{3}}^2 = F_{3}(F_{4}-F_{2}) = F_{3}F_{4}-F_{3}F_{2}$$

 

$$.$$

$$.$$

$$.$$

 

$${F_{n}}^2 = F_{n}(F_{n+1}-F_{n-1})=F_{n}F_{n+1}-F_{n}F_{n-1}$$

 

$$\Rightarrow \sum_{k=1}^n F_{k} = F_{n}F_{n+1}$$

 

 

정리 9.

$$\forall n\in \mathbb{N} \geq 2,\space {F_{n}}^2 - F_{n+1}F_{n-1} = (-1)^{n-1}$$

 

증명)

$n$에 대한 수학적 귀납법

(1) $n=2\Rightarrow F_{2}^2 - F_{3}F_{1} = 1 - 2\times 1 = -1^1$

 

(2) $n=k$일 때 성립 가정

 

(3) $n=k+1$일 때

$$F_{k+1}^2 -F_{k+2}F_{k}=F_{k+1}(F_{k}+F_{k-1}) - F_{k+2}F_{k}$$

$$= F_{k}(F_{k+1}-F_{k+2})+F_{k+1}F_{k-1} = -(F_{k}^2 -F_{k+1}F_{k-1}) = (-1)^{k}$$

 

추가적인 성질

1) 임의의 자연수를 항상 연속하지 않은 피보나치 수들의 합으로 표현 가능하며 그 방법이 유일하다. ->제켄도르프 표현

2) 임의의 자연수 $m$에 대해 피보나치 수열이 $(mod\space m)$에서 주기를 가진다. -> 피사노 주기

m에 대한 피사노 주기를 $P(m)$이라 하자.
$\circ\space m>2\rightarrow 2\space|\space P(m)$
$\circ\space \forall n\in 2\mathbb{N},n > 2,\space \exists m\space s.t.\space P(m) = n$
$\circ\space P(m)\leq m^2 -1$
$\circ\space P(2^n) = 3\times 2^{n-1}$
$\circ\space P(5^n) = 4\times 5^{n}$
$\circ\space P(2\times 5^n) = 6n$
$\circ\space P(10^n) = 15\times 10^{n-1}\space\space (n\leq 2)$