수학/대수학

피보나치수열의 성질

피보나치수열은 초등학생도 흔히 접하는 매우 간단한 형태의 수열이다. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ... 그런데 이 간단한 수열에도 파고들면 수많은 수학적 의미를 찾을 수 있다. 한번 그 의미를 알아보자. 참고로 $F_n$이 의미하는 바는 $n$번째 피보나치 수로 $F_1=1$, $F_2=1$, $F_3=2$이다. 홀짝성(기우성) 아주 간단한 성질이다. 피보나치수열의 원소는 홀수, 홀수, 짝수, 그리고 반복을 이룬다. 이가 성립하는 이유는 다음과 같다. $F_1=1$ (홀수), $F_2=1$ (홀수)이다. 홀수+홀수=짝수이므로 다음 $F_3$은 짝수이고 $F_4$는 홀수+짝수=홀수가 되어 홀수 $F_5$는 짝수+홀수=홀수가 되어 홀수 $F_6$는 홀수+홀수=짝..

피보나치수열의 일반항

피보나치수열은 초등학생도 흔히 접하는 매우 간단한 형태의 수열이다. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ... 피보나치수열을 수학적으로 쓰면 다음과 같다. 초기 조건: $F_1=1$, $F_2=1$ 점화식: $F_n=F_{n-1}+F_{n-2}$($n\geq 3$) 이 정도면 피보나치수열을 사용하는 데는 부족함이 없지만 큰 피보나치수, 가령 $F_{50}$을 계산하기엔 노가다가 심하다. 따라서 이번에는 피보나치수열의 일반항을 구해볼 것이다. 이 글을 읽기 전 동차점화식의 일반항을 먼저 읽어주세요! 이 글에서는 해당 개념을 응용할 것입니다. 항 3개를 사용하는 동차점화식의 일반형은 다음과 같다. $a_n=pa_{n-1}+qa_{n-2}$ 따라서 피보나치수열은 여기서 ..

동차점화식의 일반항

개요 수열에서 점화식이란 이전항을 이용해 다음 항을 알아내는 식이다. 예를 들어 어떤 수열 $a$에 대해 다음 식은 모두 점화식이다. $a_{n+1}=2a_n$ $a_{n+1}=a_n+4$ $a_{n+1}=3a_n+4$ $a_{n}=2a_{n-1}+3a_{n-2}$ 이 중 식 1, 2, 3 꼴의 점화식에서 일반항을 유도하는 방법은 이미 이 글에서 다루었다. 이번 글에서는 4번 형식의 점화식에서 일반항을 구하는 방법에 대해 알아보자. 동차점화식과 비동차점화식 점화식은 꼴에 따라 2가지 형태로 나눌 수 있다. 1번 식과 같은 꼴의 점화식을 "동차점화식"이라고 하고 2번 식과 같은 꼴의 점화식을 비동차점화식이라고 한다. $a_n=k_1 a_{n-1}+k_2 a_{n-2}+\cdots$$+k_m a_{n-m}$..

원주율의 근사방법

원주율이란, 원에서 지름과 반지름의 길이비로 정의된다. 모든 원에서 이 값은 일정하며, 따라서 상수이다. 원주율이 무리수라는 증명은 이미 존재하는데, 이는 곧 원주율은 원을 하나 그리고, 원주와 반지름의 길이를 실측해서 나타낼 수 없음을 의미한다. 따라서 여타 다른 무리수, 이를테면 $\sqrt{2}$와 같이 $\pi$도 근사를 통해 그 값을 구해야 한다. #include #include #include #include #define BATCH 999999 #define WILL_TRY 1400000 #define SQUARE 14000 #define RND(M) rand()%M #define DOUBLE_SIZE sizeof(double) clock_t start_p, end_p; void approx..

유클리드 호제법과 디오판토스 방정식

일반적으로 두 자연수의 최대공약수를 구하기 위해 우리는 두 수를 소인수 분해한다. 예를 들어 두 자연수 $a$와 $b$가 있고 이들을 소인수 분해한 것이 $a=pq^2$이고 $b=p^2q$인 경우 두 수의 최대공약수 $g=pq$이다. 이때 $g=(a,b)=pq$로 쓸 수 있다. 이 방법은 분명 효과적이지만 두 수가 매우 큰 경우 그리 효과적인 방법은 아니다. 이 글에서는 두 수의 최대공약수를 구하는 다른 방법인 유클리드 호제법에 대해 다룬다. 유클리드 호제법 유클리드 호제법은 다음과 같은 정리이다. 두 자연수 $a$와 $b$가 있을 때 $a=bq+r$ ($q,r \in \mathbb{Z}$)라면 $(a,b)=(b,r)$이다. 이에 대한 증명은 다음과 같다. $(a,b)=G$라고 하고 $a=GA$, $b=..

일반항과 점화식

< 등비수열과 등차수열 수열에는 일반항과 점화식이라는 개념이 있다. 이전 글을 보았으면 알겠지만 일반항은 수열의 항의 값을 항의 번호로 구하는 일반적인 식이며, 점화식은 구하고자 하는 항의 이전항들로 항의 값을 구하는 식이다. 그 글에서는 일반항과 점화식에 대해 자세히 알아본다. 등차수열과 등비수열의 일반항과 점화식 한 줄로 정리하자면 다음과 같다. ($a$: 일반항, $n$: 항의 번호, $d$: 공차, $r$: 공비) 일반항 점화식 등차수열 $S_n=a+(n-1)d$ $S_n=S_{n-1}+d$ 등비수열 $S_n=ar^{n-1}$ $S_n=rS_{n-1}$ 이미 이전 글에서 유도에 대해 설명했지만 이번에는 그냥 규칙을 찾는 것이 아니라 수학적으로 접근해보겠다. 점화식은 수열의 정의에서 당연하게 유도되..

등차수열과 등비수열

일반항과 점화식 > 이번 글에서는 수열 시리즈를 시작하며 가장 기본적인 등차수열, 등비수열에 대해 다룰 것이다 수열의 점화식과 일반항 수열이란 수의 나열이다. 예를 들면 $1, 2, 3, 4, 5 \cdots$는 자연수의 수열이며 $2, 3, 5, 7, 11, 13 ,17 \cdots$는 소수의 수열이다. 수열에는 항이라는 것이 있다. 항이란 수열의 몇 번째 수인지를 묻는 것이다. 예를 들어 수열 ${1, 2, 4, 8, 16, 32 \cdots}$의 제1항은 1, 제2항은 2, 제3항은 4이다. 수학적으로 쓰자면 수열 $a$의 $n$번째 항은 $a_n$으로 쓴다. 첫항의 경우 $a$로 쓸 수도 있다. 일반적으로 수열은 아무 의미없는 수의 나열이 아니라 일정한 규칙을 가지고 수를 나열한다. 그렇기 때문에..