3
1

Докажите, что для любой пары натуральных чисел $%k$% и $%n$% существуют $%k$% (не обязательно различных) натуральных чисел $%m_1, m_2, . . . , m_k$%, удовлетворяющих равенству $$1+\frac{2^k-1}{n}=(1+\frac{1}{m_1})(1+\frac{1}{m_2}) . . . (1+\frac{1}{m_k})$$

задан 13 Апр '14 17:52

изменен 13 Апр '14 17:52

10|600 символов нужно символов осталось
2

Применим метод математической индукции. Прежде всего, заметим, что при $%k=1$% утверждение очевидно (получается одно число $%1+\frac1n$%).

Пусть $%k > 1$%. Проводим индукцию по $%n$%. При $%n=1$% число в левой части равно произведению $%k$% двоек, то есть $%m_1=\cdots=m_k=1$%.

Пусть $%n > 1$%, и предположим, что для меньших значений $%n$% утверждение доказано при всех $%k$%. Будем различать два случая.

1) $%n$% чётно, $%n=2m$%. Тогда $%1+\frac{2^k-1}n=\frac{2^k+2m-1}{2m}=\frac{2^k+2m-1}{2^k+2m-2}\cdot\frac{2^{k-1}+m-1}{m}=(1+\frac1{2^k+2m-2})(1+\frac{2^{k-1}-1}m)$%. Первый сомножитель имеет вид $%1+\frac1d$% для натурального $%d$%. Второй сомножитель по индукционному предположению можно представить в виде произведения $%k-1$% сомножителей требуемого вида ввиду $%k-1\ge1$%.

2) $%n$% нечётно, $%n=2m-1$%, $%m > 1$%. Здесь $%1+\frac{2^k-1}n=\frac{2^k+2m-2}{2m-1}=\frac{2m}{2m-1}\cdot\frac{2^{k-1}+m-1}{m}=(1+\frac1{2m-1})(1+\frac{2^{k-1}-1}{m})$% с теми же выводами. Предположение индукции применимо ввиду $%m < 2m-1=n$%.

ссылка

отвечен 13 Апр '14 18:30

@falcao: спасибо, красивое решение. У меня есть пару вопросов:
1)когда Вы написали "Пусть $%n>1$%, и предположим, что для меньших значений $%n$% утверждение доказано при всех $%k$%." - вы имели ввиду, для всех $%n$%, больших единицы?
2)как из $%\frac{2^k+2m-1}{2m}$% получилось $%\frac{2^k+2m-1}{2^k+2m-2}\cdot\frac{2^{k-1}+m-1}{m}$%?

(13 Апр '14 18:51) kirill1771

1) Случай $%n=1$% был рассмотрен как база индукции. Далее надо рассмотреть оставшийся случай, то есть $%n > 1$%. При доказательстве утверждения для данного $%n$% мы, как обычно, предполагаем, что оно верно для всех меньших натуральных чисел, то есть для $%1$%, $%2$%, ..., $%n-1$%. На все эти случаи можно ссылаться как на уже доказанные.

2) Обратите внимание на то, что $%2^k+2m-2=2(2^{k-1}+m-1)$%, сокращая общий множитель в числителе и знаменателе. Выражение справа превращается в выражение слева.

(13 Апр '14 19:01) falcao

@falcao: это я понял, а как появилось $%\frac{2^k+2m-1}{2^k+2m-2}$% (левый множитель этого выражения)?

(13 Апр '14 21:53) kirill1771

@kirill1771: вероятно, Ваш вопрос состоит в следующем (если я правильно догадался). То, что тождество верно, это понятно, но как додумались до самого этого преобразования? Ответ очень простой: я рассмотрел случаи небольших n и посмотрел, какая получается при этом закономерность. Всё идёт от опыта и от наблюдений, как и в "естественных" науках. Выражение в числителе принимает, по сути, любые значения (нечётные). Допустим, это 17. Естественно тогда предположить, что оно получилось из 17/16 = 1 + 1/16.

(13 Апр '14 22:23) falcao

@falcao: да, спасибо, я просто смысл своего вопроса плохо донес, мне очень интересно, как кто-то до чего-то додумывается, тем более в этом случае.

(13 Апр '14 22:31) kirill1771

@kirill1771: это очень похвально само по себе, но тогда в такой форме и надо спрашивать. Я всегда отвечаю прямо на вопрос. Вы спросили "как получилось". Я объяснил "буквально". Это почти как в анекдоте про "вы находитесь на воздушном шаре" :)

(13 Апр '14 22:36) falcao

@falcao: да, согласен, просто немного заклинило меня - сегодня целый день чего-то решал, под вечер периодически "замыкание" происходит. Впредь буду следить за конкретностью вопросов. Спасибо.

(13 Апр '14 22:49) kirill1771
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×4,854
×916
×472

задан
13 Апр '14 17:52

показан
725 раз

обновлен
13 Апр '14 22:50

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru