Докажите, что для последовательности чисел Фибоначчи данное выражение - целое

@KatarinaR · Регистрация: 17.02.2015

Студворк — интернет-сервис помощи студентам

Докажите,что для последовательности чисел Фибоначчи {u_k} при любом целом неотрицательном n число
1/10*(u_n+60-u_n) - целое

@kabenyuk · 22.11.2015, 14:34

Тут придется подсчитать остатки от деления на 10 для первых 61 чисел Фибоначчи, считая u₀=u₁=1, и помня о том, что u_n+2=u_n+1+u_n, это сделать нетрудно. Мы с удивлением увидим, что u₆₀=u₆₁=1(mod 10).

Дальше провести индукцию.

echs · 23.11.2015, 16:54

Доказать,что u_n+60=u_n (mod 10)
Метод математикой индукции
Шаг 1.
При n=0 сравнение очевидно, ибо u₀=u₆₀=1 (mod 10)
Шаг 2.
Допустим, что верно сравнение при n=k. То есть
u_k+60=u_k (mod 10)
И докажем, что оно верно при n=k+1
u_(k+1)+60=u_k+1 (mod 10)
Имеем
u_(k+1)+60 = u_k+61 = u_k+59 + u _k+60 = u_k-1 + u_k = u_{k + 1} (mod 10)
Что и требовалось доказать.

@Alex5 · 24.11.2015, 14:26

Сообщение от kabenyuk

для первых 61 чисел

kabenyuk, можно обойтись без вычисления 60 чисел.

Сообщение от geh

очевидно, ибо u₆₀=1 (mod 10)

geh, как-то не очень очевидно. (Вы предлагаете 60 чисел вычислять?)

А что если (u₁₂₀-u₀)/45

iifat · 24.11.2015, 14:53

Сообщение от Alex5

60 чисел вычислять?

Ну, есть ещё прямая формула.

@kabenyuk · 24.11.2015, 15:39

Сообщение от Alex5

можно обойтись без вычисления 60 чисел.

Наверное. Это первая пара чисел, равная 1 по модулю 10 (кроме нулевого и первого), далее такие пары встречаются через каждые 60 шагов.

Добавлено через 6 минут
По этому поводу можно посмотреть периоды Пизано.

echs · 24.11.2015, 16:35

kabenyuk,
Я тоже посчитал по модулю 10 (всего пара минут)

@Catstail · 25.11.2015, 17:19

Странное что-то у меня получается:

Кликните здесь для просмотра всего текста

Code
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
0 0
1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
10 55
11 89
12 144
13 233
14 377
15 610
16 987
17 1597
18 2584
19 4181
20 6765
21 10946
22 17711
23 28657
24 46368
25 75025
26 121393
27 196418
28 317811
29 514229
30 832040
31 1346269
32 2178309
33 3524578
34 5702887
35 9227465
36 14930352
37 24157817
38 39088169
39 63245986
40 102334155
41 165580141
42 267914296
43 433494437
44 701408733
45 1134903170
46 1836311903
47 2971215073
48 4807526976
49 7778742049
50 12586269025
51 20365011074
52 32951280099
53 53316291173
54 86267571272
55 139583862445
56 225851433717
57 365435296162
58 591286729879
59 956722026041
60 1548008755920 <- !!!

echs · 25.11.2015, 17:50

Catstail,
Счет надо вести с НУЛЯ. Ведь номера 1 и 2 занимают единицы.

@kabenyuk · 25.11.2015, 17:52

Сообщение от Catstail

Странное что-то у меня получается

Не удивительно. Вы начали нумерацию с 1 и к тому же u₁=0, u₂=1.
Более принята другая нумерация и другие начальные данные u₀=1, u₁=1.
Потому ваша последовательность отстает на шаг - то что вы назвали 60-м членом на самом деле 59-й.

echs · 25.11.2015, 17:52

Считать можно было не все число целиком,
а только последнюю цифру (то есть по модулю 10)

@Catstail · 25.11.2015, 18:05

Сообщение от geh

Счет надо вести с НУЛЯ

- я и вел с нуля... Да, я и до публикации таблицы понимал, что дело в нумерации.

kabenyuk, вот картинка из Вики

@kabenyuk · 25.11.2015, 18:39

Сообщение от Catstail

вот картинка из Вики

Вынужден согласиться с вами, действительно часто нумеруют числа Фибоначчи с 1 (посмотрел еще разные книжки). Но у меня в памяти почему-то всегда было с нуля. Но это не имеет значения для задачи.
Там же вот какая формулировка: u_60+n-u_n делится на 10. При n=1 необходимо вычислить 61-й член (но уже со сдвинутой нумерацией).

@texnik-san · 27.11.2015, 16:27

Предлагаю другой подход к решению.

10=2*5. Если некое число a таково, что a mod 2 = 0 и a mod 5 = 0, то и a mod 10 = 0

Обратим внимание, что остатки от деления на 2 у чисел Фибоначчи зацикливаютсяс шагом 3, а остатки от деления на 5 - с шагом 20. Делаем вывод, что остатки от деления на 10 зацикливаются с шагом 60.

@Catstail · 27.11.2015, 17:40

Сообщение от texnik-san

Обратим внимание, что остатки от деления на 2 у чисел Фибоначчи зацикливаются с шагом 3, а остатки от деления на 5 - с шагом 20

