Как найти рекурсивную формулу

Также рассмотрим гармоническую последовательность:

Еще как пример можно рассматривать последовательность Фибоначчи. Эта последовательность значений

была определена рекурсивно — не было дано прямой формулы для нахождения

-го элемента последовательности Фибоначчи.

Одна специальная рекурсивно определенная функция, которая не имеет простого явного определения, дает числа Фибоначчи:

Значениями этой функции являются:

Таким образом, последовательность чисел Фибоначчи такова:

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

.

Выполним следующие действия, чтобы найти рекурсивную формулу для геометрической последовательности:

Шаг 1. Определим, является ли данная последовательность геометрической. Умножим или разделим каждый член на число. Если от одного члена к другому получается одинаковая сумма, то последовательность геометрическая.

Шаг 2. Найдем общее отношение данной последовательности.

Шаг 3. Сформулируем рекурсивную формулу, указав первый член. Затем создадим формулу общего отношения к предыдущему члену.

В итоге формула для геометрической последовательности имеет такой вид:

Recursion can be defined by two properties. A base case and recursion step. The base case is a terminating scenario that doesn’t use recursion to produce results. The recursion step consists of a set of rules that reduces the successive cases to forward to the base case.

Recursive Formula

A recursive function is a function that defines each term of a sequence using the previous term i.e., The next term is dependent on the one or more known previous terms. Recursive function h(x) is written as-

h(x) = a₀h(0) + a₁h(1) + a₂h(2) + … + a_{x – 1}h(x – 1) 

Where a_i ≥ 0 and i = 0, 1, 2, 3, … x – 1

Recursive Formula is a formula that defines the each term of sequence using the previous/preceding terms. It defines the following parameters

1. The first term of the sequence
2. The pattern rule to get any term from its previous terms.

There are few recursive formulas to find the n^th term based on the pattern of the given data. They are,

• n^th term of Arithmetic Progression a_n = a_{n – 1} + d for n ≥ 2
• n^th term of Geometric Progression a_n = a_{n – 1} × r for n ≥ 2
• n^th term in fibonacci Sequence a_n = a_{n – 1} + a_{n – 2} for n ≥ 2 and a₀ = 0 & a₁ = 1

Where d is common difference and r is the common ratio

Sample Problems

Question 1: Given a series of numbers with a missing number in middle 1, 11, 21, ?, 41. Using recursive formula find the missing term.

Solution:

Given,

1, 11, 21, _, 41

First term (a) = 1

Difference between terms = 11 – 1 = 10

21 – 11 = 10

So the difference between numbers is same.

Common Difference (d) = 10

Recursive Function to find nth term is a_n = a_n-1 + d

a₄ = a_4-1 + d

= a₃ + d

= 21 + 10

a₄ = 31

Missing term in the given series is 31.

Question 2: Given series of numbers 5, 9, 13, 17, 21,… From the given series find the recursive formula 

Solution:

Given number series

5, 9, 13, 17, 21,…

first term (a) = 5

Difference between terms = 9 – 5 = 4

13 – 9 = 4

17 – 13 = 4

21 – 17 = 4

So the difference between numbers is same.

Common Difference (d) = 4

The given number series is in Arithmetic progression.

So recursive formula a_n = a_n-1 + d

a_n = a_n-1 + 4

Question 3: Given a series of numbers with a missing number in middle 1, 3, 9, _, 81, 243. Using recursive formula find the missing term.

Solution:

Given,

1, 3, 9, _, 81, 243

First term (a) = 1

The difference between numbers are large so It should not be in Arithmetic progression. 

Let’s check whether it is in Geometric progression or not,

a₂/a₁ = 3/1 = 3

a₃/a₂ = 9/3 = 3

a₅/a₄ = 243/81 = 3

Hence ratio between adjacent numbers are same. So given series is in Geometric Progression 

Common Ratio (r) = 3

Recursive Function to find nth term is a_n = a_n-1 × r

a₄ = a_4-1 × r

= a₃ × r

= 9 × 3

a₄ = 27

Missing term in the given series is 27.

Question 4: Given series of numbers 2, 4, 8, 16, 32, … From the given series find the recursive formula.

Solution:

Given number series,

2, 4, 8, 16, 32, …

First term (a) = 2

Difference between terms = 4 – 2 = 2

8 – 4 = 4

It is not in A.P as difference between numbers are not same.

Let’s check whether it is in Geometric progression or not

