Метод рекурентних співвідношень визначник. Т. зв. Матицина дискретна математика розв'язання рекурентних співвідношень. практикум. Розміщення без повторень

Рекурентним співвідношенням, рекурентним рівняннямабо рекурентною формулоюназивається співвідношення виду, яке дозволяє обчислювати всі члени послідовності
якщо задані її перші kчленів.

1. Формула
задає арифметичну прогресію.

2. Формула
визначає геометричну прогресію.

3. Формула
задає послідовність чисел Фібоначчі.

У разі, коли рекурентне співвідношення лінійне та однорідне, тобто виконується співвідношення виду

(p= Const), послідовність
називається зворотної. Багаточлен

називається характеристичнимдля зворотної послідовності
. Коріння багаточлена
називаються характеристичними.

Безліч всіх послідовностей, що задовольняють даному рекурентному співвідношенню, називається загальним рівнянням.

Опис загального рівняння співвідношення (1) має аналоги з описом рішення звичайного диференціального рівняння постійними коефіцієнтами.

Теорема 1. 1. Нехай- Корінь характеристичного багаточлена (2). Тоді послідовність
, деc- Довільна константа, задовольняє співвідношенню (1).

2. Якщо
- просте коріння характеристичного багаточлена (2), то загальне рішення рекурентного співвідношення (1) має вигляд, де
- Довільні константи.

3. Якщо- корінь кратності
характеристичного багаточлена (2), то загальне рішення рекурентного співвідношення (1) має вигляд
, де- Довільні константи.

Знаючи загальне рішення рекурентного рівняння (1), за початковими умовами,
можна знайти невизначені постійні і тим самим отримати рішення рівняння (1) з цими початковими умовами.

Приклад 2. Знайти послідовність
, що задовольняє рекурентне співвідношення
та початковим умовам
.

Коріння характеристичного багаточлена
є числа
. Отже, з теореми 3.1. загальне рішення має вигляд
. Використовуючи початкові умови, отримуємо систему

вирішуючи яку, знаходимо
і
. Таким чином,
.

Розглянемо неоднорідне лінійне рекурентне рівняння

Нехай
- загальне рішення однорідного рівняння (1), а
- приватне(конкретне) Рішеннянеоднорідного рівняння (3). Тоді послідовність
утворює загальне рішення рівняння (3), і цим справедлива.

Теорема 2.Загальне рішення неоднорідного лінійного рекурентного рівняння подається як суми загального рішення відповідного однорідного лінійного рекурентного рівняння і деякого окремого рішення неоднорідного рівняння.

Таким чином, в силу теореми 1. Завдання знаходження загального рішення рекурентного рівняння (3) зводиться до знаходження деякого приватного рішення.

В окремих випадках є загальні рецепти знаходження загального рішення.

Якщо
(де ) не є характеристичним коренем, то підставляючи
в (3), отримуємо і звідси
, тобто приватне рішення можна задати формулою
.

Нехай
- багаточлен ступеня rвід змінної n, і число 1 не є характерним коренем. Тоді і приватне рішення слід шукати у вигляді
. Підставляючи багаточлени у формулу (3), отримуємо

Порівнюючи коефіцієнти в лівій та правій частинах останньої рівності, отримуємо співвідношення чисел , що дозволяють ці цифри визначити.

приклад. Знайти рішення рівняння

(4)

з початковою умовою
.

Розглянемо характеристичний багаточлен
. Так як
та права частина
рівняння (3) дорівнює n+1, то приватне рішення шукатимемо у вигляді
. Підставляючи рівняння (4), отримуємо . Прирівнюючи коефіцієнти у лівій та правій частинах останньої рівності, отримуємо систему

звідки знаходимо
. Таким чином, приватне рішення рівняння (4) має вигляд
. По теоремі 3.1. загальне рішення однорідного рівняння
задається формулою
, та за теоремою 3.2. отримуємо загальне рішення рівняння (4):
. З початкової умови
знаходимо
, тобто. . Таким чином,
.

Числа Фібоначчі.

При вирішенні багатьох комбінаторних задач застосовують метод зведення даної задачі до задачі, що стосується меншої кількості елементів. Наприклад, можна вивести формулу для числа перестановок:

Звідси видно, що може бути зведений до факторіалу від меншого числа.

Хорошою ілюстрацією до побудови рекурентних співвідношень є завдання Фібоначчі. У своїй книзі в 1202 р. італійський математик Фібоначчі навів таке завдання. Пара кроликів приносить приплід раз на місяць двох кроленят (самку і самця), причому новонароджені кроленята через два місяці після народження самі приносять приплід. Скільки кроликів з'явиться за рік, якщо на початку була одна пара кроликів.

З умови завдання випливає, що через місяць буде дві пари кроликів, через два місяці приплід дасть тільки перша пара кроликів, що з'явилися два місяці тому, тому всього буде 3 пари кроликів. Ще за місяць буде вже 5 пар. І так далі.

Позначимо через кількість пар кроликів після місяців з початку року. Тоді за місяць кількість пар кроликів можна знайти за формулою:

Ця залежність називається рекурентним співвідношенням . Слово "рекурсія" означає повернення назад (у нашому випадку – повернення до попередніх результатів).

За умовою, і тоді по співвідношенню маємо: , , і т.д., .

Визначення 1:Числа називаються числами Фібоначчі . Це відома в математиці послідовність чисел:

1, 1, 2, 3, 5, 8, 13, 21, ...

У цій послідовності кожне наступне число є сумою двох попередніх чисел. І в рекурентному співвідношенні також наступний член перебуває як сума двох попередніх членів.

Встановимо зв'язок між числами Фібоначчі та комбінаторним завданням. Нехай потрібно знайти число - послідовностей, що складаються з нулів та одиниць, у яких жодні дві одиниці не стоять поспіль.

Візьмемо будь-яку таку послідовність і зіставимо їй пару кроликів за таким правилом: одиницям відповідають місяці появи на світ однієї з пар «предків» цієї пари (включаючи і вихідну), а нулями – всі інші місяці. Наприклад, послідовність встановлює таку «генеалогію» – сама пара з'явилася наприкінці 11-го місяця, її батьки наприкінці 7-го місяця, «дід» – наприкінці 5-го місяця, та «прадід» наприкінці 2-го місяця. Початкова пара шифрується послідовністю. У жодній послідовності дві одиниці не можуть стояти поспіль – пара, що тільки-но з'явилася, не може принести приплід через місяць. Очевидно, різним послідовностям відповідають різні пари та назад.

Таким чином, число послідовностей із зазначеними властивостями дорівнює .

Теорема 1:Число перебуває як сума біномних коефіцієнтів: . Якщо – непарно, то . Якщо – парно, то . Інакше: - ціла частина числа.

Доведення:Справді, - число всіх послідовностей із 0 і 1, у яких жодні дві одиниці не стоять поряд. Число таких послідовностей, що містять рівно одиниць і нулів, дорівнює при цьому тоді змінюється від 0 до . Застосовуючи правило суми, отримуємо цю суму.

Цю рівність можна довести інакше. Позначимо:

З рівності слід, що . Крім цього, ясно, що і . Так як обидві послідовності і задовольняють рекурентному співвідношенню, то і.

Визначення 2:Рекурентне співвідношення має порядок якщо воно дозволяє обчислювати через попередніх членів послідовності: .

Наприклад, - рекурентне співвідношення другого порядку, а рекурентне співвідношення 3-го порядку. Співвідношення Фібоначчі є співвідношенням другого порядку.

Визначення 3: Рішеннямрекурентного співвідношення є послідовність, що задовольняє цьому співвідношенню.

Якщо задано рекурентне співвідношення ‑ го порядку, йому задовольняють нескінченно багато послідовностей, т.к. Перші елементи можна задати довільно. Але якщо перші елементи задані, інші члени визначаються однозначно.

Наприклад, співвідношення Фібоначчі крім розглянутої вище послідовності 1, 1, 2, 3, 5, 8, 13, 21, ..., можуть задовольняти також інші послідовності. Наприклад, послідовність 2, 2, 4, 8, 12,... будується за тим самим принципом. Але якщо задати початкові члени (їх у послідовності Фібоначчі – 2), то рішення визначається однозначно. Початкових членів беруть стільки, який порядок співвідношення.

За відомими рекурентними співвідношеннями та початковими членами можна виписувати члени послідовності один за одним і таким шляхом ми можемо отримати будь-який її член. Але в багатьох випадках нам не потрібні всі попередні члени, а потрібен один певний член. У цьому випадку зручніше мати формулу - члена послідовності.

Ми будемо говорити, що деяка послідовність є рішенням цього рекурентного співвідношення, якщо під час встановлення цієї послідовності співвідношення тотожно виконується.

Наприклад, послідовність одна із рішень співвідношення: . Це легко перевірити звичайною підстановкою.

Визначення 4:Рішення рекурентного співвідношення - го порядку називається загальним якщо воно залежить від довільних постійних , змінюючи які, можна отримати будь-яке рішення даного співвідношення.

Наприклад, для співвідношення загальним рішення буде .

Насправді легко перевіряється, що воно буде рішенням нашого співвідношення. Покажемо, що будь-яке рішення можна отримати у такому вигляді. Нехай і – довільні.

Тоді знайдуться такі і, що

Очевидно, для будь-яких систем рівнянь має єдине рішення.

Визначення 5:Рекурентне співвідношення називається лінійним якщо воно записується у вигляді:

де – числові коефіцієнти.

Для вирішення довільних рекурентних співвідношень загальних правил, взагалі кажучи, немає. Однак для вирішення лінійних рекурентних співвідношень є загальні правила рішення.