- это положение нуждается в доказательстве

@texnik-san · 27.11.2015, 21:05

Сообщение от Catstail

- это положение нуждается в доказательстве

Равенства
u1 mod 2 = u4 mod 2
u2 mod 2 = u5 mod 2
и
u1 mod 5 = u21 mod 5
u2 mod 5 = u22 mod 5
просто проверяем вычислениями

Кликните здесь для просмотра всего текста

1	1	1	1
2	1	1	1
3	2	0	2
4	3	1	3
5	5	1	0
6	8	0	3
7	13	1	3
8	21	1	1
9	34	0	4
10	55	1	0
11	89	1	4
12	144	0	4
13	233	1	3
14	377	1	2
15	610	0	0
16	987	1	2
17	1597	1	2
18	2584	0	4
19	4181	1	1
20	6765	1	0
21	10946	0	1
22	17711	1	1

Остальное следует из определения последовательности и свойства сложения по модулю.

@Catstail · 27.11.2015, 21:30

texnik-san, пример не является доказательством общего утверждения

@texnik-san · 27.11.2015, 21:50

Пример - это первый шаг матиндукции.

Дальше сами, мне очень лень )))

@Alex5 · 27.11.2015, 22:33

Сообщение от texnik-san

Равенства
u1 mod 2 = u4 mod 2
u2 mod 2 = u5 mod 2
и
u1 mod 5 = u21 mod 5
u2 mod 5 = u22 mod 5
просто проверяем вычислениями

texnik-san, верно.
Причем по модулю 5 можно обойтись вычислением первых 7 элементов.
( mod 5 ) 0 1 1 2 3 0 3 3 . . .
Значит следующие 5 элементов получаются умножением на 3 ( по модулю 5 ).
0 1 1 2 3
потом 0 3 3 . .
потом 0 3*3 3*3 . .
потом 0 3*3*3 3*3*3 . .
Остается понять, какая степень 3 равняется 1 (mod 5 ).

Добавлено через 3 минуты
Пример. mod( 17 )

0 1 1 2 3 5 8 13 4 0 4 4

Так как 4*4 = -1, 4*4*4*4 = 1, то период по модулю 17 равен 9*4 = 36.

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@KatarinaR 0 / 0 / 0 Регистрация: 17.02.2015 Сообщений: 99

	Докажите, что для последовательности чисел Фибоначчи данное выражение - целое 22.11.2015, 13:20. Показов 1792. Ответов 18 Метки нет (Все метки) Докажите,что для последовательности чисел Фибоначчи {u_k} при любом целом неотрицательном n число 1/10*(u_n+60-u_n) - целое 0

@kabenyuk $Эксперт по математике/физике$ 4182 / 3052 / 918 Регистрация: 19.11.2012 Сообщений: 6,196
	22.11.2015, 14:34
	Тут придется подсчитать остатки от деления на 10 для первых 61 чисел Фибоначчи, считая u₀=u₁=1, и помня о том, что u_n+2=u_n+1+u_n, это сделать нетрудно. Мы с удивлением увидим, что u₆₀=u₆₁=1(mod 10). Дальше провести индукцию. 2

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	23.11.2015, 16:54
	Доказать,что u_n+60=u_n (mod 10) Метод математикой индукции Шаг 1. При n=0 сравнение очевидно, ибо u₀=u₆₀=1 (mod 10) Шаг 2. Допустим, что верно сравнение при n=k. То есть u_k+60=u_k (mod 10) И докажем, что оно верно при n=k+1 u_(k+1)+60=u_k+1 (mod 10) Имеем u_(k+1)+60 = u_k+61 = u_k+59 + u _k+60 = u_k-1 + u_k = u_{k + 1} (mod 10) Что и требовалось доказать. 0

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	24.11.2015, 16:35
	kabenyuk, Я тоже посчитал по модулю 10 (всего пара минут) 0

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	25.11.2015, 17:50
	Catstail, Счет надо вести с НУЛЯ. Ведь номера 1 и 2 занимают единицы. 0

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	25.11.2015, 17:52
	Считать можно было не все число целиком, а только последнюю цифру (то есть по модулю 10) 0

@texnik-san шапоклякистка 8-го дня 3681 / 2241 / 391 Регистрация: 26.06.2015 Сообщений: 4,647 Записей в блоге: 1
	27.11.2015, 16:27
	Предлагаю другой подход к решению. 10=2*5. Если некое число a таково, что a mod 2 = 0 и a mod 5 = 0, то и a mod 10 = 0 Обратим внимание, что остатки от деления на 2 у чисел Фибоначчи зацикливаютсяс шагом 3, а остатки от деления на 5 - с шагом 20. Делаем вывод, что остатки от деления на 10 зацикливаются с шагом 60. 0

@Catstail Супер-модератор 38173 / 21108 / 4307 Регистрация: 12.02.2012 Сообщений: 34,709 Записей в блоге: 14
	27.11.2015, 21:30
	texnik-san, пример не является доказательством общего утверждения 0

@texnik-san шапоклякистка 8-го дня 3681 / 2241 / 391 Регистрация: 26.06.2015 Сообщений: 4,647 Записей в блоге: 1
	27.11.2015, 21:50
	Пример - это первый шаг матиндукции. Дальше сами, мне очень лень ))) 0