Recursion Story Begins!

Algebra Level 3

Define the sequence { F n } \{F_n\} recursively as follows: F 0 = 1 F_0 = 1 , F 1 = 1 F_1 = 1 , and for n 2 n \ge 2 , F n F_n be the remainder of F n 1 + F n 2 F_{n - 1} + F_{n - 2} when divided by 3 3 .

What is the value of k = 2017 2024 F k ? \large\ \sum _{ k=2017 }^{ 2024 }{ { F }_{ k } }?


The answer is 9.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Hassan Abdulla
Sep 1, 2017

F k = { 1 , 1 , 2 , 0 , 2 , 2 , 1 , 0 , 1 , 1 , . . . . . . . . } { F }_{ k }=\left\{ 1,1,2,0,2,2,1,0,1,1,........ \right\}

we can see that

F k = { 1 k = 8 n 1 k = 8 n + 1 2 k = 8 n + 2 0 k = 8 n + 3 2 k = 8 n + 4 2 k = 8 n + 5 1 k = 8 n + 6 0 k = 8 n + 7 { F }_{ k }=\begin{cases} 1 & & k=8n \\ 1 & & k=8n+1 \\ 2 & & k=8n+2 \\ 0 & & k=8n+3 \\ 2 & & k=8n+4 \\ 2 & & k=8n+5 \\ 1 & & k=8n+6 \\ 0 & & k=8n+7 \end{cases}

so k = 0 8 F k = 9 k = 0 8 n F k = 9 n \sum _{ k=0 }^{ 8 }{ { F }_{ k } } =9\Rightarrow \sum _{ k=0 }^{ 8n }{ { F }_{ k } } =9n

k = 2017 2024 F k = k = 0 2024 F k k = 0 2016 F k \sum _{ k=2017 }^{ 2024 }{ { F }_{ k } } =\sum _{ k=0 }^{ 2024 }{ { F }_{ k } } -\sum _{ k=0 }^{ 2016 }{ { F }_{ k } }

= k = 0 8 253 F k k = 0 8 252 F k = 9 × 253 9 × 252 = 9 =\sum _{ k=0 }^{ 8\cdot 253 }{ { F }_{ k } } -\sum _{ k=0 }^{ 8\cdot 252 }{ { F }_{ k } } =9\times 253-9\times 252=9

This sequence repeats itself after 8 terms: 1, 1, 2, 0, 2, 2, 1, 0, and so on. To find F k F_k where k=2017, we divide 2017 by 8, which yields a remainder of 1. The first term is 1. 2024 divided by 8 yields a remainder of 0 (which is basically a remainder of 8). The 8th term is 0. So the answer is the sum of all the terms in one non-repeating sequence, which is 1 + 1 + 2 + 0 + 2 + 2 + 1 + 0 = 9 \boxed{9} .

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...