Difference between revisions of "2024 AMC 10B Problems/Problem 23"
(→Solution 3 (Characteristic Equation)) |
(→Solution 3 (Characteristic Equation and Generic Formula)) |
||
(4 intermediate revisions by the same user not shown) | |||
Line 23: | Line 23: | ||
==Solution 3 (Characteristic Equation and Generic Formula) == | ==Solution 3 (Characteristic Equation and Generic Formula) == | ||
− | Using characteristic equation <math>x^2=x+1</math> and starting <math>F_1 =1, F_2=1</math>, we get < | + | Using characteristic equation <math>x^2=x+1</math> and starting terms <math>F_1 =1, F_2=1</math>, we get <math>F_n=\frac{1}{\sqrt{5}} (A^n- B^n) </math>, A= <math>\frac{1+\sqrt{5}}{2}</math> , B = <math>\frac{1-\sqrt{5}}{2}</math> |
− | + | Define new sequence (this is actually Lucas sequence) <cmath> L_n = \frac{F_{2n}}{F_{n}} = \frac{A^{2n} - B^{2n}}{A^{n} - B^{n}} =A^n+B^n </cmath> | |
− | + | Given <math>L_n</math> has same 2 roots A , B from characteristic equation <math>x^2=x+1</math> which implies <math> L_{n} =L_{n-1} + L_{n-2} </math> , it can also be verified below. | |
− | + | Noticing <math> A^2 = A + 1 </math> and <math> B^2 = B + 1 </math>, | |
− | Given <math> | ||
− | |||
Therefore, | Therefore, | ||
<cmath> | <cmath> | ||
− | + | L_n = A^n + B^n = A^2 \cdot A^{n-2} + B^2 \cdot B^{n-2} = (A +1) \cdot A^{n-2} + (B+1) \cdot B^{n-2} = (A^{n-1} + B^{n-1}) + (A^{n-2} + B^{n-2}) = L_{n-1} + L_{n-2} . | |
</cmath> | </cmath> | ||
− | Calculate the first 10 | + | Calculate the first 10 terms using the recurrence relation <math> L_{n} =L_{n-1} + L_{n-2} </math> and the initial values <math> L_1 = 1 </math> and <math> L_2 = 3 </math>, we get: |
+ | <math> | ||
+ | L_1 = 1, \quad L_2 = 3, \quad L_3 = 4, \quad L_4 = 7, \quad L_5 = 11 </math> | ||
+ | |||
+ | <math>\quad L_6 = 18, \quad L_7 = 29, \quad L_8 = 47, \quad L_9 = 76, \quad L_{10} = 123 | ||
+ | </math> | ||
so the answer is <math> 1 + 3 + 4 + 7 + 11 + 18 + 29 + 47 + 76 + 123 = \boxed{(B) 319} </math>. | so the answer is <math> 1 + 3 + 4 + 7 + 11 + 18 + 29 + 47 + 76 + 123 = \boxed{(B) 319} </math>. | ||
Line 42: | Line 45: | ||
~[https://artofproblemsolving.com/wiki/index.php/User:Cyantist luckuso] | ~[https://artofproblemsolving.com/wiki/index.php/User:Cyantist luckuso] | ||
− | Appendix : Closed-form expression for the sum of the sequence <math> | + | Appendix : Closed-form expression for the sum of the Lucas sequence <math> L_n </math>, |
<cmath> | <cmath> | ||
− | S_k = \sum_{n=1}^{k} | + | S_k = \sum_{n=1}^{k} L_n = \sum_{n=1}^{k} (A^n + B^n) = \sum_{n=1}^{k} A^n + \sum_{n=1}^{k} B^n = \frac{A(1 - A^k)}{1 - A} + \frac{B(1 - B^k)}{1 - B} |
− | |||
</cmath> | </cmath> | ||
Recall the sum formula for a geometric series: | Recall the sum formula for a geometric series: | ||
<cmath> | <cmath> | ||
− | \sum_{n=1}^{k} r^n = r + r^2 + \cdots + r^k = \frac{r(1 - r^k)}{1 - r}, \quad \text{for } r \neq 1 | + | \sum_{n=1}^{k} r^n = r + r^2 + \cdots + r^k = \frac{r(1 - r^k)}{1 - r}, \quad \text{for } r \neq 1 |
</cmath> | </cmath> | ||
To simplify further, notice that: | To simplify further, notice that: | ||
− | + | <math> A = \frac{1 + \sqrt{5}}{2} </math> and <math> B = \frac{1 - \sqrt{5}}{2} </math> are roots of <math> x^2 = x + 1 </math>, so: | |
<cmath> | <cmath> | ||
− | 1 - A = | + | 1 - A = B \quad \text{and} \quad 1 - B = A. |
</cmath> | </cmath> | ||
<cmath> | <cmath> | ||
− | S_k = \frac{A(1 - A^k)}{ | + | S_k = \frac{A(1 - A^k)}{B} + \frac{B(1 - B^k)}{A} = \frac{A^{k+2} - A^2 + B^{k+2} - B^2}{A \cdot B} = \frac{A^{k+2} + B^{k+2} - (A^2+ B^2) }{A \cdot B} = A^{k+2} + B^{k+2} -3 = L_{n+2} - 3 |
</cmath> | </cmath> | ||
− | This formula gives us a direct way to calculate the sum of <math> | + | |
+ | This formula <math>S_k = A^{k+2} + B^{k+2} - 3 </math> gives us a direct way to calculate the sum of <math> L_n </math> for any <math> k </math>. | ||
==Solution 4== | ==Solution 4== |
Revision as of 21:23, 15 November 2024
- The following problem is from both the 2024 AMC 10B #23 and 2024 AMC 12B #18, so both problems redirect to this page.
Contents
[hide]Problem
The Fibonacci numbers are defined by and for What is
Solution 1 (Bash)
The first terms
so the answer is .
Solution 2 (Pattern)
Plug in a few numbers to see if there is a pattern. List out a few Fibonacci numbers, and then try them on the equation. You'll find that and The pattern is that then ten fractions are in their own Fibonacci sequence with the starting two terms being and , which can be written as for The problem is asking for the sum of the ten terms , and after adding up the first ten terms , you arrive at the solution
~Cattycute
Note: The first ten terms () are actually part of a sequence called the Lucas numbers.
~NXC
Solution 3 (Characteristic Equation and Generic Formula)
Using characteristic equation and starting terms , we get , A= , B =
Define new sequence (this is actually Lucas sequence)
Given has same 2 roots A , B from characteristic equation which implies , it can also be verified below. Noticing and , Therefore,
Calculate the first 10 terms using the recurrence relation and the initial values and , we get:
so the answer is .
Appendix : Closed-form expression for the sum of the Lucas sequence ,
Recall the sum formula for a geometric series:
To simplify further, notice that: and are roots of , so:
This formula gives us a direct way to calculate the sum of for any .
Solution 4
Remember that for any ,
so the answer is .
~Apollo08 (first solution)
Video Solution 1 by Pi Academy (In Less Than 3 Mins ⚡🚀)
https://youtu.be/YjQ9Q93RCu4?feature=shared
~ Pi Academy
Video Solution 2 by Innovative Minds
https://www.youtube.com/watch?v=7KEk5VbxwAU
Video Solution 3 by SpreadTheMathLove
https://www.youtube.com/watch?v=24EZaeAThuE
See also
2024 AMC 10B (Problems • Answer Key • Resources) | ||
Preceded by Problem 22 |
Followed by Problem 24 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | ||
All AMC 10 Problems and Solutions |
2024 AMC 12B (Problems • Answer Key • Resources) | |
Preceded by Problem 17 |
Followed by Problem 19 |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | |
All AMC 12 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.