Guest
Новичок
|
    
Всем доброго времени суток.
Есть замечательная книга 'Конкретная математика', по ходу чтения которой у меня появились несколько вопросов.
Конкретнее, мне не понятна следующая штука:
есть рекуррентное соотношение:
f(1) = a;
f(2n) = 2f(n) + b;
f(2n + 1) = 2f(n) + v;
если попробовать его развернуть, то можно заметить, что коэффиценты при a, b и v меняются => их можно заменить некими абстракными функциями от n, т.е.
f(n) = H(n)a + I(n)b + J(n)v;
Далее в книге предлагается заменить f(n) некой постоянной функцией, чтобы выявить возможную закономерность между коэффицентами H(n), I(n) и J(n).
сначала f(n) = 1, тогда
(1)
1 = a;
1 = 2 * 1 + b;
1 = 2 * 1 + v;
(отсюда a = 1, b = 0, v = 0)
далее f(n) = n, тогда
(2)
1 = a;
2n = 2n + b;
2n + 1 = 2n + v;
(отсюда a = 1, b = 0, v = 1)
В общем, мне совершенно не понятно, почему в случае (1) единица оставалась неизменной, в отличе от случая (2), когда её следовало бы сначала домножить на 2, а потом прибавить единицу.
заранее благодарен.
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 14 июня 2006 6:17 | IP
|
|
Guest
Новичок
|
какая страница в "Конкретной математике"?
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 14 июня 2006 8:10 | IP
|
|
Guest
Новичок
|
30
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 14 июня 2006 9:31 | IP
|
|
Angel Studio
Удален
|
Цитата: Guest написал 14 июня 2006 6:17
Всем доброго времени суток.
Есть замечательная книга 'Конкретная математика', по ходу чтения которой у меня появились несколько вопросов.
Конкретнее, мне не понятна следующая штука:
есть рекуррентное соотношение:
f(1) = a;
f(2n) = 2f(n) + b;
f(2n + 1) = 2f(n) + v;
если попробовать его развернуть, то можно заметить, что коэффиценты при a, b и v меняются => их можно заменить некими абстракными функциями от n, т.е.
f(n) = H(n)a + I(n)b + J(n)v;
Далее в книге предлагается заменить f(n) некой постоянной функцией, чтобы выявить возможную закономерность между коэффицентами H(n), I(n) и J(n).
сначала f(n) = 1, тогда
(1)
1 = a;
1 = 2 * 1 + b;
1 = 2 * 1 + v;
(отсюда a = 1, b = 0, v = 0)
далее f(n) = n, тогда
(2)
1 = a;
2n = 2n + b;
2n + 1 = 2n + v;
(отсюда a = 1, b = 0, v = 1)
В общем, мне совершенно не понятно, почему в случае (1) единица оставалась неизменной, в отличе от случая (2), когда её следовало бы сначала домножить на 2, а потом прибавить единицу.
заранее благодарен.
На сколько я понял вопрос, авторы книги нисколько не ошиблись: функция f(n)=1 - это тождественная единица, т.е. функция возвращает значение 1 при любом n. И ничего ни на что здесь умножать не надо.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 15 июня 2006 6:09 | IP
|
|
|
Форум
Рекуррентное соотношение
