рдлрд┐рдмреЛрдирд╛рдЪреА рд╕рдВрдЦреНрдпрд╛ рдЯреЗрдмрд▓ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдХреНрдпрд╛ рд╣реИ?
рдпрд╣ рдЯреВрд▓ рд╕реВрдЪрдХрд╛рдВрдХ (рдЗрдВрдбреЗрдХреНрд╕) рдорд╛рдиреЛрдВ рдХреА рдПрдХ рд░реЗрдВрдЬ рдХреЗ рд▓рд┐рдП рдлрд┐рдмреЛрдирд╛рдЪреА рд╕рдВрдЦреНрдпрд╛рдУрдВ \(F_n\) рдХреА рдЯреЗрдмрд▓ рдмрдирд╛рддрд╛ рд╣реИред рдЖрдк рдкрд╣рд▓рд╛ рдЗрдВрдбреЗрдХреНрд╕ n, рд╣рд░ рдкрдВрдХреНрддрд┐ рдореЗрдВ n рдХрд┐рддрдирд╛ рдмрдврд╝реЗрдЧрд╛ (рд╡реГрджреНрдзрд┐), рдФрд░ рдХрд┐рддрдиреА рдкрдВрдХреНрддрд┐рдпрд╛рдБ рдЪрд╛рд╣рд┐рдП тАФ рдпрд╣ рд╕рдм рдЪреБрдирддреЗ рд╣реИрдВред рдЗрд╕рдХреЗ рдмрд╛рдж рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рд╣рд░ n рдХреЗ рд╕рд╛рде рдЙрд╕рдХрд╛ рдлрд┐рдмреЛрдирд╛рдЪреА рдорд╛рди рджрд┐рдЦрд╛рддрд╛ рд╣реИ рдФрд░ рдпрд╣ рднреА рджрд░реНрд╢рд╛рддрд╛ рд╣реИ рдХрд┐ рд╢реНрд░реГрдВрдЦрд▓рд╛ рдХрд┐рддрдиреА рддреЗрдЬрд╝реА рд╕реЗ рдмрдврд╝рддреА рд╣реИред рдпрд╣ рдкреВрд░реА рддрд░рд╣ рдЧрдгрд┐рддреАрдп рдЯреВрд▓ рд╣реИ, рдЗрд╕рд▓рд┐рдП рджреБрдирд┐рдпрд╛ рднрд░ рдореЗрдВ рдПрдХ рдЬреИрд╕рд╛ рдХрд╛рдо рдХрд░рддрд╛ рд╣реИ рдФрд░ рдЗрд╕рдореЗрдВ рдХрд┐рд╕реА рджреЗрд╢ рдпрд╛ рдХреНрд╖реЗрддреНрд░ рдХреА рдХреЛрдИ рдорд╛рдиреНрдпрддрд╛ рд╢рд╛рдорд┐рд▓ рдирд╣реАрдВ рд╣реИред
рдЗрд╕рдХрд╛ рдЙрдкрдпреЛрдЧ рдХреИрд╕реЗ рдХрд░реЗрдВ
рд╕реВрдЪрдХрд╛рдВрдХ n рдХрд╛ рдкреНрд░рд╛рд░рдВрднрд┐рдХ рдорд╛рди (рдпрд╛рдиреА рдкрд╣рд▓рд╛ рджрд┐рдЦрдиреЗ рд╡рд╛рд▓рд╛ n), рд╡реГрджреНрдзрд┐ (рд╣рд░ рдкрдВрдХреНрддрд┐ рдореЗрдВ n рдХрд┐рддрдирд╛ рдмрдврд╝реЗ), рдФрд░ рджреЛрд╣рд░рд╛рд╡реЛрдВ рдХреА рд╕рдВрдЦреНрдпрд╛ (рдХрд┐рддрдиреА рдкрдВрдХреНрддрд┐рдпрд╛рдБ) рджрд░реНрдЬ рдХрд░реЗрдВред рдЙрджрд╛рд╣рд░рдг рдХреЗ рд▓рд┐рдП, рдпрджрд┐ рд╢реБрд░реБрдЖрддреА рдЗрдВрдбреЗрдХреНрд╕ 1, рд╡реГрджреНрдзрд┐ 1 рдФрд░ 13 рдкрдВрдХреНрддрд┐рдпрд╛рдБ рдЪреБрдиреЗрдВ, рддреЛ рдпрд╣ рдХреНрд▓рд╛рд╕рд┐рдХ рд╢реНрд░реГрдВрдЦрд▓рд╛ 1, 1, 2, 3, 5, 8, ... рдмрдирд╛рддреА рд╣реИ рдФрд░ \(F_{13} = 233\) рддрдХ рдкрд╣реБрдБрдЪрддреА рд╣реИред
рд╕реВрддреНрд░ рдХреА рд╡реНрдпрд╛рдЦреНрдпрд╛
рдлрд┐рдмреЛрдирд╛рдЪреА рд╢реНрд░реГрдВрдЦрд▓рд╛ рдЗрд╕ рдкреБрдирд░рд╛рд╡реГрддреНрддрд┐ (рд░рд┐рдХрд░реНрд╕рди) рд╕реЗ рдкрд░рд┐рднрд╛рд╖рд┐рдд рд╣реЛрддреА рд╣реИ:
$$F_1 = 1, \quad F_2 = 1, \quad F_n = F_{n-1} + F_{n-2} \;\; (n \ge 3)$$рдЗрд╕рдХреЗ рдЕрд▓рд╛рд╡рд╛ рдмрд┐рдиреЗрдЯ рдХрд╛ рдмрдВрдж рд░реВрдк (Binet's formula) рднреА рд╣реИ тАФ
$$F_n = \frac{(1+\sqrt{5})^n - (1-\sqrt{5})^n}{2^n \cdot \sqrt{5}}$$рдЬреЛ рд╡рд╣реА рдкреВрд░реНрдгрд╛рдВрдХ рджреЗрддрд╛ рд╣реИ, рдкрд░ рдмрдбрд╝реЗ n рдХреЗ рд▓рд┐рдП рдлреНрд▓реЛрдЯрд┐рдВрдЧ-рдкреЙрдЗрдВрдЯ рддреНрд░реБрдЯрд┐ рд╣реЛ рд╕рдХрддреА рд╣реИред рдпрд╣ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рд╕рдЯреАрдХ рдкреВрд░реНрдгрд╛рдВрдХ рдкреБрдирд░рд╛рд╡реГрддреНрддрд┐ рдХрд╛ рдЙрдкрдпреЛрдЧ рдХрд░рддрд╛ рд╣реИред \(n \le 0\) рдХреЗ рд▓рд┐рдП рдпрд╣ рд╕рд╛рдорд╛рдиреНрдпреАрдХреГрдд (рдиреЗрдЧрд╛рдлрд┐рдмреЛрдирд╛рдЪреА) рдирд┐рдпрдо \(F_{-n} = (-1)^{n+1} F_n\) рдЕрдкрдирд╛рддрд╛ рд╣реИ, рдЬрд┐рд╕рд╕реЗ \(F_0 = 0\), \(F_{-1} = 1\), \(F_{-2} = -1\) рдорд┐рд▓рддрд╛ рд╣реИред
рд╣рд▓ рдХрд┐рдпрд╛ рдЧрдпрд╛ рдЙрджрд╛рд╣рд░рдг
рдпрджрд┐ рд╢реБрд░реБрдЖрддреА рдЗрдВрдбреЗрдХреНрд╕ 5, рд╡реГрджреНрдзрд┐ 2 рдФрд░ 4 рдкрдВрдХреНрддрд┐рдпрд╛рдБ рд╣реЛрдВ, рддреЛ n рдХреЗ рдорд╛рди 5, 7, 9, 11 рд╣реЛрдВрдЧреЗред рдЗрдирдХреЗ рдлрд┐рдмреЛрдирд╛рдЪреА рдорд╛рди рдХреНрд░рдорд╢рдГ 5, 13, 34 рдФрд░ 89 рд╣реИрдВред рдЗрд╕рд▓рд┐рдП рдЯреЗрдмрд▓ рдХрд╛ рдЕрдВрддрд┐рдо рдорд╛рди \(F_{11} = 89\) рд╣реЛрдЧрд╛ред
рдЕрдХреНрд╕рд░ рдкреВрдЫреЗ рдЬрд╛рдиреЗ рд╡рд╛рд▓реЗ рдкреНрд░рд╢реНрди
рдХреНрдпрд╛ рд╡реГрджреНрдзрд┐ 1 рд╕реЗ рдЕрдзрд┐рдХ рд╣реЛ рд╕рдХрддреА рд╣реИ? рд╣рд╛рдБред рд╡реГрджреНрдзрд┐ 2 рд╣реЛрдиреЗ рдкрд░ рд╣рд░ рджреВрд╕рд░рд╛ рдЗрдВрдбреЗрдХреНрд╕, рд╡реГрджреНрдзрд┐ 3 рд╣реЛрдиреЗ рдкрд░ рд╣рд░ рддреАрд╕рд░рд╛ рдЗрдВрдбреЗрдХреНрд╕ рд▓рд┐рдпрд╛ рдЬрд╛рддрд╛ рд╣реИ, рдФрд░ рдЗрд╕реА рддрд░рд╣ рдЖрдЧреЗред
рдХреНрдпрд╛ рдЛрдгрд╛рддреНрдордХ рд╕реВрдЪрдХрд╛рдВрдХ рд╕рдорд░реНрдерд┐рдд рд╣реИрдВ? рд╣рд╛рдБ, рдиреЗрдЧрд╛рдлрд┐рдмреЛрдирд╛рдЪреА рд╡рд┐рд╕реНрддрд╛рд░ рдХреЗ рдЬрд╝рд░рд┐рдПред рд╢реБрд░реБрдЖрддреА рдЗрдВрдбреЗрдХреНрд╕ 0 рд░рдЦрдиреЗ рдкрд░ \(F_0 = 0\) рдорд┐рд▓рддрд╛ рд╣реИред
n рдХрд┐рддрдирд╛ рдмрдбрд╝рд╛ рд╣реЛ рд╕рдХрддрд╛ рд╣реИ? рдорд╛рди 64-рдмрд┐рдЯ рдкреВрд░реНрдгрд╛рдВрдХреЛрдВ рд╕реЗ рдЧрдгрдирд╛ рдХрд┐рдП рдЬрд╛рддреЗ рд╣реИрдВ рдФрд░ рд▓рдЧрднрдЧ \(F_{90}\) рддрдХ рд╕рдЯреАрдХ рд░рд╣рддреЗ рд╣реИрдВ; рдЗрд╕рдХреЗ рдЖрдЧреЗ рдмрд╣реБрдд рдмрдбрд╝реЗ рдорд╛рди рдУрд╡рд░рдлрд╝реНрд▓реЛ рд╣реЛ рд╕рдХрддреЗ рд╣реИрдВред