피보나치 수열 심화과정3 -모든 자연수는 피보나치 수의 합으로 유일하게 분해할 수 있다(제켄도르프의 정리)-

1. 피보나치 수 피보나치 수열 $F_{n}$을 다음과 같이 정의하고, $F_{n}$을 피보나치 수라고 하자. $F_{0} = 0, F_{1} = F_{2} = 1$, $F_{n} = F_{n-1} + F_{n-2}, n \geq 2$ 두 피보나치 수 $F_{m}$과 $F_{n}$에 대하여 m = n+1 혹은 m = n-1이면 두 피보나치 수가 인접하다고 한다. 즉, $F_{n+1}$과 $F_{n}$은 인접한 피보나치 수이며 $F_{n}$과 $F_{n-1}$은 인접한 피보나치 수이다. 2. 제켄도르프의 정리(Zeckendorf's theorem) "모든 자연수는 인접하지 않은 피보나치 수($F_{0}$, $F_{1}$을 제외한)들의 합으로 표현할 수 있으며, 그 표현 방법이 유일하다" 예를 들어 n = ..

• format_list_bulleted 정수론
• · 2023. 5. 23.
• textsms

피보나치 수열 심화과정2 - 자연수 n이 피보나치 수인지 바로 알 수 있을까? -

1. 주어진 수가 피보나치 수인지 바로 알 수 있을까? 피보나치 수는 $F_{1} = F_{2} = 1$이고 $F_{i} = F_{i-1} + F_{i-2}$을 만족하는 $F_{i}$이다. 반대로 어떤 자연수 n이 주어질때 그 수가 피보나치 수열 $F_{i}$의 하나인지 바로 판단할 수 있을까? 2. 행렬을 이용해 피보나치 수를 만드는 방법 일반적으로는 $F_{1} = F_{2} = 1$부터 차근차근 만들어나가는 것이다. 그러면 언젠가 주어진 자연수 n 근처에 도달할 것이고, n에 정확히 도달하면 n은 피보나치 수이고 n을 넘어가면 n은 피보나치 수가 아니다. 행렬을 이용한 피보나치 수 생성하는 방법이 O(logN)으로 가장 빠르면서 유의미한데, 이정도만 해도 사실 상당히 빠르다 https://deepd..

• format_list_bulleted 정수론
• · 2023. 5. 23.
• textsms

귀류법과 수학적 귀납법 정확히 알기

1. 증명 19세기 말부터 증명이 무엇인지 많은 연구가 있었다 증명은 글로 쓰는 것이 아니라 '정확한 명제로 표현할 수 있는 것'이라는 것이 확립된 상태 보통 정확한 명제식으로 쓰지는 않지만 근본적으로는 명제식으로 바꿀 수 있는 것이 증명이다 증명에 대한 수많은 오해는 p ↔ q 와 p → q를 혼동하는 것에서 시작함 2. 당구공 paradox '모든 당구공은 색이 같다'에 대한 증명 당연히 색이 같을리 없지만 논리적으로 증명하고자 함 ------------------------------------------------------------------------------------------------------------ 수학적 귀납법) 모든 자연수 n에 대해 명제 P(n)이 참이라는 것을 증명하기..

• format_list_bulleted 프로그래밍 개론
• · 2022. 7. 13.
• textsms