Розглянемо спочатку співвідношення 2-го порядку.

Рішення цього співвідношення ґрунтується на наступних твердженнях.

Теорема 2:Якщо і є рішенням даного рекурентного співвідношення 2-го порядку, то для будь-яких чисел і послідовність також є рішенням цього співвідношення.

Теорема 3:Якщо число є коренем квадратного рівняння, то послідовність є розв'язком рекурентного співвідношення.

З теорем 2, 3 випливає наступне правило вирішення лінійних рекурентних співвідношень 2-го порядку.

Нехай дано рекурентне співвідношення.

1) Складемо квадратне рівняння, яке називається характеристичним для цього співвідношення. Знайдемо Усекоріння цього рівняння (навіть кратні та комплексні).

2) Складемо загальне рішення рекурентного співвідношення. Його структура залежить від виду коренів (однакові вони чи різні).

а) Якщо це співвідношення має два різних кореняі , то загальне рішення співвідношення має вигляд .

Справді, з теорем 2, 3 слід, що - рішення та система рівнянь

Має єдине рішення, т.к. за умови .

Наприклад, для чисел Фібоначчі маємо . Характеристичне рівняння має вигляд: . Вирішуючи останнє рівняння, отримаємо коріння:, .

Якщо всі коріння характеристичного рівняння різні, то загальне рішення має вигляд: .

Якщо ж, наприклад, то цьому кореню відповідають рішення:

даного рекурентного співвідношення. У загальному рішенні цьому кореню відповідає частина.

Наприкладвирішуючи рекурентне співвідношення:

складаємо характеристичне рівняння виду: .

Його коріння,. Тож спільне рішення є.

Комбінаторні обчислення на кінцевих множинах

Введення у комбінаторику

Предметом теорії комбінаторних алгоритмів, що часто називають комбінаторними обчисленнями, є обчислення на дискретних математичних структурах. У цій теорії велика увага приділяється алгоритмічному підходу до вирішення завдань дискретної математики, оптимізації перебору варіантів, скорочення числа розглянутих рішень.

Область комбінаторних алгоритмів включає завдання, які вимагають підрахунку (оцінювання) числа елементів у кінцевій множині або перерахування цих елементів у спеціальному порядку (додаток Б). У цьому широко застосовується процедура вибору елементів із поверненням та її варіанти.

Існують два види завдань підрахунку. У простому випадку задається конкретна множина і потрібно визначити точно кількість елементівв ньому. У випадку є сімейство множин, задане деяким параметром, і визначається потужність множини як функція параметра. При цьому часто буває достатньою оцінкою порядку функції, а іноді потрібно тільки оцінка швидкості її зростання. Наприклад, якщо потужність підлягає розгляду множини зростає за деяким параметром експоненційно, то цього може виявитися достатньо для того, щоб відмовитися від запропонованого підходу до вивчення проблеми, не займаючись різними деталями. До цього, більш загального, типу проблем застосовуються процедури асимптотичних розкладів, рекурентних співвідношень та функцій, що виробляють.

Асимптотика

Асимптота - особлива лінія (найчастіше пряма), що є граничною для кривої, що розглядається.

Асимптотика – це мистецтво оцінювання та порівняння швидкостей зростання функцій. Кажуть, що за х®¥ функція "поводиться, як х", або" зростає з такою ж швидкістю, як х", і при х®0 "поводиться як 1/ x". Кажуть, що "log xпри x®0 і будь-якому e>0 поводиться, як x e , і що за n®¥ росте не швидше, ніж n log nТакі неточні, але інтуїтивно ясні твердження корисні при порівнянні функцій так само, як і співвідношення<, £ и = при сравнивании чисел.

Визначимо три основні асимптотичні співвідношення.

Визначення 1.Функція f(x) еквівалентна g(x) при х® x 0, якщо тільки якщо =1.

У цьому випадку кажуть, що функція f(x) асимптотично дорівнює функції g(x) або що f(x) росте з такою ж швидкістю, як і g(x).

Визначення 2. f(x) = o ( g(x)) при x® x 0, якщо тільки якщо =0.

Кажуть, що при x® x 0 f(x) росте повільніше, ніж g(x), або що f(x) "є о-мале" від g(x).

Визначення 3 . f(x)=Про( g(x)) при x® x 0, якщо тільки якщо існує константа З така, що sup =С.

У цьому випадку кажуть, що f(x) росте не швидше, ніж g(x), або що за x® x 0 f(x) "є О-велике" від g(x).

Співвідношення f(x)=g(x)+o(h(x)) при x®¥ означає, що f(x)-g(x)=o(h(x)). Аналогічно f(x)=g(x)+Про(h(x)) означає, що f(x)-g(x)=О(h(x)).

Вирази О(·) та про(·) можуть використовуватися також і в нерівностях. Наприклад, нерівність x+o(x)£2 xпри x®0 означає, що для будь-якої функції f(x) такий, що f(x)=o(x), при x®¥ має місце співвідношення x+f(x)£2 xдля всіх досить великих значень х.

Наведемо деякі корисні асимптотичні рівність.

Поліном асимптотично дорівнює своєму старшому члену:

при x®¥; (4.1)

при x®¥; (4.2)

при x®¥ та a k¹0. (4.3)

Суми ступенів цілих чисел задовольняють співвідношення:

при n®¥. (4.4)

Звідси, зокрема, маємо при n®¥

У більш загальному випадку при n®¥ і для будь-якого цілого k³0

; (4.6)

. (4.7)

Рекурентні співвідношення

Поняття рекурентних співвідношень проілюструємо на класичній проблемі, поставленій та вивченій Фібоначчі близько 1200 року.

Фібоначчі поставив свою проблему у формі розповіді про швидкість зростання популяції кроликів за таких припущень. Все починається з однієї пари кролів. Кожна пара кроликів стає фертильною (fertile – плідний) через місяць, після чого кожна пара народжує нову пару кроликів щомісяця. Кролики ніколи не вмирають, і їхнє відтворення ніколи не припиняється. Нехай F n- Число пар кроликів у популяції після проходження nмісяців і нехай ця популяція складається з N nпар приплоду та O n"старих" пар, тобто. F n = N n + O n. Таким чином, у черговому місяці відбудуться наступні події:

Стара популяція в ( n+1)-й момент збільшиться на кількість народжених на момент часу n, тобто. O n+1 = O n + N n= F n;

Кожна стара в момент часу nпара виробляє в момент часу ( n+1) пару приплоду, тобто. N n+1= C n.

Наступного місяця ця картина повторюється:

O n+2 = O n+1+ N n+1= F n+1,

N n+2=O n+1;

об'єднавши ці рівності, отримаємо рекурентне співвідношення Фібонначі:

O n+2 + N n+2=F n+1 + O n+1,

F n+2 = F n+1 + F n. (4.8)

Вибір початкових умов для послідовності чисел Фібоначчі не є важливим; суттєві властивості цієї послідовності визначаються рекурентним співвідношенням (4.8). Зазвичай вважають F 0=0, F 1=1 (іноді вважають F 0=F 1=1).

Рекурентне співвідношення (4.8) є окремим випадком однорідних лінійних рекурентних співвідношень з постійними коефіцієнтами:

x n = a 1 x n-1 + a 2 x n-2 + ... ak x n-k , (4.9)

де коефіцієнти a iне залежать від nі x 1, x 2, …, x kвважаються заданими.

Існує загальний спосіб вирішення (тобто. відшукання x nяк функції n) лінійних рекурентних співвідношень із постійними коефіцієнтами. Цей метод розглянемо з прикладу співвідношення (4.8). Знайдемо рішення у вигляді

F n=cr n (4.10)

з постійними зі r. Підставляючи цей вираз у (4.8), отримаємо

cr n + 2 = cr n+ 1 + cr n,

cr n(r n -r-1)=0. (4.11)

Це означає, що F n=cr nє рішенням, якщо або з=0, або r= 0 (і звідси F n =0 для всіх n), а також (і це цікавіший випадок) якщо r 2 - r -1=0, причому константа здовільна. Тоді з (4.11) випливає

r= або r = . (4.12)

Число »1,618 відоме як "золотий" переріз, оскільки з давніх часів вважається, що трикутник (прямокутник) зі сторонами 1 і має найбільш приємні для ока пропорції.

Сума двох рішень однорідного лінійного рекурентного співвідношення, очевидно, також є рішенням, і насправді можна показати, що загальне рішення послідовності Фібоначчі має вигляд

F n= , (4.13)

де константи зі с’визначаються початковими умовами. Поклавши F 0 =0 і F 1 =1, отримаємо таку систему лінійних рівнянь:

, (4.14)

рішення якої дає

c = -c" = . (4.15)

Транскрипт

1 МІНІСТЕРСТВО ОСВІТИ І НАУКИ РОСІЙСЬКОЇ ФЕДЕРАЦІЇ Костромський державний університет імені М. А. Некрасова Т. Н. Матицина ДИСКРЕТНА МАТЕМАТИКА

2 ББК я73-5 М348 Друкується за рішенням редакційно-видавничої ради КМУ ім. Н. А. Некрасова Рецензент А. В. Череднікова, кандидат фізико-математичних наук, доцент М348 Матицина Т. Н. Дискретна математика. Вирішення рекурентних співвідношень: практикум [Текст] / Т. Н. Матицина. Кострома: КДУ ім. Н. А. Некрасова, с. Практикум містить індивідуальні завдання для студентів та призначений для забезпечення самостійної роботи з освоєння першої частини курсу «Дискретна математика». Для студентів 2-3 курси фізико-математичного факультету, які навчаються за спеціальностями «Математика» з додатковою спеціальністю «Інформатика», «Інформатика» з додатковою спеціальністю «Математика». ББК я73-5 Т. Н. Матицина, 2010 КМУ ім. Н. А. Некрасова,

