Форум программистов, компьютерный форум, киберфорум
Наши страницы
Дискретная математика
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/5: Рейтинг темы: голосов - 5, средняя оценка - 5.00
ACTIONFENIX
3 / 3 / 2
Регистрация: 21.02.2015
Сообщений: 77
Завершенные тесты: 1
1

Доказательство решения рекуррентного соотношения методом индукции

16.04.2016, 20:19. Просмотров 877. Ответов 3
Метки нет (Все метки)

С доказательством первого шага понятно, а вот как делать дальше?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.04.2016, 20:19
Ответы с готовыми решениями:

Решение рекуррентного соотношения
Не знаю с какого бока подойти к решению, прошу помощи. Вот само соотношение - Q0 = a Q1 = b Qn =...

Решение рекуррентного соотношения
Помогите, пожалуйста, решить следующее рекуррентное соотношение: an+2 + 9an = 0 где: a0 = a1 = 1.

Общее решение рекуррентного соотношения
Нашел корни характеристического уравнения. x1=-2 x2=1 x3=-1 x4=2 x5=7 Как записать общее...

Найти первые 5 членов рекуррентного соотношения.
выручайте плиз!

Найти общее решение рекуррентного соотношения 5-го порядка
И снова в бой. На этот раз рекуррентные соотношения. ...

3
mathidiot
Эксперт по математике/физике
3035 / 2623 / 1149
Регистрация: 14.01.2014
Сообщений: 5,669
16.04.2016, 21:36 2
В приведенном условии задачи какая-то ошибка - шаг по индукции дает: http://www.cyberforum.ru/cgi-bin/latex.cgi?T(2n)=2T(n)+2n=2n\cdot lg(n)+2n\neq 2nlg(2n)
0
Байт
Эксперт C
20456 / 12985 / 2729
Регистрация: 24.12.2010
Сообщений: 27,174
16.04.2016, 22:41 3
mathidiot, Однако, это не совсем так.
2nlgn + 2n = 2n(lgn + lg2) = 2n lg 2n
Очевидно, lg - логарифм по основанию 2

Добавлено через 4 минуты
И индукцию, видимо, надо вести не по n, а по k
Впрочем, совершенно непонятно, как ведет себя T на числах, не являющимися степенями двойки. И в самом деле T есть функция не от n, а от k.
ACTIONFENIX, дурят вашего брата...
0
ACTIONFENIX
3 / 3 / 2
Регистрация: 21.02.2015
Сообщений: 77
Завершенные тесты: 1
17.04.2016, 09:41  [ТС] 4
Задача в текстовом виде: Воспользуйтесь методом математической индукции для доказательства того, что, когда n является точной степенью 2, решением рекуррентного соотношения
http://www.cyberforum.ru/cgi-bin/latex.cgi?T(n)=\begin{cases} & \text{ 2 if } n=2  \\  & \text{ 2T(n/2)+n if } n={2}^{k}, k>1  \end{cases}
является http://www.cyberforum.ru/cgi-bin/latex.cgi?T(n)=n\lg n

Добавлено через 5 минут
Байт, вряд ли дурят, ибо я эту задачу взял с книги Кормена об алгоритмах. И там действительно логарифм по основанию 2.

Добавлено через 11 секунд
Уже вроде и сам решил задачу:
http://www.cyberforum.ru/cgi-bin/latex.cgi?n=2:\\n\lg n=2\\2\lg 2=2\\2=2\\n={2}^{k}:\\{2}^{k}\lg {2}^{k}=2\frac{{2}^{k}}{2}\lg \frac{{2}^{k}}{2}+{2}^{k}\\k{2}^{k}=(k-1){2}^{k}+{2}^{k}\\k{2}^{k}={2}^{k}(k-1+1)\\k=k\\n={2}^{k+1}\\{2}^{k+1}\lg {2}^{k+1}={2}^{k+1}\lg \frac{{2}^{k+1}}{2}+{2}^{k+1}\\{2}^{k+1}\lg {2}^{k+1}={2}^{k+1}(\lg \frac{{2}^{k+1}}{2}+1)\\\lg {2}^{k+1}=\lg \frac{{2}^{k+1}}{2}+1\\k+1=k+1\\
0
17.04.2016, 09:41
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.04.2016, 09:41

Найти коэффициент рекуррентного соотношения
Помогите найти коэффициент рекуррентного соотношения.

Общее решение рекуррентного соотношения в случае,когда все корни характеристического многочлена различны?
Обыскал весь интернет нигде не могу найти ответ на данный вопрос.Помогите пожайлуста.

Доказательство принципа математической индукции
Из названия темы следует мой вопрос. Мне нужно понять как доказывалась мат. индукция (а не как...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru