Привет, математическая блог. Я тут понемножку схожу с ума.

Читаю «Конкретную математику» Кнута и столкнулся с тем, перед чем мой жалкий разум меркнет и разлагается.

задача 2.36 из главы про суммы:

Последовательность Соломона Голомба f(1),f(2),f(3) — единственная неубывающая последовательность целых чисел, обладающая тем свойством, что она содержит ровно f(k) вхождений каждого k

далее идет таблица первых значений

n 1 2 3 4 5 6 7 8 9 10 11 12

f(n) 1 2 2 3 3 4 4 4 5 5 5 6

Что эта за функция я примерно представляю. Допустим n=3, f(3)=2 и соответственно в ряду f(n) будет две тройки.

Далее вводится функция g(n) — наибольшее целое число m такое, что f(m)=n.

Что такое g(n) тоже вроде бы понятно. Пусть n=5, тогда наибольшее f(m)=5 — это f(11) и соответственно g(5)=11.

Дальше начинается сама задача:

а) просят показать, что g(n)=сумма по к от о до n f(k). Это действительно следует непосредственно из того, что g(n)–g(n–1)=f(n), но в ответах эта формула дается как «по определению». Я это никаким образом не могу ухватить своей башкой! Почему g(n)–g(n–1) будет f(n)?

b) просят показать, что g(g(n))=сумма по к от о до n kf(k). Это выводится из разности g(g(n))–g(g(n–1)), но я опять же убей не пойму что такое g(g(n)) в принципе.

Спасибо!

GD Star Rating
loading...

7 Responses to Последовательность Соломона Голомба

  1. Zvin:

    Твоя последовательность тесно связана с F(n), через золотое сечение ?:1+sqrt5)/2
    соответственно, для твоей последовательности:
    an=?2–?n?–1

  2. Zvin:

    можешь записать, например, так: для такого k, что: a1+a2+…+an–1 < k <= a1+a2+…+an, a(k)=n

  3. NiMonkey:

    g(g(n)) — это жэ от жэ от эн. Жэ от эн натуральное число? Натуральное. Значит от него можно взять ещё раз жэ. Что непонятного?

  4. Ssan:

    непонятно, что это по сути есть. т.е. что происходит с этим натуральным n (с изначальным натуральным n), когда от него берут п

  5. CiMoon:

    Это показывается методом математической индукции.

    Метода мат. индукции выглядит так:
    1) показываем выполнимость для первого элемента;
    2) доказываем, что если это верно для элемента n, то это верно и для элемента n+1.

    Получается, что из 1 ? 2, из 2 ? 3, из 3 ? 4 и так далее.

    В данном случае:

    a)
    1) показываем, что g(1) = f(1) (некоторые математики адекватно проглатывают пастулат, что g(0) = 0, и это в общем более корректно, хоть и не всем понятно);
    2) показываем, что g(n) = g(n ­ — 1) + f(n).

    б)
    g(n) определено для любого натурального числа. В свою очередь результатом g(n) являются также только натуральные числа. Это значит, что g(g(n)) переводится на русский так:

    Берём n–й элемент последовательности g(n) = m, а потом для полученного числа m (оно же пренадлежит множеству натуральных, значит, можно) берём m–й элемент той же последовательности h = g(m). Таким образом, каждому натуральному числу n сопоставляется число h. Получаем последовательность h(n) = g(g(n)). Кажется, это называется композицией.

  6. La:

    Darth– *APPLOUDS*

  7. CiMoon:

    1.
    Ок, для единицы всё понятно, g(g(1)) = g(1) = 1.

    Катит.

    2.
    Терь смотрим, что происходит, когда увеличиваем n на 1. Например, с 2 до
    g(g(3)) ­ — g(g(2)) = g(5) ­ — g(3) = 11 ­ — 5 = 6;
    n * f(n) = 3 * f(3) = 2 * 2 = 6.

    Снова катит.

    Далее, чтобы нам жилось нормально, будем оперировать не этой кучей скобочек, а просто числами, описывающими два состояния: до и
    после увеличения n на 1.

    Новые значения:
    N — n + 1;
    F — значение f(N);
    G —  значение g(N);
    G2 — значение g(G).

    При этом мы знаем, что G = g(n) + F. А вот с G2 всё веселее: у неё аргумент подскочил сразу на F. Поэтому

    G2 = g(g(n)) + сумма(k от от G ­ — F + 1 до G; f(k)).

    Так вот по определению f(k) на этом интервале имеет одно и то же значение f(F), поэтому

    G2 = g(g(n)) + Ff(F).

    Собственно, чтд.

Добавить комментарий