3 ЗМІСТ Вступ Методичні рекомендації щодо вирішення лінійних рекурентних співвідношень Основні поняття та визначення рекурентних (поворотних) послідовностей Алгоритми рішення ЛОРС та ЛРС Приклади рішення ЛОРС та ЛРС Завдання для самостійного вирішення Завдання для вирішення ЛОРС та ЛРС Відповіді Висновок Бібліографічний

4 ВСТУП Перша частина курсу «Дискретна математика», що вивчається студентами 2 3 курсів фізико-математичного факультету, які навчаються за спеціальностями «Інформатика» з додатковою спеціальністю «Математика» (IV семестр) та «Математика» з додатковою спеціальністю «Інформатика» (V , передбачає рішення рекурентних співвідношень В даний видання включені завдання на обчислення однорідних та неоднорідних лінійних рекурентних співвідношень. Приводом для написання практикуму стала та обставина, що студенти практично не мають навичок вирішення завдань з даного курсу. Однією з причин є відсутність доступного підручника чи збірника завдань. Завдання із запропонованого практикуму допоможуть кожному зі студентів (індивідуально) розібратися з основними методами та прийомами вирішення завдань. З метою легшого освоєння матеріалу на початку посібника розглянуто всі типи завдань, що пропонуються для самостійного вирішення. Наприкінці розміщено список рекомендованої літератури, яка допоможе глибше вивчити цей предмет. Тема «Рекурентні співвідношення» близька до шкільного курсу (арифметичні та геометричні прогресії, послідовність квадратів і кубів натуральних чисел тощо), тому не вимагає від студентів попереднього вивчення будь-яких інших дисциплін. Основи теорії рекурентних співвідношень (поворотних послідовностей) були розроблені та опубліковані в 20-х роках. XVIII ст. французьким математиком А. Муавром та одним із перших за часом членів Петербурзької Академії наук швейцарським математиком Д. Бернуллі. Розгорнуту теорію дав найбільший математик XVIII ст. 4

5 петербурзький академік Л. Ейлер. З пізніших робіт слід виділити виклад теорії зворотних послідовностей у курсах обчислення кінцевих різниць, читаних знаменитими російськими математиками академіками П. Л. Чебишевим та А. А. Марковим. Рекурентні співвідношення (від латинського слова recurrere повертатися) відіграють велику роль дискретної математики, будучи сутнісно у певному сенсі дискретним аналогом диференціальних рівнянь. Крім того, вони дозволяють зводити це завдання від параметрів до задачі від 1 параметрів, потім до завдання від 2 параметрів і т. д. Послідовно зменшуючи число параметрів, можна дійти до завдання, яке вже легко вирішити. Поняття рекурентного співвідношення (поворотної послідовності) є широким узагальненням поняття арифметичної чи геометричної прогресії. Як окремі випадки воно охоплює також послідовності квадратів або кубів натуральних чисел, послідовності цифр десяткового розкладання раціонального числа (і взагалі будь-які періодичні послідовності), послідовності коефіцієнтів приватного від поділу двох багаточленів, розташованих за зростаючими ступенями х, і т.д.

6 1. МЕТОДИЧНІ РЕКОМЕНДАЦІЇ З РІШЕННЯ ЛІНІЙНИХ РЕКУРРЕНТНИХ СПІВВІДНОШЕНЬ 1.1. Основні поняття та визначення рекурентних (поворотних) послідовностей Записуватимемо послідовності у вигляді a 1, a 2, a 3, a, (1) або, коротко, (a ). Якщо існує натуральне число k та числа α 1, α 2, α k (дійсні або уявні), такі, що, починаючи з деякого номера та для всіх наступних номерів, a +k = α 1 a +k 1 + α 2 a + k α k a, (k 1), (2) то послідовність (1) називається рекурентною (поворотною) послідовністю порядку k, а співвідношення (2) рекурентним (поворотним) рівнянням порядку k. Таким чином, рекурентна послідовність характеризується тим, що кожен її член (починаючи з деякого з них) виражається через те саме кількість k безпосередньо попередніх йому членів за формулою (2). Сама назва "рекурентна" (а також зворотна) вживається саме тому, що тут для обчислення наступного члена повертаються до попередніх членів. Наведемо кілька прикладів рекурентних послідовностей. Приклад 1. Геометрична прогресія. Нехай маємо геометричну прогресію: a 1 = α, a 2 = α q, a 3 = α q 2, a = α q 1, ; (3) для неї рівняння (2) набуває вигляду: a +1 = q a. (4) 6

7 Тут k = 1 та α 1 = q. Таким чином, геометрична прогресія є рекурентною послідовністю першого порядку. Приклад 2. Арифметична прогресія. У разі арифметичної прогресії a 1 = α, a 2 = α + d, a 3 = α + 2d, a = α + (1)d, маємо a +1 = a + d співвідношення, яке не має виду рівняння (2). Однак якщо ми розглянемо два співвідношення, написані для двох сусідніх значень: a +2 = a +1 + d і a +1 = a + d, то отримаємо їх шляхом почленного віднімання a +2 a +1 = a +1 a, або a +2 = 2a +1 a рівняння виду (2). Тут k = 2, α 1 = 2, α 2 = 1. Отже, арифметична прогресія є рекурентною послідовністю другого порядку. Приклад 3. Розглянемо старовинне завдання Фібоначчі 1 про кількість кроликів. У ній потрібно визначити кількість пар зрілих кроликів, що утворилися від однієї пари протягом року, якщо відомо, що кожна зріла пара кроликів щомісяця народжує нову пару, причому новонароджені досягають повної зрілості протягом місяця. У цьому завдання цікавий аж ніяк не результат, отримати який зовсім неважко, але послідовність, члени якої виражають загальну кількість зрілих пар кроликів у початковий момент (a 1) через місяць (a 2), через два місяці (a 3) і, взагалі, через місяців (a+1). Очевидно, що a 1 = 1. Через місяць додасться пара новонароджених, але кількість зрілих пар буде колишня: a 2 = 1. Через два місяці кроленята досягнуть зрілості і загальна кількість зрілих пар дорівнюватиме двом: a 3 = 2. Нехай ми вирахували вже кількість 1 Фібоначчі, або Леонардо Пізанський, італійський середньовічний математик (близько 1200 р.) залишив після себе книгу «Про абак», що містить великі арифметичні та алгебраїчні відомості, запозичені у народів Середньої Азії та візантійців та творчо ним переробка. 7

8 зрілих пар через 1 місяць a і через місяць a +1. Так як до цього часу раніше зрілих пар дадуть ще a пар приплоду, то через + 1 місяців загальна кількість зрілих пар буде: a +2 = a +1 + a. (6) Звідси a 4 = a 3 + a 2 = 3, a 5 = a 4 + a 3 = 5, a 6 = a 5 + a 4 = 8, a 7 = a 6 + a 5 = 13,. Ми отримали таким чином послідовність a 1 = 1, a 2 = 1, a 3 = 2, a 4 = 3, a 5 = 5, a 6 = 8, a 7 = 13, a 13 = 233, (7) у якій кожен наступний член дорівнює сумі двох попередніх. Послідовність ця називається послідовністю Фібоначчі, а члени її числами Фібоначчі. Рівняння (6) показує, що послідовність Фібоначчі є рекурентною послідовністю другого порядку. Приклад 4. Як такий приклад розглянемо послідовність квадратів натуральних чисел: a 1 = 1 2, a 2 = 2 2, a 3 = 3 2, a = 2,. (8) Тут a +1 = (+ 1) 2 = і, отже, a +1 = a (9) Збільшуючи на одиницю, отримаємо: a +2 = a (10) І, отже (віднімаючи почленно (9) з (10)), a +2 a +1 = a +1 a + 2, або a +2 = 2a +1 a + 2. (11) Збільшуючи у рівності (11) на одиницю, матимемо: a +3 = 2a +2 a; (12) звідки (віднімаючи почленно (11) з (12)) a +3 a +2 = 2a +2 3a +1 + a, 8

9 або a+3 = 3a +2 3a +1 + a. (13) Ми отримали рекурентне рівняння третього порядку. Отже, послідовність (8) є рекурентною послідовністю третього порядку. Приклад 5. Розглянемо послідовність кубів натуральних чисел: a 1 = 1 3, a 2 = 2 3, a 3 = 3 3, a = 3,. (14) Так само, як у прикладі 4, можна переконатися, що послідовність кубів натуральних чисел є рекурентна послідовність четвертого порядку. Члени її задовольняють рівняння a +4 = 4a +3 6a a +1 a. (15) У разі найпростіших рекурентних послідовностей, наприклад, арифметичної та геометричної прогресій, послідовності квадратів або кубів натуральних чисел, ми можемо знаходити будь-який член послідовності, не вдаючись до обчислення попередніх членів. У разі ж послідовності чисел Фібоначчі ми, на перший погляд, не маємо можливості для цього і, щоб обчислити тринадцяте число Фібоначчі a 13, знаходимо попередньо один за одним усі попередні члени (користуючись рівнянням a +2 = a +1 + a ( 6)): a 1 = 1, a 2 = 1, a 3 = 2, a 4 = 3, a 5 = 5, a 6 = 8, a 7 = 13, a 8 = 21, a 9 = 34, a 10 = 55, a 11 = 89, a 12 = 144, a 13 = 233. У ході детального дослідження структури членів рекурентної послідовності можна отримати формули, що дозволяють обчислити в загальному випадку будь-який член рекурентної послідовності, не вдаючись до обчислення попередніх членів. Інакше кажучи, наступне завдання у тому, щоб знайти формулу -го члена послідовності, залежить тільки від номера. 9

10 Рекурентне співвідношення у загальному випадку може бути записане у вигляді a + k = F(, a + k 1, a + k 2, a), де F функція від k + 1 змінної, а число k називають порядком співвідношення. Рішенням рекурентного співвідношення називається числова послідовність b 1, b 2, b 3, b, для якої виконується рівність: b + k = F(, b + k 1, b + k 2, b) при будь-якому = 0, 1, 2, . Взагалі кажучи, довільне рекурентне співвідношення має безліч рішень. Наприклад, якщо розглянути рекурентне співвідношення другого порядку a +2 = a +1 + a, то йому, крім послідовності Фібоначчі: 1, 1, 2, 3, 5, 8, 13, 21, 34,..., що характеризується тим, що тут a 1 = a 2 = 1, задовольняє ще безліч інших послідовностей, що виходять при різному виборі значень a 1 і a 2. Так, наприклад, при a 1 = 3 і a 2 = 1 отримуємо послідовність: 3, 1, 2 , 1, 3, 4, 7, 11, 18, 29,. Щоб однозначно визначити рішення рекурентного співвідношення, необхідно задати початкові умови (початкових умов має бути рівно стільки, який порядок рекурентного співвідношення). Вирішити рекурентне співвідношення означає знайти формулу -го члена послідовності. На жаль, немає загального методу вирішення довільних рекурентних співвідношень. Винятком є ​​клас про лінійних рекурентних співвідношень з постійними коефіцієнтами. Рекурентне співвідношення виду a + k = α 1 a + k 1 + α 2 a + k α k a, де і деякі числа, i = 1, 2, k, називається лінійним однорідним рекурентним співвідношенням (ЛОРС) з постійними коефіцієнтами порядку k. 10

11 Рекурентне співвідношення виду a + k = α 1 a + k 1 + α 2 a + k α k a + f(), де a i деякі числа, i = 1, 2, k, f() 0 функція від, називається лінійним рекурентним співвідношенням (ЛРС) з постійними коефіцієнтами порядку k Алгоритми рішення ЛРС і ЛРС Алгоритм рішення ЛРС. Маємо ЛОРС: a + k = a 1 a + k 1 + a 2 a + k a k a. 1 крок. Кожному ЛОРС порядку k відповідає рівняння алгебри ступеня k з тими ж коефіцієнтами, і воно називається характеристичним рівнянням ЛОРС. Складаємо характеристичне рівняння x k = α 1 x k 1 + α 2 x k α k x 0 і знаходимо його коріння xi, де i = 1, k. 2 крок. Якщо x i коріння кратності 1 (тобто всі різні між собою), то загальне рішення ЛОРС має вигляд: a = c 1 (x 1) + c 2 (x 2) + c 3 (x 3) + + c k (x k ) = c i x i Якщо x i коріння кратності r i, то загальне рішення ЛОРС має вигляд k a = i= 1 (c 1 2 ri 1 i1 + ci2 + ci cir) (наприклад, якщо корінь x кратності 2, то a = (c 1 + c 2) х). i x i k i = 1 3 крок. Коефіцієнти i знаходяться за допомогою початкових умов. 11

12 Алгоритм рішення ЛРС. Маємо ЛРС: a + k = a 1 a + k 1 + a 2 a + k a + f (). Функцію f() можна подати у вигляді R m () λ, де R m () багаточлен ступеня m від змінної. Справді, наприклад: f() = 10 3= (10 3)1 = R 1 () 1, або f() = = (2 + 3) 3 = R 2 () 3. Перепишемо ЛРС у вигляді a + k α 1 a +k 1 α 2 a +k 2 α k a = R m () λ. 1 крок. Виписуємо відповідний ЛОРС: a + k α 1 a + k 1 α 2 a + k 2 α k a = 0 і знаходимо його загальне рішення. Для цього складаємо характеристичне рівняння x k α 1 x k 1 α 2 x k 2 α k x 0 = 0 і знаходимо його коріння x i, де i = 1, k. Нехай, наприклад, x i різне коріння, тоді загальне рішення відповідного ЛОРС має вигляд: a = c 1 (x 1) + c 2 (x 2) + c 3 (x 3) + c k (x k). 2 крок. Знаходимо a приватне рішення ЛРС: а) якщо λ не корінь характеристичного рівняння x k α 1 x k 1 α 2 x k 2 α k = 0, то a = Q m () λ, де Q m () багаточлен ступеня m від змінної; б) якщо λ корінь характеристичного рівняння x k α 1 x k 1 α 2 x k 2 α k = 0 кратності r, то a = r Q m () λ, де Q m () багаточлен ступеня m від змінної. Далі, підставляємо a у вихідне ЛРС і знаходимо коефіцієнти в многочлен Q m (). 12

13 3 крок. Знаходимо загальне рішення ЛРС, воно є сумою загального рішення відповідного ЛОРС a і ​​приватного рішення ЛРС a, тобто a = a + a. Коефіцієнти c i знаходяться за допомогою початкових умов Приклади рішення ЛОРС та ЛРС Користуючись наведеним алгоритмом знаходження рішення ЛОРС та ЛРС, розберемо декілька завдань. Завдання 1. Знайти рішення лінійного однорідного рекурентного співвідношення другого порядку: a +2 = 6 a +1 8 a, a 0 = 3, a 1 = Складаємо характеристичне рівняння x 2 = 6 x 8 x 0 і знаходимо його коріння. x 2 6x + 8 = 0; x 1 = 2, x 2 = 4 коріння різні, отже, їх кратність дорівнює Знаходимо загальне рішення ЛОРС: a = c 1 (x 1) + c 2 (x 2) = c c Оскільки задані початкові умови, то коефіцієнти c 1 і з 2 визначаються однозначно. a 0 = c c = c 1 + c 2 = 3; a 1 = c c = 2c 1 + 4c 2 = 4. Отримали систему: c1 + c2 = 3, 2c1 + 4c2 = 4. Вирішуючи її, знайдемо коефіцієнти: c 1 = 8, c 2 = 5. Таким чином, рішення ЛОРС має вид a = Завдання 2. Знайти рішення лінійного однорідного рекурентного співвідношення: 13

14 a +2 = 6 a +1 9 a, a 0 = 5, a 1 = Складаємо характеристичне рівняння x 2 = 6x 9 і знаходимо його коріння. x 2 6x + 9 = 0; (x3) 2 = 0; x 1 = x 2 = 3 два корені, при цьому x 1 і x 2 збіглися, отже, кратність кореня дорівнює Знаходимо загальне рішення ЛОРС: a = (c 1 + c 2) (x 1) = (c 1 + c 2) За допомогою початкових умов визначаємо коефіцієнти c1 та c2: a 0 = (c 1 + c 2 0) 3 0 = c 1 = 5; a 1 = (c 1 + c 2 1) 3 1 = (c 1 + c 2) 3 = 6. Отримали систему c1 = 5, c1 + c2 = 2. Вирішуючи її, знайдемо коефіцієнти c 1 = 5, c 2 = 3. Отже, рішення ЛОРС має вигляд: a = (5 3) 3. Зауваження. Як відомо, корінням квадратного рівняння можуть бути раціональні, ірраціональні, комплексні числа і т. п. Метод вирішення лінійних рекурентних співвідношень з таким корінням вирішується аналогічно. Завдання 3. Знайти рішення лінійного однорідного рекурентного співвідношення третього порядку: a +3 = 3 a a +1 8 a, a 0 = 9, a 1 = 9, a 2 = Складаємо характеристичне рівняння x 3 = 3 x x 8 і знаходимо його коріння. x 3 3x 2 6x + 8 = 0; (x 1) (x + 2) (x 4) = 0; x 1 = 1, x 2 = 2, x 3 = 4 коріння різні, отже, їх кратність дорівнює Знаходимо загальне рішення ЛОРС: a = c 1 (x 1) + c 2 (x 2) + c 3 (x 3) = c c 2 (2) + c

15 3. За допомогою початкових умов знаходимо коефіцієнти c 1 , c 2 і c 3. a 0 = c c 2 (2) 0 + c = c 1 + c 2 + c 3 = 9; a 1 = c c 2 (2) 1 + c = c 1 2c 2 + 4c 3 = 9; a 2 = c c 2 (2) 2 + c = c 1 + 4c c 3 = 9. c1 + c2 + ñ3 = 9, Вирішуючи систему c1 2c2 + 4c3 = 9, отримаємо c 1 = 7, c 2 = 4, c 3 = 2. Таким c1 + 4c2 + 16c3 = 9, таким чином, рішення ЛОРС має вигляд: a = (2) 2 4. Завдання 4. Знайти рішення лінійного однорідного рекурентного співвідношення третього порядку: a +3 = a a +1 3 a, a 0 = 6, a 1 = 15, a 2 = становимо характеристичне рівняння x 3 = x 2 + 5x 3 і знаходимо його коріння. x 3 + x 2 5x + 3 = 0; (x 1) 2 (x + 3) = 0; x 1 = x 2 = 1 корінь кратності 2; x 3 = 3 корінь кратності Знаходимо загальне рішення ЛОРС: a = (c 1 + c 2) (x 1) + c 3 (x 3) = (c 1 + c 2) 1 + c 3 (3). 3. За допомогою початкових умов знаходимо коефіцієнти c1, c2 та c3. a 0 = (c 1 + c 2 0) c 3 (3) 0 = c 1 + c 3 = 6; a 1 = (c 1 + c 2 1) c 3 (3) 1 = c 1 + c 2 3c 3 = 15; a 2 = (c 1 + c 2 2) c 3 (3) 2 = c 1 + 2c 2 + 9c 3 = 8. c1 + ñ3 = 6, Розв'язуючи систему c1 + c2 3c3 = 15, отримаємо c 1 = 8, c 2 = 1 і c 3 = 2. Таким c1 + 2c2 + 9c3 = 8, таким чином, рішення ЛОРС має вигляд: a = (8 +) 1 2 (3). 15

16 Завдання 5. Знайти рішення лінійного рекурентного співвідношення другого порядку: Перепишемо ЛРС як a +2 = 18 a a + 128, a 0 = 5, a 1 = 2. a a a = () 1. Виписуємо відповідний ЛОРС: a a a = 0. характеристичне рівняння та знаходимо його коріння. x 2 18x + 81 = 0; (x9) 2 = 0; x 1 = x 2 = 9 коріння характеристичного рівняння збіглося, отже, їх кратність дорівнює 2. Тоді загальне рішення a = (c 1 + c 2) (x 1) = (c 1 + c 2) Знаходимо a приватне рішення ЛРС. За умовою f() = R m () λ = = = R 0 () λ, де R 0 () = 128 багаточлен нульового ступеня від змінної, а λ = 1 не корінь характеристичного рівняння відповідного ЛОРС. Отже, a = Q m () λ = Q 0 () 1 де Q 0 () багаточлен нульового ступеня від змінної, в загальному вигляді Q 0 () = с. Таким чином, a = с 1. Далі, підставляємо a у вихідне ЛРС () і знаходимо коефіцієнт з багаточлен Q 0 (): с з с 1 = ; з 18с + 81с = 128; 64с = 128; с = 2. Отже, отримали a = с 1 = 2 1 = 2. 16

17 3. Знаходимо загальне рішення ЛРС, воно є сумою загального рішення відповідного ЛОРС a і ​​приватного рішення ЛРС a, тобто a = a + a = (c 1 + c 2) Залишилося за допомогою початкових умов знайти коефіцієнти c 1 і c 2. a 0 = (c 1 + c 2 0) = c = 5; a 1 = (c 1 + c 2 1) = 9c 1 + 9c = 2; Вирішуючи систему c1 + 2 = 5, 9c1 + 9c2 + 2 = 2, отримаємо c 1 = 3, c 2 = 3. Таким чином, рішення ЛРС має вигляд: a = (3 3) Завдання 6. Знайти рішення лінійного рекурентного співвідношення: a +2 = 10 a a , a 0 = 7, a 1 = 50. Перепишемо ЛРС у вигляді a a a = Виписуємо відповідний ЛОРС: a a a = 0; складаємо характеристичне рівняння та знаходимо його коріння. x 2 10 x + 25 = 0; (x5) 2 = 0; x 1 = x 2 = 5 корінь кратності 2. Тоді загальне рішення ЛОРС має вигляд: a = (c 1 + c 2) (x 1) = (c 1 + c 2) Знаходимо a приватне рішення ЛРС. За умовою f() = R m () λ = 50 5 = R 0 () λ, де R 0 () = 50 багаточлен нульового ступеня від змінної, а λ = 5 збігається з коренем x 1 кратності 2 характеристичного рівняння відповідного ЛОРС. Отже, a = r Q m () λ = = 2 Q 0 () 5, де Q 0 () = з багаточленом нульового ступеня від змінної. Таким чином, a = 2 з 5. Далі, підставляємо a у вихідне ЛРС і знаходимо коефіцієнт з: 17

18 с (+ 2) з (+ 1) з 2 5 = 50 5 (розділимо на 5 0); 25с (+2) 2 50с (+1) з 2 = 50; с() 2с() + с 2 = 2; с = 1. Отже, a = 2 з 5 = Виписуємо загальне рішення ЛРС: a = a + a = (c 1 + c 2) За допомогою початкових умов знаходимо коефіцієнти c 1 і c 2: a 0 = (c 1 + c 2 0) = c 1 = 7; a 1 = (c 1 + c 2 1) = 5c 1 + 5c = 50; Вирішуючи систему c1 = 7, c1 + c2 + 1 = 10, отримаємо c 1 = 7, c 2 = 2. Таким чином, рішення ЛРС має вигляд: a = (7 + 2) = () 5. Завдання 7. Знайти рішення лінійного рекурентного співвідношення: a +2 = 6 a +1 8 a , a 0 = 0, a 1 = 11. Перепишемо ЛРС у вигляді a +2 6 a a = Виписуємо відповідний ЛОРС: a +2 6 a a = 0; складаємо характеристичне рівняння та знаходимо його коріння. x 2 6x + 8 = 0; x 1 = 2, x 2 = 4 коріння кратності рівної 1. Тоді загальне рішення ЛОРС має вигляд a = c 1 (x 1) + c 2 (x 2) = c c Знаходимо a приватне рішення ЛРС. За умовою f() = R m () λ = = (3 + 2) 1 = R 1 () λ, де R 1 () = багаточлен першого ступеня від змінної, а λ = 1 не корінь характеристичного рівняння відповідного ЛОРС. Отже, a = Q m () λ = Q 1 () 1, де Q 1 () багаточлен першого ступеня від змінної, у загальному вигляді Q 1 () = = a + b. Таким чином, a = (a + b) 1. 18

19 a та b: Далі, підставляємо a у вихідне ЛРС і знаходимо коефіцієнти (a (+ 2) + b) (a (+ 1) + b) (a + b) 1 = 3 + 2; 25с (+2) 2 50с (+1) з 2 = 3 + 2; 3a + (3b 4a) = Таким чином, отримали, що два багаточлени рівні, а тоді рівні відповідні коефіцієнти: 3a = 3, a = 1, 3b 4a = 2 b = 2. Отже, a = (a + b) 1 = Виписуємо загальне рішення ЛРС: a = a + a = c c (+2). За допомогою початкових умов знаходимо коефіцієнти c 1 і c 2: a 0 = c c (0 + 2) = 0; a 1 = c c (1 + 2) = 11; Вирішуючи систему c1 + c2 = 2, 2c1 + 4c2 = 14, отримаємо c 1 = 3, c 2 = 5. Таким чином, рішення ЛРС має вигляд: a = Завдання 8. Знайти рішення лінійного рекурентного співвідношення: a +2 = 5 a +1 6 a + (10 4) 2, a 0 = 5, a 1 = 12. Перепишемо ЛРС у вигляді a +2 5 a a = (10 4) Виписуємо відповідний ЛОРС: a +2 5 a a = 0; складаємо характеристичне рівняння та знаходимо його коріння. x 2 5x + 6 = 0; x 1 = 3, x 2 = 2 коріння різних кратностей 1. Тоді загальне рішення ЛОРС має вигляд: a = c 1 (x 1) + c 2 (x 2) = c c

20 2. Знаходимо приватне рішення ЛРС. За умовою маємо, що f() = = R m () λ = (10 4) 2 = R 1 () λ, де R 1 () = (10 4) багаточлен першого ступеня від змінної, а λ = 2, то тобто збігається з коренем характеристичного рівняння відповідного ЛОРС. Отже, a = r Q m () λ = 1 Q 1 () 2, де Q 1 () багаточлен першого ступеня від змінної, у загальному вигляді Q 1 () = a + b. Таким чином, отримуємо a = = (a + b) 2. Далі, підставляємо a у вихідне співвідношення та знаходимо коефіцієнти a та b. (+ 2)(a (+ 2) + b) (+ 1) (a (+ 1) + b) (a + b) 2 = = (10 4) 2. Розділимо це рівняння на 2 0: 4(+ 2) (a (+ 2) + b) 10 (+ 1) (a (+ 1) + b) + 6 (a + b) = 10 4; 4a + (6a 2b) = Таким чином, отримали, що два багаточлени рівні, а тоді рівні відповідні коефіцієнти: 4a = 4, a = 1, 6a 2b = 10 b = 2. Отже, a = (a + b) 2 = (2) Виписуємо загальне рішення ЛРС, тобто a = a + a = c c (2) 2. За допомогою початкових умов знаходимо коефіцієнти c 1 і c 2. a 0 = c c (0 2) 2 0 = 5; a 1 = c c (1 2) 2 1 = 12. Вирішуючи систему c1 + c2 = 5, 3c1 + 2c2 = 14, отримаємо c 1 = 4, c 2 = 1. Таким чином, рішення ЛРС має вигляд: a = (2 ) 2 = () 2. 20

21 Завдання 9. Знайти рішення лінійного рекурентного співвідношення: a +2 = 8 a a , a 0 = 1, a 1 = 7. Перепишемо ЛРС у вигляді a +2 8 a a = () Виписуємо відповідний ЛОРС: a +2 8 a a = 0 ; складаємо характеристичне рівняння та знаходимо його коріння. x 2 8 x + 16 = 0; x 1 = x 2 = 4 коріння збіглося, отже, кратність кореня дорівнює 2. Тоді загальне рішення ЛОРС має вигляд: a = (c 1 + c 2) (x 1) = (c 1 + c 2) Знаходимо a приватне рішення ЛРС . За умовою f() = R m () λ = = () 1 = R 2 () λ, де R 2 () = багаточлен другого ступеня від змінної, а λ = 1 не збігається з коренем характеристичного рівняння відповідного ЛОРС. Отже, a = Q m () λ = Q 2 () 1, де Q 2 () багаточлен другого ступеня від змінної, у загальному вигляді Q 2 () = a 2 + b + c. Таким чином, a = = (a 2 + b + c) 1. Далі, підставляємо a у вихідне співвідношення і знаходимо коефіцієнти a, b та c. (a (+ 2) 2 + b (+ 2) + c) (a (+ 1) 2 + b (+ 1) + c) (a b + c) 1 = () 1; a(+ 2) 2 + b(+ 2)+ c 8a(+ 1) 2 8b(+ 1) 8c + 16a b + 16c = = ; 9a 2 12a + 9b 4a 6b + 9c = Таким чином, отримали, що два багаточлени рівні, а тоді рівні відповідні коефіцієнти: 9a = 9, 12a + 9b = 6, 4a 6b + 9c = 2 a = 1, b = 2, c = 2. 21

