피보나치 수열

피보나치 수열(Fibonacci Sequence)은 첫 번째 항과 두 번째 항이 1이며 그 뒤의 항은 바로 앞 두 항의 합인 수열이다. 이탈리아의 수학자인 레오나르도 피보나치(Leonardo Fibonacci)의 이름을 딴 수열이다. 피보나치 수열은 {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...} 와 같이 뒤로 갈수록 급격히 증가한다.

개요

피보나치 수열은 첫 번째 항과 두 번째 항이 1이며 그 뒤의 항은 바로 앞 두 항의 합인 수열이다. 이 수열의 항을 피보나치 수(Fibonacci Number)라고 부른다. 편의상 0을 0번째 항으로 놓기도 한다.

• 1항부터 시작할 경우 다음과 같이 정의된다.

$F_{1}=F_{2}=1$
$F_{n}=F_{n-1}+F_{n-2}\qquad (n\in \{3,4,\dots \})$

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 

• 0항부터 시작할 경우 다음과 같이 정의된다.

$F_{0}=0$
$F_{1}=1$
$F_{n}=F_{n-1}+F_{n-2}\qquad (n\in \{2,3,4,\dots \})$

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 

역사

최초의 피보나치 수열은 기원전 450년 인도의 수학자 핑갈라가 쓴 책에서 이와 같은 수열이 최초 언급되었다. 이후 이탈리아의 수학자인 레오나르도 피보나치(Leonardo Fibonacci)가 1202년 저서인 '산반서'라는 책에서 '토끼의 번식 증가량'을 언급하며 연구하였다.

• 첫 달에 새로 태어난 토끼는 한 쌍만이 존재한다.
• 두 달 이상 된 토끼는 번식이 가능하다.
• 번식이 가능한 토끼 한 쌍은 매달 새끼 한 쌍을 낳는다.
• 이 때 토끼는 죽지 않는다.

첫 달에는 새로 태어난 토끼 한 쌍이 있고, 첫 달에는 번식할 수 없어 두 번째 달에는 그대로 토끼 한 쌍, 세 번째 달부터는 이 토끼 한 쌍이 새끼를 낳게 되어 토끼가 2쌍이 되고, 네 번째 달에는 3쌍, 다섯 번째 달에는 5쌍이 된다. 이때 n번째 달에 a쌍의 토끼가 있었고, 다음 n+1번째 달에는 새로 태어난 토끼를 포함해 b쌍이 있었다고 하면 그다음 n+2번째 달에는 a+b 쌍의 토끼가 있게 된다. 이는 n번째 달에 살아있던 토끼는 충분한 나이가 되어 새끼를 낳을 수 있지만, 바로 전 달인 n+1번째 달에 막 태어난 토끼는 아직 새끼를 낳을 수 없기 때문이다.

실제 피보나치 수열은 예전부터 알려져 있었으나 피보나치 수의 생성 함수는 완전히 정리되기까지 오랜 시간이 걸렸다. 1765년 레온하르트 오일러가 최초로 이 생성함수를 정리하여 발표했었고 이후 1848년 자크 비네가 이 생성함수를 재발견하여 발표했고 결국 피보나치 수의 생성함수는 비네의 식이라고 불렸다.

항등식

• 피보나치 수의 일반항은 다음과 같다.

$F_{n}={\frac {\varphi ^{n}-(1-\varphi )^{n}}{\sqrt {5}}}={\frac {1}{\sqrt {5}}}\left(\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right)={\frac {(1+{\sqrt {5}})^{n}-(1-{\sqrt {5}})^{n}}{2^{n}{\sqrt {5}}}}$

