2020년 마지막 노잼사실
게시글 주소: https://orbi.kr/00034573985
모든 자연수 n은 서로다른 피보나치 수의 합으로 나타낼 수 있다. (F_i = F_{i-1}+F_{i-2}, F_0 = 0, F_1 = 1)
n = 1,2,3,4인경우는 거의 자명. 주어진 n이 피보나치 수라면 증명할거없음. 주어진 n이 피보나치 수가 아니라고 하면, 어떤 i가 있어서 F_i<n<F_{i+1}을 만족한다. 여기서 각각의 a<n에 대해서 위의 진술이 참이라고 가정 그리고 a = n-F_i인 경우를 생각해보면, 가정에 의해서 a는 서로 다른 피보나치 수의 합으로 나타낼 수 있음. a<F_{i+1}-F_i = F_{i-1}이기 때문에 a를 표현하는 피보나치수들에는 F_{i-1}을 포함하고 있지 않음. 따라서 F_i를 포함하고있지 않음. 따라서 a를 나타내는 피보나치의 수들과 F_i의 합은 n이고 각각의 피보나치 수들은 서로 다름.
여기서 사용된 방법이 귀납법이긴한데 본래 귀납법보다는 강한 가정을 함. strong induction이라고 하고, 그래프 이론이나 이산수학에서 많이출몰함.
원래 설명안쓰는데 올해 마지막이니 씀 (그리고 몇줄안되서 씀).
해피뉴이어ㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓ
아 참고로 저 표현은 유일하다고한다. 왤까?
2021에는 꿀잼사실좀 많이 올라왔으면
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
해설까지 ㄷㄷ 평가원보다 친절하시네요
*2022 논술 유출*성지가 될 겁니다