22 Отже, a = (a 2 + b + c) 1 = Виписуємо загальне рішення ЛРС, тобто a = a + a = (c 1 + c 2) (). За допомогою початкових умов знаходимо коефіцієнти c 1 і c 2. a 0 = (c 1 + c 2 0) () = 1; a 1 = (c 1 + c 2 1) () = 7. Вирішуючи систему c1 + 2 = 1, 4c1 + 4c2 + 5 = 7, отримаємо c 1 = 1, c 2 = 2. Таким чином, рішення ЛРС має вигляд : a = (1 2)

23 2. ЗАВДАННЯ ДЛЯ САМОСТІЙНОГО РІШЕННЯ 2.1. Завдання для вирішення ЛОРС та ЛРС Лінійні однорідні рекурентні співвідношення другого порядку 1. a +2 = 9 a a, a 0 = 2, a 1 = a +2 = 3,5 a +1 2,5 a, a 0 = 3,5 , a 1 = a +2 = 8 a a, a 0 = 4, a 1 = a +2 = 2 a a, a 0 = 3, a 1 = i. 5. a +2 = 10 a a, a 0 = 3, a 1 = a +2 = 6 a a, a 0 = 0, a 1 = 2i a +2 = 8 a a, a 0 = 2, a 1 = a + 2 = 4 a a, a 0 = 7, a 1 = a +2 = a +1 + a, a 0 = 2, a 1 = a +2 = 8 a a, a 0 = 8, a 1 = a +2 = () a a, a 0 = 7, a 1 = a +2 = 5 a +1 4 a, a 0 = 0, a 1 = a +2 = 2 a +1 5 a, a 0 = 5, a 1 = 6i a +2 = 3 a a, a 0 = 7, a 1 = a +2 = 6 a +1 9 a, a 0 = 8, a 1 = a +2 = 6 a a, a 0 = 3, a 1 = 9 2i. 17. a +2 = a a, a 0 = 4, a 1 = a +2 = 14 a a, a 0 = 5, a 1 = a +2 = 8 a a, a 0 = 2, a 1 = a +2 = 7 a a, a 0 = 5, a 1 = a +2 = 2 a +1 + a, a 0 = 2, a 1 =

24 1 22. a +2 = a +1 a, a 0 = 4, a 1 = a +2 = 4 a +1 a, a 0 = 12, a 1 = a +2 = a a, a 0 = 2, a 1 = a +2 = 2 a a, a 0 = 8, a 1 = a +2 = 6 a +1 9 a, a 0 = 12, a 1 = a +2 = 4 a +1 5 a, a 0 = 5, a 1 = 10 i a +2 = 3 a +1 a, a 0 = 8, a 1 = a +2 = 14 a a, a 0 = 5, a 1 = a +2 = 4 a a, a 0 = 2, a 1 = a +2 = 4 a +1 5 a, a 0 = 3, a 1 = 6 7i. 32. a +2 = a a, a 0 = 5, a 1 = a +2 = 16 a a, a 0 = 7, a 1 = a +2 = 5 a +1 6 a, a 0 = 2, a 1 = a +2 = 10 a a, a 0 = 2, a 1 = 10 4i a +2 = 6 a +1 5 a, a 0 = 11, a 1 = a +2 = 2 a a, a 0 = 11, a 1 = a +2 = 6 a a; a 0 = 3, a 1 = 0. Лінійні однорідні рекурентні співвідношення третього порядку 39. a +3 = 7 a a a, a 0 = 1, a 1 = 3, a 2 = a +3 = 4 a +2 a +1 6 a, a 0 = 4, a 1 = 5, a 2 = a +3 = 6 a a a, a 0 = 5, a 1 = 8, a 2 = a +3 = 8 a a a, a 0 = 4, a 1 = 31, a 2 = a +3 = 5 a +2 3 a +1 9 a, a 0 = 1, a 1 = 3, a 2 = a +3 = 15 a a a, a 0 = 8, a 1 = 40, a 2 =

25 45. a +3 = 27 a a, a 0 = 6, a 1 = 3, a 2 = a +3 = 6 a a a, a 0 = 15, a 1 = 32, a 2 = a +3 = 15 a a a, a 0 = 1, a 1 = 20, a 2 = a +3 = 9 a a a, a 0 = 0, a 1 = 4, a 2 = a +3 = 2 a a +1 6 a, a 0 = 4, a 1 = 5, a 2 = a +3 = 4 a +2 5 a a, a 0 = 2, a 1 = 6, a 2 = a +3 = 6 a +2 5 a a, a 0 = 4, a 1 = 2, a 2 = a +3 = 3 a a a, a 0 = 2, a 1 = 17, a 2 = a +3 = 9 a a a, a 0 = 1, a 1 = 3, a 2 = a +3 = 6 a a +1 6 a, a 0 = 13, a 1 = 31, a 2 = a +3 = 5 a +2 3 a +1 9 a, a 0 = 3, a 1 = 14, a 2 = a +3 = a a +1 4 a, a 0 = 2, a 1 = 1, a 2 = a +3 = 3 a a a, a 0 = 2, a 1 = 3, a 2 = a +3 = 12 a a a, a 0 = 2, a 1 = 16, a 2 = a +3 = 4 a a a, a 0 = 0,2, a 1 = 6, a 2 = a +3 = 8 a a a, a 0 = 3, a 1 = 13, a 2 = a +3 = 4 a a a, a 0 = 3, a 1 = 29, a 2 = a +3 = 5 a +2 7 a a, a 0 = 11, a 1 = 34, a 2 = a +3 = 11 a a a, a 0 = 27, a 1 = 17, a 2 = a +3 = 12 a a a, a 0 = 1, a 1 = 37, a 2 = a +3 = 3 a a a, a 0 = 11, a 1 = 23, a 2 = a +3 = 7 a a a, a 0 = 3, a 1 = 6, a 2 = a +3 = 4 a a a, a 0 = 4, a 1 = 1, a 2 = 4; 68. a +3 = 7 a a a, a 0 = 1, a 1 = 0, a 2 = a +3 = 5 a a a, a 0 = 6, a 1 = 0, a 2 = a +3 = 5 a +2 3 a a, a 0 = 10, a 1 = 1, a 2 = a +3 = 3 a +2 3 a +1 + a, a 0 = 2, a 1 = 4, a 2 = a +3 = 3 a a a , a 0 = 6, a 1 = 5, a 2 =

26 73. a +3 = 10 a a a, a 0 = 0, a 1 = 1, a 2 = a +3 = 8 a a a, a 0 = 8, a 1 = 23, a 2 = a +3 = 5 a + 2 8 a +1 4 a, a 0 = 11, a 1 = 15, a 2 = a +3 = a a a, a 0 = 6, a 1 = 5, a 2 = a +3 = 10 a a a, a 0 = 1, a 1 = 2, a 2 = a +3 = a a a, a 0 = 1, a 1 = 14, a 2 = a +3 = 2 a +2 + a a, a 0 = 10, a 1 = 1, a 2 = a +3 = 5 a +2 8 a a, a 0 = 9, a 1 = 9, a 2 = a +3 = 8i a a +1 10i a, a 0 = 8; = 38. Лінійні рекурентні співвідношення першого порядку 82. a +1 = 4 a + 6, a 0 = a +1 = a + + 1, a 0 = a +1 = 5 a , a 0 = a +1 = 3 a + 5 2, a 0 = a +1 = 3 a + (4) 5 1, a 0 = a +1 = 4 a + 8 4, a 0 = a +1 = 3 a , a 0 = 14. Лінійні рекурентні співвідношення другого порядку 89. a +2 = 7 a a + 10, a 0 = 4, a 1 = a +2 = 10 a a + 32, a 0 = 1, a 1 = a +2 = 6 a +1 9 a 2 3, a 0 = 0, a 1 = a +2 = 7 a a , a 0 = 3, a 1 = a +2 = 9 a a + (18 20) 2, a 0 = 6, a 1 = a +2 = 8 a +1 7 a , a 0 = 9, a 1 = a +2 = 4 a +1 9 a , a 0 = 15, a 1 = 27 i a +2 = 12 a a , a 0 = 13, a 1 = 6. 26

Благовіщенський державний педагогічний університет кафедра алгебри, геометрії та МПМ 16 квітня 2011 р. 1 Рішення рекурентних співвідношень Визначення Рекурентним співвідношенням називається співвідношення

Лекція 3. Послідовності, що визначаються рекурентними співвідношеннями. Однорідні та неоднорідні лінійні рекурентні рівняння (ЛОРУ та ЛНРУ). Загальні рішення ЛОРУ та ЛНРУ. Лектор – доцент Селезньова Світлана

Лекція: Послідовності. Однорідні та неоднорідні лінійні рекурентні рівняння. Загальні рішення лінійних рекурентних однорідних та неоднорідних рівнянь. Лектор – доцент Селезньова Світлана Миколаївна

лекція. Функції натурального аргументу (послідовності). Однорідні та неоднорідні лінійні рекурентні рівняння (ЛОРУ та ЛНРУ). Загальні рішення ЛОРУ та ЛНРУ. Приклади Лектор – доцент Селезньова Світлана