a₂/a₁ = 4/2 = 2

a₃/a₂ = 8/4 = 2

a₄/a₃ = 16/8 = 2

Common Ratio (r) = 2

The given number series is in Geometric progression.

So recursive formula a_n = a_n-1 × r

a_n = a_n-1 × 2

Question 5: Find the 5^th term in a Fibonacci series if the 3^rd and 4^th terms are 2,3 respectively.

Solution:

Given that number series is in fibonacci series form.

Also given a₃ = 2

a₄ = 4

Then a₅ = a₃ + a₄

= 2 + 3

a₅ = 5

Question 6: Find the next term in the given series 1, 1, 2, 3, 5, 8, 13, …

Solution:

Given, 

1, 1, 2, 3, 5, 8, 13,…

The given series is in fibonacci form because every n^th term is the result of addition between two previous terms i.e., n – 1^th & n – 2^th terms

Example: a₃ = a₁ + a₂

3 = 1 + 2

Then a₈ = a₇ + a₆

= 13 + 8

a₈ = 21

Last Updated :
22 Mar, 2022

Like Article

Save Article

Скачать файл с кодом и данные можно в оригинале поста в моем блоге

В языке Wolfram Language есть четыре совершенно потрясающие функции: FindSequenceFunction, RSolve, DifferenceRootReduce и FindFormula. В этой статье мы обсудим их возможности и поговорим о функциях, тесно с ними связанных — для поиска параметров линейной рекурсии FindLinearRecurrence (коэффициентов линейного рекуррентного уравнения), производящих функциях GeneratingFunction и Z-преобразовании ZTransform.

Первая функция — FindSequenceFunction — по последовательности чисел ищет выражение для её n-го члена не требуя вообще ничего более.

Hold @ FindSequenceFunction[{1, 1, 2, 3, 5, 8, 13}, n]

FindSequenceFunction[
{-2, 4Sqrt[Pi],
-16, 16Sqrt[Pi],
-128/3, 32Sqrt[Pi],
-1024/15, 128Sqrt[Pi]/3,
-8192/105, 128Sqrt[Pi]/3},
n]

Вторая функция — RSolve — решает рекуррентные уравнения самых разных типов. Элементы могут иметь вид

,

,

, где f имеет вид: n+A (арифметические разностные уравнения), B*n — геометрические или q-разностные уравнения), B*n+a (арифметико-геометрические функциональные разностные уравнения), B*n^d (степеные геометрические функциональные разностные уравнения), (A*n+B)/(C*n+D) (линейные дробные функциональные разностные уравнения).

RSolve[
	{
		a[n + 3]==2 * a[n],
		a[1]==α,
		a[2]==β,
		a[3]==γ
	},
	a, n
]

RSolve[
	{
		v[n]==(2 * Pi * v[n - 2]) / n,
		v[2]==Pi,
		v[3]==(4 * Pi) / 3
	},
	v @ n, n
]

Третья функция — DifferenceRootReduce — ищет рекуррентное соотношение для последовательности чисел, n-й член которой имеет заданный вид.

DifferenceRootReduce[-2 * n * Pi * Factorial[(n * 2) - 1],
	n
]

RSolve[
	{
		(-8 * y[n]) + n * y[2 + n]==0,
		y[-1]==1/4,
		y[0]==0,
		y[1]==-2,
		y[2]==4Sqrt[Pi]
	},
	y, n
]

Эта функция может много чего ещё, скажем, проверять тождества относительно последовательностей, к примеру:

DifferenceRootReduce[Fibonacci[2 * n]==Fibonacci[n] * LucasL[n], n]