여기서 $\varphi$는 황금비이며, ${\sqrt {5}}$는 5의 제곱근이다. 이를 비네 공식(Binet's formula)이라고 한다.

• 카시니 항등식(Cassini's identity)

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

• 도가뉴 항등식(d'Ocagne's identity)

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

• 다음과 같은 항등식이 성립한다.

$\varphi ^{n}=F_{n}\varphi +F_{n-1}$

• '음의 정수', 이 경우, 비네 공식이 여전히 성립한다.

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

0, 1, -1, 2, -3, 5, -8, 13, -21, 34, -55, 89, -144, 233, -377, 610, -987, ...

급수 공식

• 피보나치 수의 합

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

• 피보나치 수의 교대 합

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

• 피보나치 수의 제곱 합

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

• 피보나치 수의 세제곱 합

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

• 피보나치 수의 홀수 째 항의 합

$\sum _{k=1}^{n}F_{2k-1}=F_{2n}$

• 피보나치 수의 짝수 째 항의 합

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

• 피보나치 수의 3의 배수 째 항의 합

$\sum _{k=0}^{n}F_{3k}={\frac {F_{3n+2}-1}{2}}$

• 피보나치 수의 역수의 합은 수렴한다.

${\begin{aligned}\sum _{n=1}^{\infty }{\frac {1}{F_{n}}}&=3+\sum _{n=1}^{\infty }{\frac {(-1)^{n}}{F_{n}F_{n+1}F_{n+2}}}\\&={\frac {41}{12}}-{\frac {3}{2}}\sum _{n=1}^{\infty }{\frac {1}{F_{n}F_{n+1}F_{n+2}F_{n+3}F_{n+4}}}\\&={\frac {11749}{5280}}-{\frac {60}{11}}\sum _{n=1}^{\infty }{\frac {(-1)^{n}}{F_{n}F_{n+1}F_{n+2}F_{n+3}F_{n+4}F_{n+5}F_{n+6}}}\end{aligned}}$

생성 함수

• 피보나치 수의 생성 함수

$\sum _{n=0}^{\infty }F_{n}x^{n}={\frac {x}{1-x-x^{2}}}$

• 피보나치 수의 역수의 생성 함수

${\begin{aligned}\sum _{n=1}^{\infty }{\frac {1}{F_{n}}}x^{n}&=\sum _{n=1}^{\infty }{\frac {x^{n}{\sqrt {5}}}{\varphi ^{n}}}+\sum _{n=1}^{\infty }(-1)^{n}{\frac {x^{n}}{F_{n}\varphi ^{2n}}}\\&={\frac {x{\sqrt {5}}}{\varphi -x}}+\sum _{n=1}^{\infty }(-1)^{n}{\frac {x^{n}}{F_{n}(F_{2n}\varphi +F_{2n-1})}}\\&={\frac {x{\sqrt {5}}}{\varphi -x}}-{\frac {x{\sqrt {5}}}{\varphi ^{3}+x}}+\sum _{n=1}^{\infty }{\frac {x^{n}}{F_{n}\varphi ^{4n}}}\\&={\frac {x{\sqrt {5}}}{\varphi -x}}-{\frac {x{\sqrt {5}}}{\varphi ^{3}+x}}+{\frac {x{\sqrt {5}}}{\varphi ^{5}-x}}+\sum _{n=1}^{\infty }(-1)^{n}{\frac {x^{n}}{F_{n}\varphi ^{6n}}}\end{aligned}}$

점근 공식

• 이웃하는 피보나치 수의 비는 황금비로 수렴

$\lim _{n\to \infty }{\frac {F_{n+1}}{F_{n}}}=\varphi$

• 다음과 같은 부등식이 성립

${\frac {\varphi ^{n-{\frac {1}{n}}}}{\sqrt {5}}}\leq F_{n}\leq {\frac {\varphi ^{n+{\frac {1}{n}}}}{\sqrt {5}}}$

수론적 성질

피보나치 수열은 서로 인접한 항끼리 정수의 서로소(1 이외에 공약수를 갖지 않는 둘 이상의 양의 정수)이다. 이는 귀류법으로 증명할 수 있다.

예시

피보나치 수열은 기본적으로 수학뿐만 아니라 자연에서 생물학적 패턴, 컴퓨터 응용 프로그램, 경제학 등 다양한 분야에서 사용되고 있다.

• 자연 : 생물학적 패턴에 자주 등장한다. 솔방울의 모양, 꽃씨의 배열, 꽃잎의 수, 나선형 엽상식물, 꿀벌의 가계도 등.
• 음악 : 조셉 쉴린저(1895-1943)는 멜로디를 피보나치 수열에 맞춰 간격을 두는 작곡 체계를 개발했다.
• 경제 : 엘리어트 파동과 같은 주식, 암호화폐 시장 차트에서 기술적 분석에 사용된다.
• 컴퓨터 : 난수 생성기, 스크럼 방법론을 사용하는 소프트웨어 개발, 네트워크 토폴로지를 위한 병렬 알고리즘 등.

참고자료

• 〈피보나치 수열〉, 《나무위키》
• 〈피보나치 수〉, 《위키백과》
• 〈Fibonacci number〉, 《wikipedia》

같이 보기

• 엘리어트 파동

이 피보나치 수열 문서는 암호화폐 거래에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.

암호화폐 : 암호화폐 종류, 암호화폐 종류(국가별), 암호화폐 종류(가나다), 암호화폐 분류, 암호화폐 거래소, 암호화폐 거래 □■⊕, 암호화폐 지갑, 암호화폐 역사, 채굴기, 채굴업체, 채굴지역 캔들 꼬리 • 망치형 • 몸통 • 비석형 • 시가 • 십자형(도지형) • 아래꼬리 • 양봉 • 역망치형 • 위꼬리 • 음봉 • 일자형 • 잠자리형 • 장대양봉 • 장대음봉 • 종가 • 최고가 • 최저가 • 캔들 차트 MACD • 고점 • 골든크로스 • 과매도 • 과매수 • 구름대 • 그래프 • 기준선 • 눌림목 • 다이버전스 • 데드크로스 • 바닥 • 보합 • 보합세 • 볼린저밴드 • 상대강도지수(RSI) • 상승 • 상승세 • 상한선 • 선행스팬1 • 선행스팬2 • 스토캐스틱 • 이동평균선 • 일목균형표 • 저점 • 저항선 • 전고점 • 전저점 • 전환선 • 지지선 • 차트 • 최고점 • 최저점 • 하락 • 하락세 • 하한선 • 후행스팬 패턴 N자형 • V자형 • 계단형 • 덤핑 • 데드캣 • 머리어깨형 • 박스권(횡보) • 베어트랩 • 불트랩 • 삼각수렴 • 쌍바닥(W자형) • 쌍봉(M자형) • 엘리어트 파동 • 역N자형 • 역V자형 • 역머리어깨형 • 펌프앤덤프 • 펌핑 • 플래시 크래시 • 피날레 • 피보나치 수열 • 하이먼 민스키 모델 거래 가상자산 사업자 • 가상자산 서비스 제공자 • 거래량 • 고객신원확인(KYC) • 고빈도거래(HFT) • 공매도 • 공매수 • 교차상장 • 극초단타 • 김프판 • 단타 • 달러마켓 • 데이트레이딩 • 덱스(DEX, 탈중앙화 거래소) • 도둑상장 • 도지마켓 • 디커플링 • 디픽스 • 락업 • 런치패드 • 레버리지 • 리딩 • 리딩방 • 마진거래 • 마진콜 • 매도 • 매도벽 • 매매 • 매수 • 매수벽 • 매집 • 바이낸스 런치패드 • 배칭거래 • 벌집계좌 • 벽 • 베어마켓 • 분할매도 • 분할매매 • 분할매수 • 불마켓 • 블록딜 • 비봇 • 비티씨마켓 • 빅맥지수 • 상승장 • 상장 • 상장호재 • 선물거래 • 손절 • 순환매 • 스왑 • 스윙트레이딩 • 스프레드 • 시가총액 • 시그널 • 시드머니 • 아비트리지 • 악재 • 알고리즘 트레이딩 • 암호화폐 거래 • 에스크로 • 에어드랍 • 엔화마켓 • 오더북 • 올인 • 왝더독 • 원화마켓 • 월렛인베스터 • 위안화마켓 • 유로마켓 • 이더마켓 • 이티피 • 익절 • 일물일가의 법칙 • 자금세탁방지(AML) • 자동거래 • 자전거래 • 장세 • 재료 • 중앙화 거래소(CEX) • 중장기투자 • 차익거래(재정거래) • 초단타(스캘핑) • 커플링 • 코봇 • 코스트 애버리징(물타기) • 코인마켓캡 • 코인코덱스 • 타이밍 • 테더마켓 • 트레이더 • 트레이딩 • 트레이딩뷰 • 패닉셀(투매) • 포모 • 포지션 • 프로그램 매매 • 픽 • 하락장 • 하트넘버 • 현물거래 • 호재 • 홈트레이딩 주문 FAS • FOK • GTC • IOC • MIT • 가격지정주문 • 동시호가 • 매도스톱리밋주문 • 매수스톱리밋주문 • 매도역지정가주문 • 매수역지정가주문 • 메이커 • 메이커 피 • 시장가주문 • 스케일오더 • 지정가주문 • 조건부주문 • 조건부지정가주문 • 장시작 동시호가 • 장마감 동시호가 • 추적손절매주문 • 추적스톱리밋주문 • 최유리지정가주문 • 최우선지정가주문 • 테이커 • 테이커 피 • 호가 • 호가 스프레드 장외거래 리퍼블릭 프로토콜 • 아토믹스왑 • 장외거래(OTC) • 체인저 투자 ATO • ETF • IBO • ICCO • ICO • IEO • IWO • RCPS • SIEO • STO • TGE • 가치투자 • 공모 • 공모펀드 • 다단계사기 • 드래그얼롱 • 로보어드바이저 • 리버스 ICO • 모태펀드 • 뮤추얼펀드 • 벤처캐피탈 • 보통주 • 분산투자 • 사기 • 사모 • 사모펀드 • 상환전환우선주 • 선투자 • 소프트캡 • 액셀러레이터 • 액셀러레이팅 • 어드바이저 • 에스에이에프티(SAFT) • 엔젤투자자 • 우선주 • 월스트리트 • 유한책임투자자(LP) • 인큐베이터 • 인큐베이팅 • 장기투자 • 전환사채 • 조각투자 • 주식 • 질라 • 집중투자 • 콜옵션 • 크라우드세일 • 크라우드펀딩 • 크립토펀드 • 태그얼롱 • 토큰넥스트 • 투기 • 투자 • 튤립버블 • 퍼블릭세일 • 펀드 • 펀딩 • 컨설팅 • 펀더멘탈 • 포트폴리오 • 폰지사기 • 풋옵션 • 프라이빗세일 • 프리세일 • 피라미드사기 • 하드캡 • 하위테스트 • 헤지 • 헤지펀드 • 히든캡 코인 속어 가즈아 • 김치 프리미엄(김프) • 대마불사 • 떡락 • 떡상 • 몰빵 • 비들러 • 존버 • 줍줍 • 코린이 • 펌핑 • 흑두루미 • 흑우 • 흡성대법 드라마 펌핑타임 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반