Функция натурального аргумента

[wpoms.]

Функция `f` определена на множестве натуральных чисел следующими условиями: `f(1) = 1`, `f(2n) = 2f(n)` и `nf(2n + 1) = (2n + 1 )(f(n) + n)` для всех `n >= 1`. i) Докажите, что `f(n)` - целое число. ii) Для какого количества натуральных чисел меньших `2007` выполняется равенство `f(n) = 2n` ?

@темы: Функции

Comments

[vyv2]

Введем новую функцию `g(n)=(f(n))/n`, тогда `g(1)=1 quad g(2n)=g(n) quad g(2n+1)=g(n)+1`.
i) `g(n) -целые, следовательно и `f(n)=ng(n)`- целые (по индукции).
ii) В терминах функции `g(n)`вопрос можно переформулировать следующим образом: для какого количества натуральных чисел меньших 2007` выполняется равенство `g(n)=(f(n))/n=2`?
`g(n)=1` может порождаться через формулу `g(2n)=g(n)` и принимает значение 1 при `n=1,2,4,8,...,1024`.
`g(2n+1)=2` может быть порождено после `g(n)=1` по формуле `g(2n+1)=g(n)+1=1` при `2n+1=3,5,9,...,1025`, а далее сохранять значение 2 по формуле `g(2n=g(n)`. Так `n=3` порождает числа со значением 2 для `n=6,12,24,..1536` всего 10 чисел, включая 3. `n=5` порождает числа со значением 2 на единицу меньше, т.е. 9 чисел `n=5,10,20,...,1280` и т.д. каждый раз на единицу меньше вплоть до последнего числа с `n=1025`.
Всего таких чисел будет `1+2+3+...+10=(1+10)*10/2=55`