РІШЕННЯ РЕКУРРЕНТНИХ РІВНЯНЬ Позначимо через значення деякого виразу при підстановці в нього цілого числа Тоді залежність члена послідовності від членів послідовності F F зі значеннями

Пензенський державний педагогічний університет ім У Г Бєлінського О А Монахова, Н А Восьминіна Рекурентні послідовності Алгебра формальних рядів Методичні рекомендації для студентів спеціальностей

Лекція 3. Послідовності, що визначаються рекурентними співвідношеннями. Однорідні та неоднорідні лінійні рекурентні рівняння (ЛОРУ та ЛНРУ). Загальні рішення ЛОРУ та ЛНРУ. Приклади Лектор – доцент Селезньова

Міністерство освіти і науки Російської Федерації Федеральна державна бюджетна освітня установа вищої професійної освіти «Сибірський державний індустріальний університет»

Міністерство транспорту Російської Федерації ФЕДЕРАЛЬНА ДЕРЖАВНА БЮДЖЕТНА ОСВІТАЛЬНА УСТАНОВА ВИЩОЇ ОСВІТИ «РОСІЙСЬКИЙ УНІВЕРСИТЕТ ТРАНСПОРТУ (МІІТ)» Кафедра «Математичний аналіз»

Лекції з Математики Вип ТММ-Ю У Чебраков ТЕОРІЯ МАГІЧНИХ МАТРИЦЬ Санкт-Петербург, 00 УДК 5+5 ББК Ч35 Рецензенти: Доктор фізико-математичних наук, професор С-Петерб техн ун- Саль Кандидат

А А КИРСАНОВ КОМПЛЕКСНІ ЧИСЛА ПСКІВ ББК 57 К45 Друкується за рішенням кафедри алгебри та геометрії та редакційно-видавничої ради ПДПІ ім СМ Кірова Рецензент: Медведєва ІН, кандидат фіз мат наук, доцент

Михайлова Інна Анатоліївна Інститут математики та природничих наук. Кафедра алгебри та фундаментальної інформатики. 30 вересня 2018 р. Приклади Числа Фібоначчі Числа Фібоначчі 1, 1, 2, 3, 5, 8, 13, 21,...

Уральський федеральний університет, Інститут математики та комп'ютерних наук, кафедра алгебри та дискретної математики Поняття багаточлена Визначення Багаточленом від однієї змінної називається вираз виду

Глава 0 НАСЛІДНОСТІ Алгоритми А- Завдання числових послідовностей А-Арифметична прогресія А-Геометрична прогресія А-Підсумування А-5 Безкінечно спадна геометрична прогресія

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СПЕЦИАЛИЗИРОВАННЫЙ УЧЕБНО-НАУЧНЫЙ ЦЕНТР Математика 0 класс МЕТОД МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ И БЕСКОНЕЧНЫЕ ЧИСЛОВЫЕ

Федеральне агентство з освіти Державна освітня установа вищої професійної освіти Ухтинський державний технічний університет (УДТУ) МЕЖ ФУНКЦІЇ Методичні

ЧИСЛОВІ НАСЛІДНОСТІ. ГЕОМЕТРИЧНА ПРОГРЕСІЯ Геометричною прогресією називається числова послідовність b, перший член якої відмінний від нуля, а кожен наступний член, починаючи з другого,

ФЕДЕРАЛЬНА АГЕНЦІЯ З ОСВІТИ Державна загальноосвітня установа вищої професійної освіти «Тверський державний університет» Математичний факультет Кафедра алгебри

Розділ 0 ТЕСТОВІ ЗАВДАННЯ ТА ДИКТАНТИ Т-00 Обчислення членів послідовності за рекурентною формулою Т-00 Складання рекурентної формули Т-00 Формула загального члена Т-004 Складання арифметичної прогресії

6-7 уч рік 6, кл Математика Комплексні числа 4 Квадратні рівняння Алгебраїчні рівняння У шкільному курсі алгебри розглядалися квадратні рівняння ax bx c =, a, () з дійсними коефіцієнтами

МІНІСТЕРСТВО ОСВІТИ І НАУКИ РОСІЙСЬКОЇ ФЕДЕРАЦІЇ Державна освітня установа вищої професійної освіти МОСКІВСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ МАШИНОБУДУВАННЯ ІІ Поспєлов,

Лекція Розділ Множини та операції над ними Поняття множини Поняття множина відноситься до найбільш первинних понять математики не визначених через простіші Під множиною розуміють сукупність

Лекції з математики. Вип. ТММ-1 Ю. В. Чебраков ТЕОРІЯ МАГІЧНИХ МАТРИЦЬ Санкт-Петербург, 010 УДК 511+51 ББК Ч345 Рецензенти: Доктор фізико-математичних наук, професор С.-Петерб. техн. ун-ту

Прогресії Послідовність функція натурального аргументу. Завдання послідовності формулою загального члена: a n = f(n), n N, наприклад, a n = n + n + 4, а = 43, а = 47, а 3 = 3,. Завдання послідовності

