Производящая функция

@AkinRUs · Регистрация: 29.11.2013

Студворк — интернет-сервис помощи студентам

Помогите пожалуйста решить данное рекуррентное соотношение с помощью производящей функции
Алгоритма построения производящей функции не понимаю(((

f(n+2)=2f(n)-f(n+1);f(1)=1,f(2)=2

zer0mail · 13.12.2013, 12:07

Разбирайся, кто мешает: http://www.genfunc.ru/theory/rsol/

@AkinRUs · 13.12.2013, 13:37 **[ТС]**

Мешает то,что тут нужно знание рядов) которые по матану мы будем проходить в следующем семестре.Правда препода по дискретеке это не волнует)

zer0mail · 13.12.2013, 14:19

Народная мудрость: "кто хочет - ищет способ, а кто не хочет - ищет причину"

Все что нужно знать для задачи о сравнении рядов - это то, что ряд A_nzⁿ = B_nzⁿ тогда, когда все A_n = B_n.

@Том Ардер · 13.12.2013, 15:20

Производящая функция:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?F(z)=\sum_{n=1}^{\infty}f(n){z}^{n}$

Тогда
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\sum_{n=1}^{\infty}f(n+1){z}^{n}=\frac{1}{z}\sum_{n=1}^{\infty}f(n+1){z}^{n+1}=\frac{1}{z}\sum_{k=2}^{\infty}f(k){z}^{k}=\frac{1}{z}\left(F(z)-f(1) z\right)$

С каждым слагаемым в исходном уравнении аналогично. Дальше немного элементарной алгебры, пригодится знание бесконечной геометрической прогрессии.
Sapienti sat.

@AkinRUs · 13.12.2013, 20:30 **[ТС]**

Спасибо огромное

iifat · 14.12.2013, 06:52

Сообщение от AkinRUs

Мешает то,что тут нужно знание рядов

Метод производящих функций весьма своеобразно понимает ряды. Скажем, сходимость нигде не доказывается. Так понимаю, идея примерно такова: если в результате пришли к сходящемуся ряду, значит, всё в порядке; а ежели нет, докажем по индукции. Это больше на уровне идеи: смотрим на рекуррентное соотношение — ну ничего не понятно. Поманипулировали с рядами — появилась формула. А доказать её куда проще, чем найти.
Всё, что надо знать про ряды — парочку (никак не больше десятка) стандартных разложений: $https://www.cyberforum.ru/cgi-bin/latex.cgi?(1+x)^n$ , $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac1{1-x}$ (частный случай, впрочем), $https://www.cyberforum.ru/cgi-bin/latex.cgi?e^x$ .

@Urnwestek · 14.12.2013, 20:04

Сообщение от iifat

если в результате пришли к сходящемуся ряду, значит, всё в порядке; а ежели нет, докажем по индукции.

Зачем?

Производящие функции — это просто кольцо над множеством последовательностей. Поэтому если мы, каким-либо образом пришли к выводу, что F(z) = G(z) то это значит, что F(z) = G(z) «покоэффициентно», т.е., что коэффициенты при соответствующих мономах равны. Про суммирование рядов и сходимость вообще речи нигде не идёт, а то что производящая функция по записи похожа на ряд — так это для удобства.

Сообщение от iifat

Это больше на уровне идеи

Доказательство с помощью производящих функций — вполне себе строгое.

iifat · 15.12.2013, 05:05

Скажем так, теории расходящихся рядов не встречал. Хотя что-то такое, признаюсь, слышал.
Если б это было "просто кольцо", нельзя было б просто писать, скажем, $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac1{1-x}=\sum\frac1{x^n}$ , это надо было бы доказывать отдельно. В теории сходящихся рядов это доказывается, при работе с производящими функциями просто берётся; но в производящих функциях, насколько знаю, ничто не мешает оперировать с рядом, к примеру, $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sum n!x^n$ , который не сходится нигде.

@rahim · 15.12.2013, 12:30

Сообщение от iifat

$https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac1{1-x}=\sum\frac1{x^n}$

Наверное, $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac1{1-x}=\sum{x^n}$ ?

iifat · 15.12.2013, 12:43

Сообщение от rahim

Наверное, $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac1{1-x}=\sum{x^n}$ ?

Ой.

@Urnwestek · 15.12.2013, 17:59

То что $https://www.cyberforum.ru/cgi-bin/latex.cgi?(1-x)^{-1} = \sum x^n$ и доказывается отдельно. А именно — умножением $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sum x^n$ на $https://www.cyberforum.ru/cgi-bin/latex.cgi?1-x$ и получением единицы.
Производящая функция — это не расходящийся ряд, это вообще не ряд, это последовательность.
Сумму последовательностей $https://www.cyberforum.ru/cgi-bin/latex.cgi?a_n$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?b_n$ определили как $https://www.cyberforum.ru/cgi-bin/latex.cgi?c_n=a_n+b_n$
А произведение последовательностей $https://www.cyberforum.ru/cgi-bin/latex.cgi?a_n$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?b_n$ определили как $https://www.cyberforum.ru/cgi-bin/latex.cgi?c_n = \sum\limits_{k=0}^n C_n^k a_k b_{n-k}$
Полученное множество последовательностей с определенной таким образом операциями сложения и умножения обозначается как $https://www.cyberforum.ru/cgi-bin/latex.cgi?\mathbb{R}[[x]]$ .
Легко проверить, что $https://www.cyberforum.ru/cgi-bin/latex.cgi?\mathbb{R}[[x]]$ — коммутативное ассоциативное кольцо с единицей.
Поэтому когда пишут $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{1}{1-x}$ — то имеется в виду «обратный по умножению к 1-x».
Легко доказать, что в $https://www.cyberforum.ru/cgi-bin/latex.cgi?\mathbb{R}[[x]]$ обратимы те и только те последовательности, у которых $https://www.cyberforum.ru/cgi-bin/latex.cgi?a_0 \neq 0$ .

Всё. Нигде нету никакого упоминания не о сходимости, не о рядах, это чисто алгебраическая конструкция (её ещё иногда наделяют топологией, но в самом простом случае об этом речи не идёт).

Определенную связь производящих функций с рядами даёт метод суммирования рядов по Абелю. Ряд $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sum_{k=0}^{\infty} a_k$ называется суммируемым по Абелю, если существует предел $https://www.cyberforum.ru/cgi-bin/latex.cgi?\lim\limits_{t \to 1 - 0}\sum_{k=0}^{\infty} t^k a_k$ который называется значением суммы ряда в смысле Абеля.
Легко проверить, что:
1) Если ряд суммируем в обычном смысле, то он суммируем и по Абелю. При этом значние суммы ряда в смысле Абеля совпадает со значением суммы ряда в обычном смысле.
2) Если ряды $https://www.cyberforum.ru/cgi-bin/latex.cgi?a_n$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?b_n$ суммируемы по Абелю, то ряд $https://www.cyberforum.ru/cgi-bin/latex.cgi?c_n = a_n+b_n$ тоже суммируем по Абелю. При этом значение суммы ряда $https://www.cyberforum.ru/cgi-bin/latex.cgi?c_n$ в смысле Абеля равно сумме значений рядов $https://www.cyberforum.ru/cgi-bin/latex.cgi?a_n$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?b_n$ в смысле Абеля.
3) Если ряды $https://www.cyberforum.ru/cgi-bin/latex.cgi?a_n$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?b_n$ суммируемы по Абелю, то ряд $https://www.cyberforum.ru/cgi-bin/latex.cgi?c_n = \sum\limits_{k=0}^n C_n^k a_k b_{n-k}$ суммируем по Абелю. При этом значение суммы ряда $https://www.cyberforum.ru/cgi-bin/latex.cgi?c_n$ в смысле Абеля равно произведению значений сумм рядов $https://www.cyberforum.ru/cgi-bin/latex.cgi?a_n$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?b_n$ в смысле Абеля.
Исходя из 2 и 3 можно заключить, что кольцо рядов суммируемых по Абелю является подкольцом кольца производящих функций $https://www.cyberforum.ru/cgi-bin/latex.cgi?\mathbb{R}[[x]]$ поэтому работать с ними можно как с обычными производящими функциями.

