제가 어제 풀었던 문제 중 피보나치 수 6라는 문제가 있었는데요. 제가 발견한 그 규칙이 사실 어떤 공식으로 이미 있더라구요!?!

역시 있을 줄 알았습니다. 찾아보길 잘했어요.

혹시나 더욱 많은 공식을 원하시다면 여기에서 확인 할 수 있어요! 디게 재밌으니 한번 다들 작성해보는 것도 괜찮을 것 같네요!

일단 사실 도가뉴 항등식이라는 것을 배우려고 했으나 다른 것들도 재미있게 해볼 수 있을 것 같아서 한번 다 다뤄보려구요!

1. 카시니 항등식 (Cassini’s Identity)#

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

증명#

기본 검증표#

n	계산식	단계별 계산	최종 결과	$(- 1)^{n}$
3	F₄F₂ - F₃²	3 × 1 - 2² = 3 - 4	-1	(-1)³ = -1
4	F₅F₃ - F₄²	5 × 2 - 3² = 10 - 9	1	(-1)⁴ = 1

확장된 검증표#

n	$F_{n - 1}$	$F_{n}$	$F_{n + 1}$	$F_{n + 1} F_{n - 1} - F_{n}^{2}$	$(- 1)^{n}$
1	0	1	1	1 × 0 - 1² = -1	(-1)¹ = -1
2	1	1	2	2 × 1 - 1² = 1	(-1)² = 1
3	1	2	3	3 × 1 - 2² = -1	(-1)³ = -1
4	2	3	5	5 × 2 - 3² = 1	(-1)⁴ = 1
5	3	5	8	8 × 3 - 5² = -1	(-1)⁵ = -1

F_{n + 1} F_{n} F_{n} F_{n - 1} = 1110^{n}

d e t F_{n + 1} F_{n} F_{n} F_{n - 1} = F_{n + 1} F_{n - 1} - F_{n}^{2} = (- 1)^{n}

행렬식을 계산하는 것으로도 항등식을 증명할 수 있어요

깨알 상식
det은 2×2 행렬의 행렬식은 대각선 곱의 차이로 계산

2. 도가뉴 항등식 (d’Ocagne’s Identity)#

저는 일단 오늘 포스팅의 포커스를 도가뉴에 맞추기 때문에 더욱 좀 자세히 가져왔습니다.

F_{m + n} = F_{m} F_{n + 1} + F_{m - 1} F_{n}

2.1. 행렬을 이용한 증명#

[F_{k + 1} F_{k} F_{k} F_{k - 1}] = [1110]^{k}

이제 k = m+n일 때를 생각해보면

[F_{m + n + 1} F_{m + n} F_{m + n} F_{m + n - 1}] = [1110]^{m + n}

여기서 중요한 성질은 행렬의 거듭제곱 법칙입니다요

[1110]^{m + n} = [1110]^{m} [1110]^{n} = [F_{m + 1} F_{m} F_{m} F_{m - 1}] [F_{n + 1} F_{n} F_{n} F_{n - 1}]

그래서 이제 각각의 행렬을 보면 아래오 같습니다.

[1110]^{m} = [F_{m + 1} F_{m} F_{m} F_{m - 1}]

[1110]^{n} = [F_{n + 1} F_{n} F_{n} F_{n - 1}]

이 두 행렬을 곱하면

[F_{m + 1} F_{n + 1} + F_{m} F_{n} F_{m} F_{n + 1} + F_{m - 1} F_{n} F_{m + 1} F_{n} + F_{m} F_{n - 1} F_{m} F_{n} + F_{m - 1} F_{n - 1}] = [F_{m + n + 1} F_{m + n} F_{m + n} F_{m + n - 1}]

결과적으로는 아래의 결과를 확인할 수 있어요!

F_{m + n} = F_{m} F_{n + 1} + F_{m - 1} F_{n}

2.2. 수학적 귀납법을 이용한 증명#

고정된 m에 대해 n에 대한 귀납법을 사용할 수도 있습니다.

먼저, 귀납법의 기본 단계(n=1)를 살펴봅시다

좌변: $F_{m + 1} = F_{m} + F_{m - 1}$ (피보나치 수열의 정의)
우변: $F_{m - 1} F_{1} + F_{m} F_{2} = F_{m - 1} + F_{m}$ (F₁ = F₂ = 1이므로)

다음으로, 귀납 가정(n=k)을 설정하고 봅시다

$F_{m + k} = F_{m - 1} F_{k} + F_{m} F_{k + 1}$

마지막으로, 귀납 단계(n=k+1)를 증명할 수 있어요

$F_{m + k + 1} = F_{m + k} + F_{m + k - 1}$ (피보나치 수열의 정의)

귀납 단계의 완전한 증명을 위해 더 자세히 전개 해봅시다

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

이렇게 귀납법의 모든 단계가 성립함을 보였으므로, 도가뉴 항등식이 모든 자연수 n에 대해 성립함이 증명된 겁니다. 수식과 증명 과정을 함께 살펴보면, 이 항등식이 피보나치 수열의 재귀적 성질을 어떻게 활용하는지 볼 수 있습니다. 굉장히 흥미로운디용 하ㅏ하하ㅏ하하

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

3. 음의 정수 확장#

일반적으로 피보나치 수열은 양의 정수 인덱스에 대해 정의됩니다

$F_{n} = F_{n - 1} + F_{n - 2}, where F_{0} = 0, F_{1} = 1, F_{2} = 1$

초기값
where은 초기값 설정

하지만 이 점화식을 음의 정수 인덱스로도 확장할 수 있습니다. 음의 인덱스를 가진 피보나치 수는 아래의 공식을 따릅니다

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

이것이 어떻게 작동하는지 이해하기 위해, 피보나치 수열의 점화식을 역방향으로 생각해봅시다.

기존 점화식을 변형해보면

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

이를 이용해 F₀부터 시작하여 음의 인덱스의 값들을 계산할 수 있습니다

F₀ = 0
F₁ = 1
F₋₁ = F₁ - F₀ = 1 - 0 = 1
F₋₂ = F₀ - F₋₁ = 0 - 1 = -1
F₋₃ = F₋₁ - F₋₂ = 1 - (-1) = 2
F₋₄ = F₋₂ - F₋₃ = -1 - 2 = -3
F₋₅ = F₋₃ - F₋₄ = 2 - (-3) = 5

이렇게 확장된 전체 수열을 나열하면

$..., 8, - 5, 3, - 2, 1, - 1, 0, 1, 1, 2, 3, 5, 8, ...$

타란!

4. 급수 공식들#

4.1. 합 공식#

처음 n개의 피보나치 수를 더한 값

k = 0 \sum n F_{k} = F_{n + 2} - 1

4.2. 교대합 공식#

피보나치 수들을 번갈아가며 더하고 빼는 경우의 합

k = 0 \sum n (- 1)^{k + 1} F_{k} = (- 1)^{n + 1} F_{n - 1} + 1

4.3. 제곱합 공식#

피보나치 수들의 제곱의 합

k = 0 \sum n F_{k}^{2} = F_{n} F_{n + 1}

4.4. 세제곱합 공식#

피보나치 수들 세제곱의 합

k = 0 \sum n F_{k}^{3} = \frac{F _{3 n + 2} + ( - 1 ) ^{n + 1} 6 F _{n - 1} + 5}{10}

4.5. 참고할만한 공식#

기본적 공식
홀수번째 항들의 합#
$k = 1 \sum n F_{2 k - 1} = F_{2 n}$
짝수번째 항들의 합#
$k = 0 \sum n F_{2 k} = F_{2 n + 1} - 1$
3의 배수번째 항들의 합#
$k = 0 \sum n F_{3 k} = \frac{F _{3 n + 2} - 1}{2}$
그 외의 공식도 있고, 특성도 있는데 그건 여기를 참고해서 보시면 되겠습니다.

5. 그 외 기억해 둘만한 성질들#

5.1. 비네 공식 (Binet’s Formula)#

무리수인 √5와 황금비(φ)를 사용하여 항상 정수인 피보나치 수를 정확히 계산

깨알 상식
황금비에 대해서 먼저 알아야 되더라구요!
φ = (1 + √5) / 2 ≈ 1.618034
수식에서는 이렇게 정의하고 있는데요 φ² = φ + 1 이런 것도 만족한다는 것이지요 허헣
φ¹ = φ
φ² = φ + 1
φ³ = φ² × φ = (φ + 1)φ = φ² + φ = (φ + 1) + φ = 2φ + 1
φ⁴ = φ³ × φ = (2φ + 1)φ = 2φ² + φ = 2(φ + 1) + φ = 3φ + 2
그래서 이렇게 풀이할 수 있습니다.

정의를 먼저 해보겠습니다

φ = (1 + √5) / 2 ≈ 1.618034 -> 황금비

ψ = -1/φ ≈ -0.618034 -> 반황금비

φⁿ은 항상 aφ + b 형태
ψⁿ도 같은 방식으로 cφ + d 형태
φ - ψ = √5
그래서 (φⁿ - ψⁿ) / √5는 항상 정수

F_{n} = \frac{ϕ ^{n} - ϕ ^{n}}{5} = \frac{1}{5} \frac{1 + 5}{2}^{n} - \frac{1 - 5}{2}^{n}

솔직히 이거 보면서 좀 놀라긴 했슴둥

재밌네요 언제나 수학을 배우다 보면 진짜 흥미롭고 신기한 것들 투성이네요

5.2. 서로소 성질#

연속된 피보나치 수들은 항상 서로소

g c d (F_{n}, F_{n + 1}) = 1

5.3. 황금비, 극한#

피보나치 수열의 연속된 두 항의 비는 황금비(φ)에 수렴

n \to \infty lim \frac{F _{n + 1}}{F _{n}} = ϕ = \frac{1 + 5}{2} \approx 1.618034

정말 놀랍게도 이런 공식들이 있다는데 신기하네요!!

코딩, ps 하다보면 정말 많이 보게되는 수열 피보나치 수열인데 이런 것들을 모르고 있었다는 것도 좀 웃기긴 합니다 ㅋㅋㅌㅎㅋㅎ

그 외로 더욱 자세한 설명은 나중에 알고리즘 구현 때 다 깊이 다뤄볼게용.. 저도 이게 지금 정리한걸 풀어쓰고 있기도하고, 다 잘 알고 있는게 아니여서 더욱 자세히 쓰다가는 오류를 범할 것 같아 여기까지 마무리하겠스빈다.

나중에는 오일러 피 함수와 gcd 어떻게 효율적으로 다 할 수 있는지에 대해서 다뤄봐도 좋을 것 같네요!!

아 그리고 여기에 나오는 공식으로 이 문제를 풀 수 있어요! 한번 다들 try try~~

1. 카시니 항등식 (Cassini’s Identity)#

증명#

기본 검증표#

확장된 검증표#

2. 도가뉴 항등식 (d’Ocagne’s Identity)#

2.1. 행렬을 이용한 증명#

2.2. 수학적 귀납법을 이용한 증명#

3. 음의 정수 확장#

4. 급수 공식들#

4.1. 합 공식#

4.2. 교대합 공식#

4.3. 제곱합 공식#

4.4. 세제곱합 공식#

4.5. 참고할만한 공식#

홀수번째 항들의 합#

짝수번째 항들의 합#

3의 배수번째 항들의 합#

5. 그 외 기억해 둘만한 성질들#

5.1. 비네 공식 (Binet’s Formula)#

5.2. 서로소 성질#

5.3. 황금비, 극한#

Reference#

wiki #

1. 카시니 항등식 (Cassini’s Identity)#

증명#

기본 검증표#

확장된 검증표#

2. 도가뉴 항등식 (d’Ocagne’s Identity)#

2.1. 행렬을 이용한 증명#

2.2. 수학적 귀납법을 이용한 증명#

3. 음의 정수 확장#

4. 급수 공식들#

4.1. 합 공식#

4.2. 교대합 공식#

4.3. 제곱합 공식#

4.4. 세제곱합 공식#

4.5. 참고할만한 공식#

홀수번째 항들의 합#

짝수번째 항들의 합#

3의 배수번째 항들의 합#

5. 그 외 기억해 둘만한 성질들#

5.1. 비네 공식 (Binet’s Formula)#

5.2. 서로소 성질#

5.3. 황금비, 극한#

Reference#

wiki#

wiki #