PUMaC 2011 · 数论（A 组） · 第 7 题
PUMaC 2011 — Number Theory (Division A) — Problem 7
题目详情
- [ 7 ] Let { g } be a sequence of positive integers such that g = g = 1 and the following i 0 1 i =0 recursions hold for every positive integer n : 2 2 g = g + g 2 n +1 2 n − 1 2 n − 2 2 g = 2 g g − g 2 n 2 n − 1 2 n − 2 2 n − 2 Compute the remainder when g is divided by 216. 2011
解析
- This sequence, which starts off as 1 , 1 , 1 , 2 , 3 , 5 , 21 , 34 , . . . contains many members of the Fi- ∞ bonacci sequence. However, it is not the Fibonacci sequence. If { F } is the Fibonacci se- i i =1 quence with F = F = 1, then the g sequence can be written as 1 , 1 , F , F , F , F , F , F , ... , 0 1 1 2 3 4 7 8 which suggests that g = F k and g = F k for all positive integers k . 2 k 2 k +1 2 − 1 2 We prove this by induction. Since the initial conditions ( g and g ) of the sequence are the same 0 1 n as F and F respectively, the base case is complete. Therefore, assume that g = F and 1 2 2 n 2 − 1 2 2 n g = F and consider g in addition to g . The Fibonacci identities F = F + F 2 n +1 2 2 n +2 2 n +3 2 k k k − 1 2 and F = 2 F F − F solve the inductive step. 2 k − 1 k k − 1 k − 1 For sake of completeness, we prove these identities in tandem by strong induction. For F = 2 k 2 2 F + F , we can check that the base case k = 1 is consistent with this identity ( F = 2 k k − 1 2 2 2 2 = 1 + 1 = F + F ). For F = 2 F F − F , the base case of k = 1 is verified by 2 k − 1 k k − 1 1 0 k − 1 2 F = 1 = 2(1) − 1 = 2 F F − F , as desired. Therefore, we have completed the base case for 1 1 0 0 induction. For the inductive hypothesis, assume that 2 2 2 F = F + F and F = 2 F F − F . 2 k − 2 2 k − 3 k − 1 k − 2 k − 1 k − 2 k − 2 3 Note that 2 2 2 2 F F − F = 2( F + F ) F − F = F + 2 F F k k − 1 k − 1 k − 2 k − 1 k − 1 k − 2 k − 1 k − 1 k − 1 2 2 2 = ( F + F ) + (2 F F − F ) . k − 1 k − 2 k − 1 k − 2 k − 2 By this equation and the inductive hypothesis, 2 2 2 2 2 F F − F = ( F + F ) + (2 F F − F ) = F + F = F , k k − 1 k − 1 k − 2 2 k − 2 2 k − 3 2 k − 1 k − 1 k − 1 k − 2 k − 2 as desired. Now, we need to finish the inductive step for the other equation: 2 2 2 2 2 2 F + F = ( F + F ) + F = 2 F + 2 F F + F k − 1 k − 2 k − 1 k − 2 k k − 1 k − 1 k − 1 k − 2 2 2 2 = 2( F + F ) + 2 F F − F . k − 1 k − 2 k − 1 k − 2 k − 2 By the inductive hypothesis, 2 2 2 2 2 F + F = 2( F + F ) + 2 F F − F = 2 F + F k − 1 k − 2 2 k − 2 2 k − 3 k k − 1 k − 1 k − 2 k − 2 = F + F = F , 2 k − 1 2 k − 2 2 k as desired. Therefore, the induction is complete and both identities have been proven. (These identities may also be proven by Binet’s formula or by matrix products.) Now, consider the Fibonacci Sequence (mod 8) and (mod 27). The first terms of the Fi- bonacci Sequence (mod 8) are 1 , 1 , 2 , 3 , 5 , 0 , 5 , 5 , 2 , 7 , 1 , 0 , . . . (repeat of the beginning) so the k k +2 period of the Fibonacci Sequence (mod 8) is 12. 2 ≡ 2 (mod 12) for all k ≥ 2, so g = F 1005 ≡ F ≡ 2 (mod 8). To calculate the period (mod 27), write out terms of the 2011 8 2 sequence (1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 7 , 1 , 8 , 0 , . . . ). Note that F ≡ 0 (mod 27). Therefore, for all 12 indicies i such that 13 ≤ i ≤ 24, F ≡ 8 F (mod 27) since this part of the sequence is gen- i i − 12 erated by F ≡ 0 and F ≡ 8 (mod 27). Therefore, F ≡ 64 ≡ 10 (mod 27). By the same 12 13 23 logic as before, F ≡ 10 F if 25 ≤ i ≤ 36. Therefore, F ≡ 80 ≡ − 1 (mod 27). Therefore, i i − 24 35 for all i such that 36 ≤ i ≤ 71, F ≡ − F (mod 27), so F ≡ 1 (mod 27). Since F ≡ 0 i i − 36 71 72 (mod 27), the Fibonacci sequence repeats after 72 terms. There is no smaller period, as that period would have to divide 36 or 24, even though we know that F ≡ − 1 and F ≡ 10 35 23 (mod 27). 1002 334 334 1005 1005 Now, 2 = 8 ≡ ( − 1) ≡ 1 (mod 9), so 2 ≡ 8 (mod 72). Therefore, F ≡ F 8 2 (mod 27). Therefore, g ≡ F ≡ 34 (mod 216), so the answer is 34 . 2011 8