Так что никакая это не «идея» а вполне себе стройная теория, но ТСу все эти заморочки с рядами не нужны, у него в стартовом посте вообще никаких рядов нету, только последовательность.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@AkinRUs 0 / 0 / 0 Регистрация: 29.11.2013 Сообщений: 28

	Производящая функция 13.12.2013, 00:34. Показов 2834. Ответов 11 Метки нет (Все метки) Помогите пожалуйста решить данное рекуррентное соотношение с помощью производящей функции Алгоритма построения производящей функции не понимаю((( f(n+2)=2f(n)-f(n+1);f(1)=1,f(2)=2 0

zer0mail 2688 / 2260 / 244 Регистрация: 03.07.2012 Сообщений: 8,231 Записей в блоге: 1
	13.12.2013, 12:07
	Разбирайся, кто мешает: http://www.genfunc.ru/theory/rsol/ 0

@AkinRUs 0 / 0 / 0 Регистрация: 29.11.2013 Сообщений: 28
	13.12.2013, 13:37 [ТС]
	Мешает то,что тут нужно знание рядов) которые по матану мы будем проходить в следующем семестре.Правда препода по дискретеке это не волнует) 0

zer0mail 2688 / 2260 / 244 Регистрация: 03.07.2012 Сообщений: 8,231 Записей в блоге: 1
	13.12.2013, 14:19
	Народная мудрость: "кто хочет - ищет способ, а кто не хочет - ищет причину" Все что нужно знать для задачи о сравнении рядов - это то, что ряд A_nzⁿ = B_nzⁿ тогда, когда все A_n = B_n. 0

@Том Ардер $Эксперт по математике/физике$ 4218 / 3418 / 396 Регистрация: 15.06.2009 Сообщений: 5,818
	13.12.2013, 15:20
	Сообщение было отмечено как решение Решение Производящая функция: $https://www.cyberforum.ru/cgi-bin/latex.cgi?F(z)=\sum_{n=1}^{\infty}f(n){z}^{n}$ Тогда $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sum_{n=1}^{\infty}f(n+1){z}^{n}=\frac{1}{z}\sum_{n=1}^{\infty}f(n+1){z}^{n+1}=\frac{1}{z}\sum_{k=2}^{\infty}f(k){z}^{k}=\frac{1}{z}\left(F(z)-f(1) z\right)$ С каждым слагаемым в исходном уравнении аналогично. Дальше немного элементарной алгебры, пригодится знание бесконечной геометрической прогрессии. Sapienti sat. 1

@AkinRUs 0 / 0 / 0 Регистрация: 29.11.2013 Сообщений: 28
	13.12.2013, 20:30 [ТС]
	Спасибо огромное 0

iifat 2900 / 1934 / 209 Регистрация: 05.06.2011 Сообщений: 5,692
	15.12.2013, 05:05
	Скажем так, теории расходящихся рядов не встречал. Хотя что-то такое, признаюсь, слышал. Если б это было "просто кольцо", нельзя было б просто писать, скажем, $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac1{1-x}=\sum\frac1{x^n}$ , это надо было бы доказывать отдельно. В теории сходящихся рядов это доказывается, при работе с производящими функциями просто берётся; но в производящих функциях, насколько знаю, ничто не мешает оперировать с рядом, к примеру, $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sum n!x^n$ , который не сходится нигде. 0

@Urnwestek 268 / 126 / 6 Регистрация: 20.10.2013 Сообщений: 196
	15.12.2013, 17:59
	То что $https://www.cyberforum.ru/cgi-bin/latex.cgi?(1-x)^{-1} = \sum x^n$ и доказывается отдельно. А именно — умножением $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sum x^n$ на $https://www.cyberforum.ru/cgi-bin/latex.cgi?1-x$ и получением единицы. Производящая функция — это не расходящийся ряд, это вообще не ряд, это последовательность. Сумму последовательностей $https://www.cyberforum.ru/cgi-bin/latex.cgi?a_n$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?b_n$ определили как $https://www.cyberforum.ru/cgi-bin/latex.cgi?c_n=a_n+b_n$ А произведение последовательностей $https://www.cyberforum.ru/cgi-bin/latex.cgi?a_n$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?b_n$ определили как $https://www.cyberforum.ru/cgi-bin/latex.cgi?c_n = \sum\limits_{k=0}^n C_n^k a_k b_{n-k}$ Полученное множество последовательностей с определенной таким образом операциями сложения и умножения обозначается как $https://www.cyberforum.ru/cgi-bin/latex.cgi?\mathbb{R}[[x]]$ . Легко проверить, что $https://www.cyberforum.ru/cgi-bin/latex.cgi?\mathbb{R}[[x]]$ — коммутативное ассоциативное кольцо с единицей. Поэтому когда пишут $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{1}{1-x}$ — то имеется в виду «обратный по умножению к 1-x». Легко доказать, что в $https://www.cyberforum.ru/cgi-bin/latex.cgi?\mathbb{R}[[x]]$ обратимы те и только те последовательности, у которых $https://www.cyberforum.ru/cgi-bin/latex.cgi?a_0 \neq 0$ . Всё. Нигде нету никакого упоминания не о сходимости, не о рядах, это чисто алгебраическая конструкция (её ещё иногда наделяют топологией, но в самом простом случае об этом речи не идёт). Определенную связь производящих функций с рядами даёт метод суммирования рядов по Абелю. Ряд $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sum_{k=0}^{\infty} a_k$ называется суммируемым по Абелю, если существует предел $https://www.cyberforum.ru/cgi-bin/latex.cgi?\lim\limits_{t \to 1 - 0}\sum_{k=0}^{\infty} t^k a_k$ который называется значением суммы ряда в смысле Абеля. Легко проверить, что: 1) Если ряд суммируем в обычном смысле, то он суммируем и по Абелю. При этом значние суммы ряда в смысле Абеля совпадает со значением суммы ряда в обычном смысле. 2) Если ряды $https://www.cyberforum.ru/cgi-bin/latex.cgi?a_n$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?b_n$ суммируемы по Абелю, то ряд $https://www.cyberforum.ru/cgi-bin/latex.cgi?c_n = a_n+b_n$ тоже суммируем по Абелю. При этом значение суммы ряда $https://www.cyberforum.ru/cgi-bin/latex.cgi?c_n$ в смысле Абеля равно сумме значений рядов $https://www.cyberforum.ru/cgi-bin/latex.cgi?a_n$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?b_n$ в смысле Абеля. 3) Если ряды $https://www.cyberforum.ru/cgi-bin/latex.cgi?a_n$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?b_n$ суммируемы по Абелю, то ряд $https://www.cyberforum.ru/cgi-bin/latex.cgi?c_n = \sum\limits_{k=0}^n C_n^k a_k b_{n-k}$ суммируем по Абелю. При этом значение суммы ряда $https://www.cyberforum.ru/cgi-bin/latex.cgi?c_n$ в смысле Абеля равно произведению значений сумм рядов $https://www.cyberforum.ru/cgi-bin/latex.cgi?a_n$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?b_n$ в смысле Абеля. Исходя из 2 и 3 можно заключить, что кольцо рядов суммируемых по Абелю является подкольцом кольца производящих функций $https://www.cyberforum.ru/cgi-bin/latex.cgi?\mathbb{R}[[x]]$ поэтому работать с ними можно как с обычными производящими функциями. Так что никакая это не «идея» а вполне себе стройная теория, но ТСу все эти заморочки с рядами не нужны, у него в стартовом посте вообще никаких рядов нету, только последовательность. 1

Производящая функция

Решение