Здесь LucasL — последовательность чисел Люка (это, по сути, последовательность Фибоначчи, только первые члены не 1, 1, а 1, 3.

Hold @ DifferenceRootReduce @ LucasL @ n

DifferenceRootReduce[LucasL[n]==Fibonacci[n - 1] + Fibonacci[n + 1]]

Как найти рекуррентную формулу для последовательности?

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

Работать это может примерно так: пусть мы ищем n-й член последовательности в виде

. Пусть у нас есть первые члены последовательности:

sequence = {1, 0, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741, 13860, 33461}

Попробуем найти выражение для n-го члена в виде

:

seauenseEq1 = MovingMap[
	Function[
		Dot[Part[#, 1;;1], {a @ 1}]==Part[#, -1]
	],
	sequence, 1
]

Hold @ Solve @ seauenseEq1

Как видно, решений нет.

Попробуем искать теперь в виде

:

seauenseEq2 = MovingMap[
	Function[
		Dot[Part[#, 1;;2], {a @ 1, a @ 2}]==Part[#, -1]
	],
	sequence, 2
]

Hold @ Solve @ seauenseEq2

Как видим, получилось. Значит, n-й член имеет вид:

.

На самом деле есть встроенная функция FindLinearRecurrence, которая позволяет найти линейную рекурсию, подобно тому, как мы это только что сделали:

Hold @ FindLinearRecurrence @ sequence

Используя функцию LinearRecurrence можно продлить последовательность:

LinearRecurrence[{2, 1}, sequence[[1;;2]], 50]

Или объединить все в одну строчку, построив функцию, которая: продлит последовательность, выдаст разностное уравнение и найдет общую формулу для n-го члена:

sequenseExtension[list_, n_] := Module[
	{lr, eq},
	lr = FindLinearRecurrence @ list;
	eq = Flatten[
		{
			a[k]==Total[
					Table[
						a[k + -i] * Part[lr, i],
						{i, 1, Length @ lr}
					]
				],
			Table[a[i], list[[i]]], {i, 1, Length @ lr}]
		}
	];
	<|
		"Уравнение" -> eq,
		"Формула" -> FullSimplify[a[k] /. Part[RSolve[eq, a, k], 1]],
		"Продление" -> LinearRecurrence[lr, Part[list, Span[1, Length[lr]]], n]
	|>
];

Hold @ sequenseExtension[{1, 1, 2, 3, 5}, 20]

Hold @ sequenseExtension[{1, 2, 2, 1, 1, 2, 2, 1}, 20]

Hold @ sequenseExtension[
{1, 0, -1, 0, 2, 0, -2, 0, 3, 0, -3, 0, 4, 0, -4},
25
]

Как найти формулу для n-го члена последовательности?

Z-преобразование

Z-преобразование состоит в вычислении ряда вида

от дискретной функции

. Это преобразование позволяет свести рекуррентное уравнение для задания последовательности к уравнению относительно образа функции

, что аналогично преобразованию Лапласа, которое сводит дифференциальные уравнения к алгебраическим.

Вот как это работает:

Grid[
	Transpose[
		Function[
			{
				#,
				Map[TraditionalForm, Map[FullSimplify, ZTransform[#, n, z]]]
			}
		][
			{
				f[n - 2],
				f[n - 1],
				f @ n,
				f[n + 1],
				f[n + 2]
			}
		]
	],
	Background -> White, Dividers -> All
]

Посмотрим на примере, скажем, возьмем хорошо известную последовательность Фибоначчи:

fibonacciEq = f[n]==f[n - 1] + f[n - 2];

initialConditions = {f[1] -> 1, f[2] -> 1};

Ясно, что её стоит переписать в виде, как показано ниже, чтобы не появлялись конструкции типа

после применения Z-преобразования.

fibonacciEq = f[n + 2]==f[n + 1] + f[n];

initialConditions = {f[0] -> 1, f[1] -> 1};

Осуществим Z-преобразование:

fibonacciEqZTransformed = ReplaceAll[fibonacciEq, pattern:f[__] :> ZTransform[pattern, n, z]]

Решим уравнение относительно образа функции f — ZTransform[f[n],n,z]:

fZTransformed = ReplaceAll[
	ZTransform[f @ n, n, z],
	Part[Solve[fibonacciEqZTransformed, ZTransform[f @ n, n, z]], 1]
]

Выполним обратное Z-преобразование, подставив одновременно начальные условия (заменим n на n-1 в финальном выражении, чтобы наша последовательность имела правильную индексацию (с первого, а не нулевого члена):

ReplaceAll[InverseZTransform[fZTransformed /. initialConditions, z, n],
	n -> (n - 1)
]

Естестевенно это можно автоматизировать, создав свой аналог RSolve:

myRSolve[eq_, initials_, f_, n_] := Module[
	{z, initialsInner, eqZTransformed, fZTransformed},
	initialsInner = ReplaceAll[initials, f[x_] :> f[x - 1]];
	eqZTransformed = ReplaceAll[eq, pattern:f[__] :> ZTransform[pattern, n, z]];
	fZTransformed = ReplaceAll[ZTransform[f @ n, n, z],
		Part[Solve[eqZTransformed, ZTransform[f @ n, n, z]], 1]
	];
	FullSimplify[
		InverseZTransform[fZTransformed /. initialsInner, z, n] /. n -> (n - 1)
	]
];

myRSolve[
	{
		f[n + 2]==(2 * f[n + 1]) + -(5 * f[n])
	},
	{f[1] -> 20, f[2] -> 0},
	f, n
]

RSolve[
	{
		f[n + 2]==(2 * f[n + 1]) + -(5 * f[n]),
		f[1]==20,
		f[2]==0
	},
	f, n
]

Но, конечно, RSolve содержит намного больше возможностей для решения самых разных дискретных уравнений, на которых мы не будем останавливаться подробнее:

RSolve[a[n]==(n * a[n]) + n, a, n],
RSolve[
	{
		a[n + 1]==(2 * a[n]) + (3 * a[n]) + 4,
		a[0]==0
	},
	a, n
],
RSolve[
	y[n + 1 * 3]==(2 * y[n + 1 * 6]) + n * 2,
	y, n
]

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

Производящая функция последовательности

это такая функция

, разложение которой в ряд Тейлора (или, более широко, Лорана) имеет вид —

. Другими словами, коэффициенты при степенях x в разложении функции в ряд задают нашу последовательность.

Скажем, функция

является производящей функцией последовательности 1, 1, 1, 1, …:

Series[1 / (1 + -x), {x, 0, 10}]

А функция

является производящей функцией последовательности Фибоначчи 1, 1, 2, 3, 5, 8, 13, …:

Series[(1 * 1) + (-x) + -(x * 2),
	{x, 0, 10}
]

Ещё есть разновидность производящей функции — экспоненциальная производящая функция, которая для последовательности

имеет вид —

.

Скажем, для последовательностей 1, 1, 1, 1… и 1, 1, 2, 3, 5, 8, 13,… экспоненциальные производящие функции таковы —

и

:

ReplaceAll[Normal[Series[E ^ x, {x, 0, 10}]],
	Power[x, n_] :> ((x ^ n) * Factorial[n])
]

ReplaceAll[
	Normal[
		FullSimplify[
			Series[
				Plus[E,
					(-(2 * x * 1)) + 5 * ((E * 5 * x) - 1) * 5
				],
				{x, 0, 10}
			]
		]
	],
	Power[x, n_] :> ((x ^ n) * Factorial[n])
]

Производящую функцию в Wolfram Language можно найти двумя функциями — GeneratingFunction и FindGeneratingFunction (экспоненциальную с помощью ExponentialGeneratingFunction):

GeneratingFunction[-(m * Factorial[n]), {n, m}, {x, y}]

TraditionalForm[
	FullSimplify[
		ExponentialGeneratingFunction[-(n * Factorial[n - 1] * Factorial[2 * n]), n, x]
	]
]

Есть много методов поиска общего члена последовательности с помощью производящих функций. Не будем подробно останавливаться на этом, скажем, только что неплохая теория есть на сайте genfunc.ru.

Один из методов похож на Z-преобразование:

generatingFEq = ReplaceAll[
	f[n + 2]==f[n + 1] + f[n],
	pattern:f[__] :> GeneratingFunction[pattern, n, z]
],
generatingF = ReplaceAll[
	GeneratingFunction[f @ n, n, z],
	Part[Solve[generatingFEq, GeneratingFunction[f @ n, n, z]], 1]
],
nthTerm = SeriesCoefficient[generatingF, {z, 0, n}],
FullSimplify[
	ReplaceAll[ReplaceAll[nthTerm, {f[0] -> 1, f[1] -> 1}],
		n -> (n - 1)
	],
	GreaterEqual[n, 1]
]

OEIS — Онлайн-энциклопедия целочисленных последовательностей и интеграция с Wolfram Language

В интернете доступна совершенно потрясающая коллекция числовых последовательностей — OEIS (On-Line Encyclopedia of Integer Sequences). Она была создана Нилом Слоуном во время его исследовательской деятельности в AT&T Labs. В OEIS хранится информация о целочисленных последовательностях, представляющих интерес как для любителей, так и для специалистов в математике, комбинаторике, теории чисел, теории игр, физике, химии, биологии, информатике. На данный момент там собрано 329085 последовательностей. Запись в OEIS включает в себя первые элементы последовательности, ключевые слова, математическое описание, фамилии авторов, ссылки на литературу; присутствует возможность построения графика или проигрывания музыкального представления последовательности. Поиск в базе данных может осуществляться по ключевым словам и по подпоследовательности.

Недавно появилась интеграция с этой базой внутри Wolfram Language (при использовании важно понимать, что это разработка пользователей — с недавного времени можно выгружать свой код в репозиторий Wolfram Function Repository). Достаточно просто указать номер интересующей вас последовательности или список номеров.

OEISSequenceData = ResourceFunction @ "OEISSequenceData";

OEISSequence = ResourceFunction @ "OEISSequence";

ResourceFunction[«OEISSequence»] — просто выдает первые члены последовательности:

Hold @ OEISSequence @ "A666"

ResourceFunction[«OEISSequenceData»] — выдает датасет с полной информацией из базы:

sequenceData[666] = OEISSequenceData[666, "Dataset"]

Скажем, можно «вытащить» код на языке Wolfram Language:

Hold @ Normal @ sequenceData[666]["CodeWolframLanguageStrings"]

Или набор случайно выбранных последовательностей с интересующей по ним информацией:

randomSequences = Dataset @ Map[
	Normal,
	OEISSequenceData[RandomInteger[{1, 300000}, 10], "Dataset"]
];

Function[
	Framed[#, FrameStyle -> None, FrameMargins -> 5, Background -> White]
][
	Grid[
		Join[
			{
				Map[Style[#, Bold, 18]&,
					{"Название", "Формулы", "Ссылки", "Первые члены", "График первых членов"}
				]
			},
			Map[
				Function[
					Map[
						Function[
							TextCell[#, LineIndent -> 0, FontSize -> 12, FontFamily -> "Open Sans Light"]
						],
						{
							Style[Part[#, 1], 16],
							Row[Part[#, 4], "n"],
							Row[Part[#, 3], "n"],
							Style[Row[Part[#, 2], "; "], 10],
							ListLinePlot[Part[#, 2], ImageSize -> Full]
						}
					]
				],
				Values @ Normal @ randomSequences[All, {"Name", "Sequence", "References", "Formulae"}]
			]
		],
		Dividers -> {{None, {LightGray}, None}, {None, {LightGray}, None}},
		ItemStyle -> Directive[FontSize -> 12, FontFamily -> "Open Sans Light"],
		ItemSize -> {{15, 25, 10, 15, 15}, Automatic},
		Alignment -> {Left, Center},
		Background -> {None, {LightOrange, White}}
	]
]

Поиск потенциально возможной формулы

Наконец, хотелось бы отметить функцию FindFormula, которая по заданному набору чисел строит формулу, которая их может описать. Примем зависимостей подобрать можно много и из разных классов функций.

data = Table[
  {
    x,
    Sin[2 * x] + Cos[x] + RandomVariate[NormalDistribution[0, 0.2]]
  },
  {x, RandomReal[{-10, 10}, 1000]}
];

ListPlot[data, Background -> White, ImageSize -> 600]

formulas = FindFormula[data, x]

Как видно, Wolfram Language подобрал функцию, очень близкую к той, на основе которой были построены «зашумленные» данные, а именно — Sin[2x]+Cos[x]:

Plot[formulas,
	{x, -10, 10},
	PlotStyle -> AbsoluteThickness[3],
	Prolog -> {AbsolutePointSize[5], Gray, Point @ data},
	Background -> White, ImageSize -> 800, PlotLegends -> "Expressions"
]

Можно построить и большее количество зависимостей, скажем, 10:

formulas = FindFormula[data, x, 10]

Plot[formulas,
	{x, -10, 10},
	PlotStyle -> AbsoluteThickness[3],
	Prolog -> {AbsolutePointSize[5], LightGray, Point @ data},
	Background -> White, ImageSize -> 800, PlotLegends -> "Expressions"
]

Стоит отметить, что есть функция, аналогичная по функционалу, которая ищет вероятностное распределение — FindDistribution.

Для сотрудничества — пишите личное сообщение на Хабре или в мою группу ВКонтакте.
Канал YouTube — вебинары и обучающие ролики.
Регистрация на новые курсы. Готовый онлайн курс.

Определения

Для рекуррентного соотношения, которому удовлетворяет последовательность мы часто хотим получить выражение для . Например, для рекуррентного соотношения, задающего числа Фибоначчи:

член может быть записан следующим образом:

Для этого можно использовать метод производящих функций (англ. generating function method).

Метод производящих функций

Алгоритм получения выражения для чисел , удовлетворяющих рекуррентному соотношению, с помощью производящих функций cостоит из шагов.

1. Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен ):

2. Домножить каждую строчку на в соответствующей степени () и сложить все выражения, многоточие надо рассматривать как множество из выражений, где . В левой части получится сумма — это производящая функция, назовем ее . Правую часть преобразовать так, чтобы она превратилась в выражение, включающее .
3. Решить полученное уравнение, получив для выражение в замкнутом виде.
4. Разложить в степенной ряд, коэффициент при будет искомым выражением для .

Примеры

пример

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

Задано линейное однородное рекуррентное соотношение порядка с постоянными коэффициентами:

Порядок соотношения — это его «глубина», то есть количество предшествующих элементов, требуемых для вычисления элемента с номером . В данном случае порядок равен , так как для вычисления требуется знать и .

Будем искать производящую функцию последовательности в виде

с этой целью умножим верхнюю строчку в записи рекуррентного соотношения на , следующую — на и последнюю — на :

Теперь сложим все уравнения для всех значений :

Левая часть уравнения в точности равна , а в правой части есть суммы, очень похожие на функцию , но не равные ей. Эти суммы нужно привести к виду . Начнём с первой:

Равенство получатся вынесением в первой степени за знак суммы, это необходимо, чтобы уровнять степень переменной и индекс переменной a внутри суммы. Действие — изменение индекса суммирования, которое позволяет избавиться от . Равенство получается, если прибавить и снова отнять значение , чтобы получить полную сумму от до . Равенство справедливо в силу того, что .

Аналогичные манипуляции со второй суммой дают нам выражение

Теперь наше исходное уравнение для производящей функции принимает вид:

откуда получаем производящую функцию последовательности в замкнутом виде:

Отыскав производящую функцию в замкнутом виде, её нужно снова разложить в ряд. Это можно сделать разными способами, но самый простой из них — разбить всю дробь на простые дроби и применить формулу для разложения . Итак, разложим знаменатель функции на множители:

Теперь разобьём дробь на сумму простых дробей:

Вспомним разложение для простейшей рациональной функции:

Из этого разложения следует, что

Таким образом,

С другой стороны, мы искали в виде

поэтому, в силу равенства рядов, (для ).

пример: числа Фибоначчи

Рассмотрим рекуррентное соотношение для чисел Фибоначчи:

Первый шаг алгоритма мы уже выполнили, записав рекуррентное соотношение. Выполним второй шаг:

Складываем все строчки:

Третий шаг алгоритма требует привести все суммы к замкнутому виду:

откуда получаем замкнутое выражение для производящей функции:

Осталось разложить её в ряд (чего требует четвёртый шаг алгоритма). С этой целью нужно разложить знаменатель на множители. Найдем корни уравнения:

Таким образом,

Нам известно разложение следующей рациональной функции:

Рассмотрим первую дробь и поделим в ней числитель и знаменатель на :

Аналогично (но с делением на ) поступим со второй дробью:

Таким образом,

и, следовательно,

Данное выражение можно упростить, если обратить внимание на то, что , и . Подставим и в предыдущее выражение:

пример

Найдём производящую функцию для последовательности квадратов чисел Фибоначчи: $1, 1, 4, 9, 25, ldots, f_k^2,ldots$.

По определению последовательности Фибоначчи выполняется:

Возведя в квадрат и сложив, получим:

Обозначим рассматриваемую последовательность , а её члены , тогда:

Рекуррентное соотношение:

Приведём суммы к замкнутому виду:

откуда получаем замкнутое выражение для производящей функции:

пример

Рассмотрим следующее рекуррентное соотношение:

Следующие действия аналогичны тем, которые мы делали для чисел Фибоначчи:

Вспомним, что

поэтому

Последняя сумма может быть свёрнута:

Подставив свёрнутое выражение обратно, имеем,

Таким образом, наше последнее уравнение примет вид

Это уравнение для производящей функции. Из него выражаем :

Разложим знаменатель на множители и разобьём дробь на сумму простых дробей:

Дальше мы знаем что делать со всеми этими дробями, кроме, разве лишь, первой. Рассмотрим её (без множителя) подробнее:

Теперь соберём ответ:

Значит,

См. также

• Производящая функция
• Арифметические действия с формальными степенными рядами

Источники информации

• Решение рекуррентных соотношений

Была ли эта статья полезной?