프로베니우스의 동전 문제는, $a$원의 동전과 $b$원의 동전만으로 만들 수 없는 금액의 최댓값을 구하는 문제입니다. (이때, $a$, $b$는 자연수입니다.) 공식만 알고 있었는데, 정확한 적용 범위가 헷갈려서 아예 증명을 해봅니다. 잘못된 부분이 있다면 알려주세요 :) 표기 $\mathbb N_0:=\ $음이 아닌 정수 집합 $\mathbb N_+:=\ $양의 정수 집합 $\text{Theorem. }$ 서로소인 두 정수 $a,b\in \mathbb N_+$에 대해 $an+bm(n, m\in \mathbb N_0)$로 표현할 수 없는 최대의 정수는 $ab-a-b$이다. 보조정리 1과 보조정리 2가 참임을 보이면 theorem도 참이다. 보조정리 1. $an+bm=ab-a-b$인 $(n,m)$은 존재하..

구체수학과 koosaga님 블로그를 참고했습니다. 수학적 귀납법 정수 $n$에 관한 어떤 명제가 모든 $n\ge n_0$에 대해 참임을 증명하는 일반적인 방법이다. 이는 2가지 단계로 나뉜다. 기초(basis) 단계: $n_0$에 대한 증명 귀납(induction) 단계: $n_0,\cdots, n-1$에 대해 증명되었다는 가정 하에 $n>n_0$에 대해 증명 하노이탑 세 개의 탑에서 하노이탑 규칙에 따라 옮기는 최소 이동 횟수를 구하면 된다. 우선, 정의를 잘 하는 것이 중요하다. 책의 필자는 명명정복이라고 한다. $T_n:=$ 규칙 하에 다른 한 기둥으로 옮기는데 필요한 최소 이동 횟수 1번 기둥에서 2번 기둥으로 위쪽 $n-1$개의 원판을 옮기고, $n$번째 원판을 3번 기둥으로 옮긴 후 2번 기둥..

구체수학 일부 합을 공략할 때 유용한 일반 전략들. 일부는 점화식으로 일반항 구하는 데에도 사용 가능. 답을 추측하고 귀납법으로 증명한다 비약이 크기 때문에(우선 공식을 추측해야 하니까) 필자는 다른 안정적인 방식으로 닫힌 형식을 구하자고 이런 방법들을 소개한다. 합을 어지럽힌다 점화식으로 일반항을 구할 때 원래 "꼬리 자르기"라고 부르던 방식을, 책에서는 "섭동법"이라는 멋진 이름으로 소개한다. 등비수열의 합을 구할 떄 쓰는 방식이기도 한데, 등차수열의 합을 구할때는 잘 안 먹힌다. 그런데, 그림 가운데의 관찰을 바탕으로 한 차원 높게 잡고 구하면 구할 수 있다. 레퍼토리를 구축한다 $\square_n=\square_{n-1}+n^2;\; \square_0=0.$ $R_n=R_{n-1}+\beta+\g..