ДИФЕРЕНЦІЙНІ РІВНЯННЯ Загальні поняття Диференціальні рівняння мають численні та найрізноманітніші додатки у механіці фізики астрономії техніці та інших розділах вищої математики (наприклад

Зміст Вступ. Основні поняття.... 4 1. Інтегральні рівняння Вольтерри... 5 Варіанти домашніх завдань.... 8 2. Резольвента інтегрального рівняння Вольтерри. 10 Варіанти домашніх завдань.... 11

МІНІСТЕРСТВО ЗАГАЛЬНОЇ ТА ПРОФЕСІЙНОЇ ОСВІТИ РОСІЙСЬКОЇ ФЕДЕРАЦІЇ НИЖЕМІСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ ім. Н. І. ЛОБАЧЕВСЬКОГО Факультет обчислювальної математики та кібернетики Кафедра математичної

лекція. Завдання про кроликів. Числа Фібоначчі, послідовність Фібоначчі, рекурентна формула 3. Властивості чисел Фібоначчі (a) Лінійність (b) Теоретико-числові властивості (c) Суми: F + F +... + F n, непарних

ЛІНІЙНА АЛГЕБРА Видавництво ТДТУ Міністерство освіти і науки Російської Федерації ГОУ ВПО "Тамбовський державний технічний університет" ЛІНІЙНА АЛГЕБРА Методичні вказівки для студентів

Тишин В І Основні методи вирішення тригонометричних рівнянь г Тишин В І Математика для вчителів та учнів Матеріал підготовлений вчителем математики Тишиним Володимиром Івановичем року Тишин В І Основні

Диференціальні рівняння вищого ладу. Конєв В.В. Малюнки лекцій. 1. Основні поняття 1 2. Рівняння, що допускають зниження порядку 2 3. Лінійні диференціальні рівняння вищого порядку

лекція.7. Розширення поняття числа. Комплексні числа, дії з них Анотація: У лекції вказується необхідність узагальнення поняття числа від натурального до комплексного. Вводяться алгебраїчна,

МІНІСТЕРСТВО ОСВІТИ І НАУКИ РОСІЙСЬКОЇ ФЕДЕРАЦІЇ федеральна державна бюджетна освітня установа вищої професійної освіти «УЛЬЯНІВСЬКИЙ ДЕРЖАВНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ»

Лекція 3 Ряди Тейлора і Маклорена Застосування статечних рядів Розкладання функцій у статечні ряди Ряди Тейлора і Маклорена Для додатків важливо вміти цю функцію розкладати в статечний ряд, ті функцію

Уральський федеральний університет, Інститут математики та комп'ютерних наук, кафедра алгебри та дискретної математики Вступні зауваження У цій лекції ми приступаємо до вивчення лінійної алгебри як такої,

Тема 2-11: Власні вектори та власні значення А. Я. Овсянніков Уральський федеральний університет Інститут математики та комп'ютерних наук кафедра алгебри та дискретної математики алгебра та геометрія

НОВОСИБІРСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ Заочна школа Математичне відділення МЕТОД МАТЕМАТИЧНОЇ ІНДУКЦІЇ ТА БЕЗКІНЕЧНІ ЧИСЛОВІ НАСЛІДНОСТІ 0-й клас, завдання ПРАВИЛА ОФОРМЛЕННЯ

ЗАВДАННЯ ДО КОНТРОЛЬНОЇ РОБОТИ За дисципліною: «Алгебра» Спеціальність: «Математика» заочна форма навчання 6 семестр Упорядник: зав кафедрою Трофімук АА Багаточлени від кількох змінних алгебраїчні результати

Вказівки, рішення, відповіді РІВНЯННЯ В ЦІЛІХ ЧИСЛАХ. Рівняння з однією невідомою. Рішення. Підставимо в рівняння. Отримаємо рівність (4a b 4) (a b 8) 0. Рівність A B 0 де А і В цілі, виконується,

ВСТУП В МАТЕМАТИЧНИЙ АНАЛІЗ Лекція. Поняття множини. Визначення функції основних властивостей. Основні елементарні функції ЗМІСТ: Елементи теорії множин Безліч дійсних чисел Числова

Робоча програма з алгебри для учнів 8-9 класів розроблена з урахуванням вимог до результатів освоєння основний освітньої програми основного загальної освіти. Робоча програма розрахована

Уральський федеральний університет, Інститут математики та комп'ютерних наук, кафедра алгебри та дискретної математики Вступні зауваження При вирішенні багатьох завдань виникає необхідність мати числові

ЗВИЧАЙНІ ДИФЕРЕНЦІЙНІ РІВНЯННЯ ПЕРШОГО ПОРЯДКУ.. Основні поняття Диференціальним рівнянням називається рівняння, до якого невідома функція входить під знаком похідної чи диференціала.

СИСТЕМИ ЛІНІЙНИХ ДИФЕРЕНЦІЙНИХ РІВНЯНЬ З ПОСТОЯННИМИ КОЕФІЦІЄНТАМИ Приведення до одного рівняння -го порядку З практичної точки зору дуже важливі лінійні системи з постійними коефіцієнтами

МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ РОСІЙСЬКОЇ ФЕДЕРАЦІЇ Нижегородський державний університет ім. НІ Лобачевського Національний дослідний університет АВ Леонтьєва

АГЕНЦІЯ ОСВІТИ АДМІНІСТРАЦІЇ КРАСНОЯРСЬКОГО КРАЮ КРАСНОЯРСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ ЗАТІВНА природничо-наукова школа при красзі ДОДАТКОВІ ГЛАВИ МАТЕМАТИКИ

Міністерство освіти Російської Федерації Російський державний університет нафти та газу імені ІМ Губкіна ВІ Іванов Методичні вказівки до вивчення теми «ДИФЕРЕНЦІЙНІ РІВНЯННЯ» (для студентів

СТУПЕНЬ З ДРОБНИМ ПОКАЗНИКОМ Якщо показник t ступеня числа є дробовим, ті t, N, то для невід'ємних значень (0) за визначенням вважають def Для негативних чисел (0)< операция возведения

Міністерство сільського господарства Російської Федерації Федеральна державна бюджетна освітня установа вищої освіти «Пермська державна сільськогосподарська академія імені

РАЦІОНАЛЬНІ ЧИСЛА Звичайні дроби Визначення Дроби виду, називаються звичайними дробами Звичайні дроби, правильні та неправильні Визначення Дроби, правильної, якщо< при, где Z, N Z, N Z,

лекція. 5. ОПИС І АНАЛІЗ ДИСКРЕТНИХ ЛІНІЙНИХ СИСТЕМ ЗА ДОПОМОГОЮ РІЗНИЧНИХ РІВНЯНЬ 5.. ОДНОМІРНІ СИСТЕМИ ПРИ ДЕТЕРМІНОВАНИХ ВПЛИВАХ 5... Опис сигналів і систем. Опис сигналів. Сигнали

На закінчення цього пункту зауважимо, що говорять також про власні вектори матриці порядку, маючи при цьому через власні вектори оператора -мірного простору, який має своєю матрицею в деякому базисі.

ПРАКТИЧНЕ ЗАНЯТТЯ Інтегрування раціональних дробів Раціональним дробом називається дріб виду P Q, де P і Q багаточлени Раціональний дріб називається правильним, якщо ступінь многочлена P нижче ступеня

Тема 14 «Алгебраїчні рівняння та системи нелінійних рівнянь» Багаточлен ступеня n називається многочлен виду P n () a 0 n + a 1 n-1 + + a n-1 + a n, де a 0, a 1, a n-1, a n задані числа, a 0,

Тема: Загальна теорія систем лінійних рівнянь А. Я. Овсянніков Уральський федеральний університет Інститут математики та комп'ютерних наук кафедра алгебри та дискретної математики алгебра та геометрія для

МІНІСТЕРСТВО ОСВІТИ І НАУКИ РОСІЙСЬКОЇ ФЕДЕРАЦІЇ Московський державний університет геодезії та картографії (МІІГАіК) Факультет дистанційних форм навчання Заочне відділення `` МЕТОДИЧНІ ВКАЗІВКИ,

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПРОМЫШЛЕННЫХ

Вирішити диференціальне рівняння Рішення: складемо і вирішимо характеристичне рівняння:, Отримано два різних дійсних кореня Все, що залишилося зробити записати відповідь, керуючись формулою

КОМПЛЕКСНІ ЧИСЛА РОЗКЛАДАННЯ МНОГОЧЛЕНІВ НА МНОЖИКИ Числові множини Множина комплексних чисел Багаточлени з речовими коефіцієнтами Розкладання на множники ЧИСЛОВІ МНОЖИНИ

РЕКУРРЕНТНІ СПІВДІЛЕННЯ

РЕКУРРЕНТНІ СПІВДІЛЕННЯ

(від латів. recur-rens, рід. відмінок recurrentis - повертається) - однотипні ф-ли, які пов'язують між собою які йдуть один за одним деякої послідовності (це може бути послідовність чисел, ф-цій і т. д.). ). Залежно від природи об'єктів, пов'язаних Р. с., ці співвідношення можуть бути алгебраїчними, функціональними, диференціальними, інтегральними тощо.

наиб. відомий клас Р. с.- це рекурентні ф-ли для спеціальних функцій.Так, для циліндричних функцій Z m (x)P. с. мають вигляд

Вони дозволяють за ф-цією Z m0 (x)Знайти ф-ції Z m (x)п-рі т= т 0 b 1, т 0 b 2і т. д. або, напр., за значеннями ф-цій у деякій точці х 0 . 0 знайти (у чисельних розрахунках) значення будь-якої з ф-цій

У цій же точці (тут m 0 - будь-яке речове число).

Др. важливий клас Р. с. дають численні методи послідовних наближень (див. Ітераційний метод);сюди ж примикають і методи обурень теорії.

У квантовій механіці є ще один вид Р. с., що зв'язують між собою вектори в просторі гільбертовий станів. nНапр., стаціонарні гармонії, осцилятори параметризуються цілими невід'ємними числами. Відповідні вектори, що позначаються , де n- ціле, за різних можуть бути отримані один з одного дією операторів народженняа + та знищення:

а Ці співвідношення можна дозволити, висловивши будь-який вектор через (найнижчий енергетич. стан, 0):

h = Узагальненням цієї конструкції є представленнявторинного квантування у квантовій статистич. механіки та квантової теорії поля (див.Фока

простір). Боголюбова рівняння);знання таких ф-цій дозволяє знайти все термодинамічні. Показники системи.

У квантовій теорії поля динаміч. міститься, напр., Грина функцій.Для їх обчислення використовують разл. наближення, найчастіше – розрахунки з теорії збурень. Альтернативний підхід заснований на інтегродиференціальних Дайсон рівняннях,які є Р. с.: ур-ня для двоточкової ф-ції Гріна містить чотириточкову і т. д. Як і ур-ня Боголюбова, цю систему вдається вирішувати, лише "оборвавши" ланцюжок (місце "обриву" вибирається зазвичай з фіз. міркувань і визначає одержуване ).

Ще один вид Р. с. у квантовій теорії поля - У орда тотожностіу теоріях калібрувальних полів.Ці тотожності також є ланцюжок інтегродиференціальних співвідношень, що пов'язують між собою ф-ції Гріна з разл. числом зовнішніх ліній p є наслідком калібрувальної інваріантності теорії. Вирішальну роль вони грають для перевірки калібрувальної симетрії під час проведення процедури перенормування.

Нарешті, сама - також рекурентна процедура: на кожному кроці (у кожній наступній петлі) використовуються контрчлени,отримані з обчислення діаграм з меншою кількістю петель (докладніше див. R-операція).А. М. Малокостів.

Фізична енциклопедія. У 5-ти томах. - М: Радянська енциклопедія. Головний редактор А. М. Прохоров. 1988 .

Дивитися що таке "РЕКУРРЕНТНІ СПІВДІЛЕННЯ" в інших словниках:

рекурентні співвідношення- - [Л.Г.Суменко. Англо-російський словник з інформаційних технологій. М.: ДП ЦНДІС, 2003.] Тематики інформаційні технології загалом EN recurrence relations … Довідник технічного перекладача

- (функції Вебера) загальна назва для спеціальних функцій, що є рішеннями диференціальних рівнянь, що виходять при застосуванні методу поділу змінних для рівнянь математичної фізики, таких як рівняння Лапласа, рівняння… Вікіпедія

Або лічилка Джозефуса - відоме математичне завдання з історичним підтекстом. Завдання засноване на легенді, що загін Йосипа Флавія, який захищав місто Йодфат, не побажав здаватися в полон тим, хто блокував печеру переважаючими силам римлян.

Пафнутий Львович Чебишев У математиці послідовністю ортогональних багаточленів називають нескінченну послідовність дійсних багаточленів … Вікіпедія

Ця стаття пропонується для видалення. Пояснення причин та відповідне обговорення ви можете знайти на сторінці Вікіпедія:До видалення/22 листопада 2012. Поки процес обговорення … Вікіпедія

Послідовність Падована це ціла послідовність P(n) з початковими значеннями і лінійним рекурентним співвідношенням Перші значення P(n) такі 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28 , 37, 49, 65, 86, 114, 151, 200, 265 … Вікіпедія

Багаточлени Ерміту певного виду послідовність багаточленів однієї речовинної змінної. Багаточлени Ерміта виникають у теорії ймовірностей, у комбінаториці, фізиці. Ці багаточлени названо на честь Шарля Ерміта. Зміст 1… … Вікіпедія

- (функції Бесселя) рішення Zv(z)ур ня Бесселя де параметр (індекс) v довільне дійсне чи комплексне число. У додатках частіше зустрічається ур ня, що залежить від чотирьох параметрів: рішення якого виражаються через Ц … Фізична енциклопедія

Метод вирішення системи лінійних алгебраїч. рівнянь А х= b з ермітовою невиродженою матрицею А. Серед прямих методів він найефективніший при реалізації ЕОМ. Обчислювальна схема методу в загальному випадку заснована на факторизації ермітової. Математична енциклопедія

Модифіковані функції Бесселя – це функції Бесселя від суто уявного аргументу. Якщо в диференціальному рівнянні Бесселя замінити на, воно набуде вигляду. Це рівняння називається модифікованим рівнянням Бессел … Вікіпедія