Об асимптотике решения нелинейного разностного уравнения типа свертки

Аннотация

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

Полный текст

Нелинейные разностные уравнения типа свертки возникают в теории вероятности при изучении броуновского движения (см. [12, 14]), информатике при анализе алгоритмов поиска (см. [10]) и хеширования (см. [11]) и комбинаторике при перечислении помеченных графов (см. [19]). Асимптотика решений таких уравнений исследовалась в [9, 10, 16, 17].

Рассмотрим нелинейное разностное уравнение типа свертки

$a_{n+1}\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}n+\alpha \mathrm{<mo\; stretchy="false">)</mo>}{a}_n+\beta {\displaystyle \sum _{s\mathrm{<mo>=</mo>0}}^n}{a}_s{a}_{n-s}\mathrm{,}n\ge \mathrm{0<mo>;</mo>}$ (1)

$a_0\mathrm{<mo>=</mo>}a$, где $\alpha$, $\beta$ $—$ параметры, $\beta \ne 0$.

Асимптотика решений уравнений такого типа используется при перечислении помеченных связных графов (см. [1, 4, 7, 18, 19]) и в теории случайных графов (см. [13]).

Введем производящую функцию (формальный степенной ряд) для последовательности чисел $\mathrm{<mo>\{</mo>}{a}_n\mathrm{<mo>\}</mo>}$, определяемой уравнением (1):

$A\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{n\mathrm{<mo>=</mo>0}}^{\infty }}{a}_n{x}^n\mathrm{.}$

Теорема 1. Пусть $\Phi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{,}b\mathrm{<mo>;</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}$ $—$ вырожденная гипергеометрическая функция Куммера. Тогда верна формула

$A\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\frac{x}{\beta }\mathrm{<mo\; stretchy="false">(</mo>}\ln \Phi \left(a\beta \mathrm{,1}-\alpha \mathrm{<mo>;</mo>}-\frac{1}{x}\right){)}^{\prime }\mathrm{.}$ (2)

Доказательство. Умножим обе части уравнения (1) на $x^n$ и просуммируем по $n$ от $0$ до $\infty$:

${\displaystyle \sum _{n\mathrm{<mo>=</mo>0}}^{\infty }}{a}_{n+1}{x}^n\mathrm{<mo>=</mo>}{\displaystyle \sum _{n\mathrm{<mo>=</mo>0}}^{\infty }}n{a}_n{x}^n+\alpha {\displaystyle \sum _{n\mathrm{<mo>=</mo>0}}^{\infty }}{a}_n{x}^n+\beta {\displaystyle \sum _{n\mathrm{<mo>=</mo>0}}^{\infty }}{\displaystyle \sum _{s\mathrm{<mo>=</mo>0}}^n}{a}_s{a}_{n-s}{x}^n\mathrm{.}$

Теперь имеем

${\displaystyle \sum _{n\mathrm{<mo>=</mo>0}}^{\infty }}{a}_{n+1}{x}^n\mathrm{<mo>=</mo>}\frac{1}{x}{\displaystyle \sum _{n\mathrm{<mo>=</mo>0}}^{\infty }}{a}_{n+1}{x}^{n+1}\mathrm{<mo>=</mo>}\frac{1}{x}\mathrm{<mo\; stretchy="false">(</mo>}{\displaystyle \sum _{n\mathrm{<mo>=</mo>0}}^{\infty }}{a}_n{x}^n-a_0\mathrm{<mo\; stretchy="false">)</mo>,}{\displaystyle \sum _{n\mathrm{<mo>=</mo>0}}^{\infty }}n{a}_n{x}^n\mathrm{<mo>=</mo>}x\mathrm{<mo\; stretchy="false">(</mo>}{\displaystyle \sum _{n\mathrm{<mo>=</mo>0}}^{\infty }}{a}_n{x}^n{)}^{\prime }\mathrm{<mo>=</mo>}x{A}^{\prime }\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>,}$

${\displaystyle \sum _{n\mathrm{<mo>=</mo>0}}^{\infty }}{\displaystyle \sum _{s\mathrm{<mo>=</mo>0}}^n}{a}_s{a}_{n-s}{x}^n\mathrm{<mo>=</mo>}{A}^2\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>,}\frac{1}{x}\mathrm{<mo\; stretchy="false">(</mo>}A\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}-a_0\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}x{A}^{\prime }\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}+\alpha A\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}+\beta A^2\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>.}$

Получили для $A\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}$ общее уравнение Риккати

$A^{\prime }\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}-\frac{\beta }{x}{A}^2\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}+\frac{1}{x}\mathrm{<mo\; stretchy="false">(</mo>}\frac{1}{x}-\alpha \mathrm{<mo\; stretchy="false">)</mo>}A\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}-\frac{a}{x^2}\mathrm{,}A\mathrm{<mo\; stretchy="false">(</mo>0<mo\; stretchy="false">)</mo><mo>=</mo>}a\mathrm{.}$

После замены переменной

$t\mathrm{<mo>=</mo>}-\frac{1}{x}\mathrm{,}y\mathrm{<mo\; stretchy="false">(</mo>}t\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}A\left(-\frac{1}{t}\right)\mathrm{,}{A}^{\prime }\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{y}^{\prime }{t^{\prime }}_x\mathrm{<mo>=</mo>}{t}^2{y}^{\prime }$

оно принимает вид

$y^{\prime }\mathrm{<mo>=</mo>}\frac{\beta }{t}{y}^2+\mathrm{<mo\; stretchy="false">(</mo>}\frac{\alpha }{t}+\mathrm{1<mo\; stretchy="false">)</mo>}y-a\mathrm{,}y\mathrm{<mo\; stretchy="false">(</mo>}t\mathrm{<mo\; stretchy="false">)</mo>}\underset{t\to -\infty }{\to }a\mathrm{.}$

Известно (см. [5, с. 42]), что общее уравнение Риккати

$y^{\prime }\mathrm{<mo>=</mo>}f\mathrm{<mo\; stretchy="false">(</mo>}t\mathrm{<mo\; stretchy="false">)</mo>}{y}^2+g\mathrm{<mo\; stretchy="false">(</mo>}t\mathrm{<mo\; stretchy="false">)</mo>}y+h\mathrm{<mo\; stretchy="false">(</mo>}t\mathrm{<mo\; stretchy="false">)</mo>}$

заменой

$u\mathrm{<mo\; stretchy="false">(</mo>}t\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\exp \left(-{\displaystyle \int }fydt\right)$

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

${u^{\prime }}^{\prime }-\left(\frac{f^{\prime }}{f}+g\right)u^{\prime }+fhu\mathrm{<mo>=</mo>0.}$

В нашем случае

$f\mathrm{<mo\; stretchy="false">(</mo>}t\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\frac{\beta }{t}\mathrm{,}g\mathrm{<mo\; stretchy="false">(</mo>}t\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\frac{\alpha }{t}+\mathrm{1,}h\mathrm{<mo\; stretchy="false">(</mo>}t\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}-a\mathrm{,}u\mathrm{<mo\; stretchy="false">(</mo>}t\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\exp \left(-{\displaystyle \int }\frac{\beta }{t}ydt\right)\mathrm{,}y\mathrm{<mo>=</mo>}-\frac{t}{\beta }\mathrm{<mo\; stretchy="false">(</mo>}\ln u{)}^{\prime }\mathrm{,}$

${u^{\prime }}^{\prime }-\left(-\frac{1}{t}+\frac{\alpha }{t}+1\right)u^{\prime }-\frac{a\beta }{t}u\mathrm{<mo>=</mo>0,}t{u^{\prime }}^{\prime }+\mathrm{<mo\; stretchy="false">(</mo>1}-\alpha -t\mathrm{<mo\; stretchy="false">)</mo>}{u}^{\prime }-au\mathrm{<mo>=</mo>0.}$

Так как одно из решений уравнения

$t{u^{\prime }}^{\prime }+\mathrm{<mo\; stretchy="false">(</mo>}b-t\mathrm{<mo\; stretchy="false">)</mo>}{u}^{\prime }-au\mathrm{<mo>=</mo>0}$

имеет вид $u\mathrm{<mo\; stretchy="false">(</mo>}t\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\Phi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{,}b\mathrm{,}t\mathrm{<mo\; stretchy="false">)</mo>}$, где $\Phi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{,}b\mathrm{,}t\mathrm{<mo\; stretchy="false">)</mo>}$ $—$ вырожденная гипергеометрическая функция (см. [5, с. 288]), то имеем $u\mathrm{<mo\; stretchy="false">(</mo>}t\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\Phi \mathrm{<mo\; stretchy="false">(</mo>}a\beta \mathrm{,1}-\alpha \mathrm{<mo>;</mo>}t\mathrm{<mo\; stretchy="false">)</mo>}$.

Известны формулы

${\Phi }^{\prime }\mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{,}b\mathrm{,}t\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\frac{a}{b}\Phi \mathrm{<mo\; stretchy="false">(</mo>}a+\mathrm{1,}b+\mathrm{1,}t\mathrm{<mo\; stretchy="false">)</mo>,}\Phi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{,}b\mathrm{,}t\mathrm{<mo\; stretchy="false">)</mo>}\sim \frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}b-a\mathrm{<mo\; stretchy="false">)</mo>}}{\mathrm{<mo\; stretchy="false">(</mo>}-t\mathrm{<mo\; stretchy="false">)</mo>}}^{-a}$

при фиксированных значениях $a$, $b$ и $t\to -\infty$ (см. [2, с. 242, 266]). Поэтому получим

$y\mathrm{<mo\; stretchy="false">(</mo>}t\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}-\frac{t}{\beta }\mathrm{<mo\; stretchy="false">(</mo>}\ln \Phi \mathrm{<mo\; stretchy="false">(</mo>}a\beta \mathrm{,1}-\alpha \mathrm{<mo>;</mo>}t\mathrm{<mo\; stretchy="false">)</mo>}{)}^{\prime }\mathrm{<mo>=</mo>}-\frac{t}{\beta }\frac{{\Phi }^{\prime }\mathrm{<mo\; stretchy="false">(</mo>}a\beta \mathrm{,1}-\alpha \mathrm{<mo>;</mo>}t\mathrm{<mo\; stretchy="false">)</mo>}}{\Phi \mathrm{<mo\; stretchy="false">(</mo>}a\beta \mathrm{,1}-\alpha \mathrm{<mo>;</mo>}t\mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}-\frac{at}{1-\alpha }\frac{\Phi \mathrm{<mo\; stretchy="false">(</mo>}a\beta +\mathrm{1,2}-\alpha \mathrm{<mo>;</mo>}t\mathrm{<mo\; stretchy="false">)</mo>}}{\Phi \mathrm{<mo\; stretchy="false">(</mo>}a\beta \mathrm{,1}-\alpha \mathrm{<mo>;</mo>}t\mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{.}$

С учетом тождества для гамма-функции $\Gamma \mathrm{<mo\; stretchy="false">(</mo>}z+\mathrm{1<mo\; stretchy="false">)</mo><mo>=</mo>}z\Gamma \mathrm{<mo\; stretchy="false">(</mo>}z\mathrm{<mo\; stretchy="false">)</mo>}$, найдем

$y\mathrm{<mo\; stretchy="false">(</mo>}t\mathrm{<mo\; stretchy="false">)</mo>}\sim -\frac{at}{1-\alpha }\frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>2}-\alpha \mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">(</mo>}-t{\mathrm{<mo\; stretchy="false">)</mo>}}^{-a\beta -1}\Gamma \mathrm{<mo\; stretchy="false">(</mo>1}-\alpha -a\beta \mathrm{<mo\; stretchy="false">)</mo>}}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>1}-\alpha -a\beta \mathrm{<mo\; stretchy="false">)</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>1}-\alpha \mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">(</mo>}-t{\mathrm{<mo\; stretchy="false">)</mo>}}^{-a\beta }}\mathrm{<mo>=</mo>}\frac{a\Gamma \mathrm{<mo\; stretchy="false">(</mo>2}-\alpha \mathrm{<mo\; stretchy="false">)</mo>}}{\mathrm{<mo\; stretchy="false">(</mo>1}-\alpha \mathrm{<mo\; stretchy="false">)</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>1}-\alpha \mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}a$

при $t\to -\infty$, т.е. начальное условие выполнено. Возвращаясь к переменной $x$, имеем

$y\mathrm{<mo\; stretchy="false">(</mo>}t\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}-\frac{t}{\beta }\mathrm{<mo\; stretchy="false">(</mo>}\ln \Phi \mathrm{<mo\; stretchy="false">(</mo>}a\beta \mathrm{,1}-\alpha \mathrm{<mo>;</mo>}t\mathrm{<mo\; stretchy="false">)</mo>}{)}^{\prime }\mathrm{,}t\mathrm{<mo>=</mo>}-\frac{1}{x}\mathrm{,}x\mathrm{<mo>=</mo>}-\frac{1}{t}\mathrm{,}$

$A\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}y\left(-\frac{1}{x}\right)\mathrm{<mo>=</mo>}\frac{1}{x\beta }{\left(\ln \Phi \left(a\beta \mathrm{,1}-\alpha \mathrm{<mo>;</mo>}-\frac{1}{x}\right)\right)}_x{x^{\prime }}_t\mathrm{<mo>=</mo>}\frac{x}{\beta }\left(\ln \Phi \left(a\beta \mathrm{,1}-\alpha \mathrm{<mo>;</mo>}-\frac{1}{x}\right)\right)\mathrm{.}$

Лемма 1. Пусть

$T_n\mathrm{<mo>=</mo>}\frac{1}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n+\delta +\mathrm{1<mo\; stretchy="false">)</mo>}}{\displaystyle \sum _{k\mathrm{<mo>=</mo>0}}^n}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}k+\delta +\mathrm{1<mo\; stretchy="false">)</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n-k+\delta +\mathrm{1<mo\; stretchy="false">)</mo>.}$

Тогда для любых $\delta \ge 0$ и любых целых $n\ge 0$ верно неравенство

$T_n\le \mathrm{2<mo\; stretchy="false">(</mo>}\delta +\mathrm{2<mo\; stretchy="false">)</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}\delta +\mathrm{1<mo\; stretchy="false">)</mo>.}$ (3)

Доказательство. Введем обозначение

$S_n\mathrm{<mo>=</mo>}{T}_n\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n+\delta +\mathrm{1<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{k\mathrm{<mo>=</mo>0}}^n}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}k+\delta +\mathrm{1<mo\; stretchy="false">)</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n-k+\delta +\mathrm{1<mo\; stretchy="false">)</mo>.}$

С помощью тождества $\Gamma \mathrm{<mo\; stretchy="false">(</mo>}z+\mathrm{1<mo\; stretchy="false">)</mo><mo>=</mo>}z\Gamma \mathrm{<mo\; stretchy="false">(</mo>}z\mathrm{<mo\; stretchy="false">)</mo>}$ получим

$\mathrm{<mo\; stretchy="false">(</mo>}n+2\delta +\mathrm{1<mo\; stretchy="false">)</mo>}{S}_{n-1}\mathrm{<mo>=</mo>}{\displaystyle \sum _{k\mathrm{<mo>=</mo>0}}^{n-1}}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}k+\delta +\mathrm{1<mo\; stretchy="false">)</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n-k+\delta \mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">(</mo>}k+\delta +1+n-k+\delta \mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}$

$\mathrm{<mo>=</mo>}{\displaystyle \sum _{k\mathrm{<mo>=</mo>0}}^{n-1}}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}k+\delta +\mathrm{2<mo\; stretchy="false">)</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n-k+\delta \mathrm{<mo\; stretchy="false">)</mo>}+{\displaystyle \sum _{k\mathrm{<mo>=</mo>0}}^{n-1}}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}k+\delta +\mathrm{1<mo\; stretchy="false">)</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n-k+\delta +\mathrm{1<mo\; stretchy="false">)</mo><mo>=</mo>}$

$\mathrm{<mo>=</mo>}{\displaystyle \sum _{k\mathrm{<mo>=</mo>1}}^n}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}k+\delta +\mathrm{1<mo\; stretchy="false">)</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n-k+\delta +\mathrm{1<mo\; stretchy="false">)</mo>}+S_n-\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n+\delta +\mathrm{1<mo\; stretchy="false">)</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}\delta +\mathrm{1<mo\; stretchy="false">)</mo><mo>=</mo>2}{S}_n-2\Gamma \mathrm{<mo\; stretchy="false">(</mo>}\delta +\mathrm{1<mo\; stretchy="false">)</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n+\delta +\mathrm{1<mo\; stretchy="false">)</mo>,}$

откуда

$S_n\mathrm{<mo>=</mo>}\frac{1}{2}\mathrm{<mo\; stretchy="false">(</mo>}n+2\delta +\mathrm{1<mo\; stretchy="false">)</mo>}{S}_{n-1}+\Gamma \mathrm{<mo\; stretchy="false">(</mo>}\delta +\mathrm{1<mo\; stretchy="false">)</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n+\delta +\mathrm{1<mo\; stretchy="false">)</mo>.}$

С помощью тождества $\Gamma \mathrm{<mo\; stretchy="false">(</mo>}z+\mathrm{1<mo\; stretchy="false">)</mo><mo>=</mo>}z\Gamma \mathrm{<mo\; stretchy="false">(</mo>}z\mathrm{<mo\; stretchy="false">)</mo>}$ найдем

$T_n\mathrm{<mo>=</mo>}\frac{\mathrm{<mo\; stretchy="false">(</mo>}n+2\delta +\mathrm{1<mo\; stretchy="false">)</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n+\delta \mathrm{<mo\; stretchy="false">)</mo>}}{2\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n+\delta +\mathrm{1<mo\; stretchy="false">)</mo>}}{T}_{n-1}+\Gamma \mathrm{<mo\; stretchy="false">(</mo>}\delta +\mathrm{1<mo\; stretchy="false">)</mo>,}{T}_n\mathrm{<mo>=</mo>}\frac{n+2\delta +1}{\mathrm{2<mo\; stretchy="false">(</mo>}n+\delta \mathrm{<mo\; stretchy="false">)</mo>}}{T}_{n-1}+\Gamma \mathrm{<mo\; stretchy="false">(</mo>}\delta +\mathrm{1<mo\; stretchy="false">)</mo>.}$

Применим индукцию по $n$.

Так как $\mathrm{1<mo><</mo>2<mo\; stretchy="false">(</mo>}\delta +\mathrm{2<mo\; stretchy="false">)</mo>}$, $\mathrm{1<mo><</mo>}\delta +2$ при $\delta \ge 0$ и $\Gamma \mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>></mo>0}$ при $x\mathrm{<mo>></mo>0}$ (см. [15, с. 138]), имеем

$T_0\mathrm{<mo>=</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}\delta +\mathrm{1<mo\; stretchy="false">)</mo><mo><</mo>2<mo\; stretchy="false">(</mo>}\delta +\mathrm{2<mo\; stretchy="false">)</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}\delta +\mathrm{1<mo\; stretchy="false">)</mo>,}{T}_1\mathrm{<mo>=</mo>2}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}\delta +\mathrm{1<mo\; stretchy="false">)</mo><mo><</mo>2<mo\; stretchy="false">(</mo>}\delta +\mathrm{2<mo\; stretchy="false">)</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}\delta +\mathrm{1<mo\; stretchy="false">)</mo>,}$

и неравенство (3) верно при $n\mathrm{<mo>=</mo>0}$ и $n\mathrm{<mo>=</mo>1}$.

Предположим, что неравенство (3) верно для $n\mathrm{<mo>=</mo>}m-1\ge 1$, и докажем его для $n\mathrm{<mo>=</mo>}m\ge 2$:

$T_m\mathrm{<mo>=</mo>}\frac{m+2\delta +1}{\mathrm{2<mo\; stretchy="false">(</mo>}m+\delta \mathrm{<mo\; stretchy="false">)</mo>}}{T}_{m-1}+\Gamma \mathrm{<mo\; stretchy="false">(</mo>}\delta +\mathrm{1<mo\; stretchy="false">)</mo>}\le \frac{m+\delta +\delta +1}{\mathrm{2<mo\; stretchy="false">(</mo>}m+\delta \mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{2<mo\; stretchy="false">(</mo>}\delta +\mathrm{2<mo\; stretchy="false">)</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}\delta +\mathrm{1<mo\; stretchy="false">)</mo>}+\Gamma \mathrm{<mo\; stretchy="false">(</mo>}\delta +\mathrm{1<mo\; stretchy="false">)</mo><mo>=</mo>}$

$\mathrm{<mo>=</mo>}\left(\delta +3+\frac{\delta +1}{m+\delta }\mathrm{<mo\; stretchy="false">(</mo>}\delta +\mathrm{2<mo\; stretchy="false">)</mo>}\right)\Gamma \mathrm{<mo\; stretchy="false">(</mo>}\delta +\mathrm{1<mo\; stretchy="false">)</mo>}\le \left(\delta +3+\frac{\delta +1}{2+\delta }\mathrm{<mo\; stretchy="false">(</mo>}\delta +\mathrm{2<mo\; stretchy="false">)</mo>}\right)\mathrm{<mo>=</mo>2<mo\; stretchy="false">(</mo>}\delta +\mathrm{2<mo\; stretchy="false">)</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}\delta +\mathrm{1<mo\; stretchy="false">)</mo>.}$

Теорема 2. Пусть $\mathrm{<mo>\{</mo>}{a}_n\mathrm{<mo>\}</mo>}$ $—$ последовательность чисел, определяемая уравнением (1). Тогда при $2a\beta +\alpha \ge 1$ и $n\to \infty$ верна асимптотическая формула

$a_n\sim \frac{n^{2a\beta +\alpha -1}n\mathrm{<mo>!</mo>}}{\beta \Gamma \mathrm{<mo\; stretchy="false">(</mo>}a\beta \mathrm{<mo\; stretchy="false">)</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}a\beta +\alpha \mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{.}$ (4)

Доказательство. Отметим, что гамма-функция $\Gamma \mathrm{<mo\; stretchy="false">(</mo>}z\mathrm{<mo\; stretchy="false">)</mo>}$ определена при $z\ne \mathrm{0,}-\mathrm{1,}-\mathrm{2,}\dots$. Поэтому в формуле (4) начальное значение $a$ и параметры $\alpha \mathrm{,}\beta$ должны быть такими, чтобы $a\beta \ne \mathrm{0,}-\mathrm{1,}-\mathrm{2,}\dots$ и $a\beta +\alpha \ne \mathrm{0,}-\mathrm{1,}-\mathrm{2,}\dots$.

Известно асимптотическое разложение вырожденной гипергеометрической функции $\Phi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{,}b\mathrm{<mo>;</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}$ при фиксированных значениях $a\mathrm{,}b$ и $\mathrm{<mo>|</mo>}x\mathrm{<mo>|</mo>}\to \infty$ (см. [6, с. 59]):

$\Phi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{,}b\mathrm{<mo>;</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}\sim \frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}b-a\mathrm{<mo\; stretchy="false">)</mo>}}{\mathrm{<mo\; stretchy="false">(</mo>}-x\mathrm{<mo\; stretchy="false">)</mo>}}^{-a}{\displaystyle \sum _{n\mathrm{<mo>=</mo>0}}^{\infty }}\frac{{\mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo>}}_n{\mathrm{<mo\; stretchy="false">(</mo>}a-b+\mathrm{1<mo\; stretchy="false">)</mo>}}_n}{n\mathrm{<mo>!</mo>}}{\mathrm{<mo\; stretchy="false">(</mo>}-x\mathrm{<mo\; stretchy="false">)</mo>}}^{-n}\mathrm{,}$

где ${\mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo>}}_n\mathrm{<mo>=</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}a+n\mathrm{<mo\; stretchy="false">)</mo><mo>/</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo>}$ $—$ символ Похгаммера. Поэтому в силу формулы (2) имеем

$A\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\frac{x}{\beta }\left(\ln \Phi \left(a\beta \mathrm{,1}-\alpha \mathrm{<mo>;</mo>}-\frac{1}{x}\right)\right)\mathrm{<mo>=</mo>}\frac{x}{\beta }\left(\ln \frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>1}-\alpha \mathrm{<mo\; stretchy="false">)</mo>}}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>1}-\alpha -a\beta \mathrm{<mo\; stretchy="false">)</mo>}}{x}^{a\beta }{\displaystyle \sum _{n\mathrm{<mo>=</mo>0}}^{\infty }}\frac{{\mathrm{<mo\; stretchy="false">(</mo>}a\beta \mathrm{<mo\; stretchy="false">)</mo>}}_n{\mathrm{<mo\; stretchy="false">(</mo>}a\beta +\alpha \mathrm{<mo\; stretchy="false">)</mo>}}_n}{n\mathrm{<mo>!</mo>}}{x}^n\right)\mathrm{<mo>=</mo>}$

$\mathrm{<mo>=</mo>}\frac{x}{\beta }\left(\ln \frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>1}-\alpha \mathrm{<mo\; stretchy="false">)</mo>}}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>1}-\alpha -a\beta \mathrm{<mo\; stretchy="false">)</mo>}}{x}^{a\beta }\right)+\frac{x}{\beta }\left(\ln {\displaystyle \sum _{n\mathrm{<mo>=</mo>0}}^{\infty }}\frac{{\mathrm{<mo\; stretchy="false">(</mo>}a\beta \mathrm{<mo\; stretchy="false">)</mo>}}_n{\mathrm{<mo\; stretchy="false">(</mo>}a\beta +\alpha \mathrm{<mo\; stretchy="false">)</mo>}}_n}{n\mathrm{<mo>!</mo>}}{x}^n\right)\mathrm{<mo>=</mo>}$

$\mathrm{<mo>=</mo>}a+\frac{x}{\beta }\left(\ln \mathrm{<mo\; stretchy="false">(</mo>1}+{\displaystyle \sum _{n\mathrm{<mo>=</mo>1}}^{\infty }}{G}_n{x}^n\mathrm{<mo\; stretchy="false">)</mo>}\right)\mathrm{<mo>=</mo>}a+\frac{x}{\beta }\left({\displaystyle \sum _{n\mathrm{<mo>=</mo>1}}^{\infty }}{g}_n{x}^n\right)\mathrm{,}$

где введено обозначение

$G_n\mathrm{<mo>=</mo>}\frac{{\mathrm{<mo\; stretchy="false">(</mo>}a\beta \mathrm{<mo\; stretchy="false">)</mo>}}_n{\mathrm{<mo\; stretchy="false">(</mo>}a\beta +\alpha \mathrm{<mo\; stretchy="false">)</mo>}}_n}{n\mathrm{<mo>!</mo>}}\mathrm{<mo>=</mo>}\frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n+a\beta \mathrm{<mo\; stretchy="false">)</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n+a\beta +\alpha \mathrm{<mo\; stretchy="false">)</mo>}}{n\mathrm{<mo>!</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}a\beta \mathrm{<mo\; stretchy="false">)</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}a\beta +\alpha \mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{.}$ (5)

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

$G\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{n\mathrm{<mo>=</mo>0}}^{\infty }}{G}_n{x}^n\mathrm{,}g\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{n\mathrm{<mo>=</mo>0}}^{\infty }}{g}_n{x}^n$

связаны функциональным уравнением $F\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{,}G\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>=</mo>}g\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}$. Из теоремы Бендера (см. [8]) следует, что при $n\to \infty$ верна асимптотика

$g_n\sim F_y\mathrm{<mo\; stretchy="false">(</mo>0,0<mo\; stretchy="false">)</mo>}{G}_n$

при условиях, когда $F\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{,}y\mathrm{<mo\; stretchy="false">)</mo>}$ аналитична в точке $\mathrm{<mo\; stretchy="false">(</mo>0,0<mo\; stretchy="false">)</mo>}$, и при $n\to \infty$ верны соотношения

$G_{n-1}\mathrm{<mo>=</mo>}o\mathrm{<mo\; stretchy="false">(</mo>}{G}_n\mathrm{<mo\; stretchy="false">)</mo>,}{\displaystyle \sum _{k\mathrm{<mo>=</mo>1}}^{n-1}}\mathrm{<mo>|</mo>}{G}_k{G}_{n-k}\mathrm{<mo>|</mo><mo>=</mo>}O\mathrm{<mo\; stretchy="false">(</mo>}{G}_{n-1}\mathrm{<mo\; stretchy="false">)</mo>}\mathrm{.}$ (6)

В нашем случае функция $F\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{,}y\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}ln\mathrm{<mo\; stretchy="false">(</mo>1}+y\mathrm{<mo\; stretchy="false">)</mo>}$ аналитична в точке $\mathrm{<mo\; stretchy="false">(</mo>0,0<mo\; stretchy="false">)</mo>}$. Из (5) с помощью тождества $\Gamma \mathrm{<mo\; stretchy="false">(</mo>}z+\mathrm{1<mo\; stretchy="false">)</mo><mo>=</mo>}z\Gamma \mathrm{<mo\; stretchy="false">(</mo>}z\mathrm{<mo\; stretchy="false">)</mo>}$ найдем при $n\to \infty$ 

$\frac{G_{n-1}}{G_n}\mathrm{<mo>=</mo>}\frac{n\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n-1+a\beta \mathrm{<mo\; stretchy="false">)</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n-1+a\beta +\alpha \mathrm{<mo\; stretchy="false">)</mo>}}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n+a\beta \mathrm{<mo\; stretchy="false">)</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n+a\beta +\alpha \mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}\frac{n}{\mathrm{<mo\; stretchy="false">(</mo>}n-1+a\beta \mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">(</mo>}n-1+a\beta +\alpha \mathrm{<mo\; stretchy="false">)</mo>}}\sim \frac{1}{n}\mathrm{<mo>=</mo>}o\mathrm{<mo\; stretchy="false">(</mo>1<mo\; stretchy="false">)</mo>.}$

Из асимптотики для гамма-функции (см. [2, с. 62]) имеем $\Gamma \mathrm{<mo\; stretchy="false">(</mo>}z+\epsilon \mathrm{<mo\; stretchy="false">)</mo>}\sim z^{\epsilon }\Gamma \mathrm{<mo\; stretchy="false">(</mo>}z\mathrm{<mo\; stretchy="false">)</mo>}$ при фиксированном $\epsilon$ и $z\to \infty$. Поэтому при $n\to \infty$ получим

$G_n\sim \frac{n^{a\beta }\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}{n}^{a\beta +\alpha }\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}{n\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}a\beta \mathrm{<mo\; stretchy="false">)</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}a\beta +\alpha \mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}\frac{n^{2a\beta +\alpha -1}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}a\beta \mathrm{<mo\; stretchy="false">)</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}a\beta +\alpha \mathrm{<mo\; stretchy="false">)</mo>}}\sim \frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n+2a\beta +\alpha -\mathrm{1<mo\; stretchy="false">)</mo>}}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}a\beta \mathrm{<mo\; stretchy="false">)</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}a\beta +\alpha \mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}C\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n+\delta \mathrm{<mo\; stretchy="false">)</mo>,}$

где использовано обозначение $\delta \mathrm{<mo>=</mo>2}a\beta +\alpha -1\ge 0$, $C\mathrm{<mo>=</mo>1<mo>/</mo><mo\; stretchy="false">(</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}a\beta \mathrm{<mo\; stretchy="false">)</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}a\beta +\alpha \mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>></mo>0}$. Следовательно, существуют такие константы $c_1\mathrm{<mo>></mo>0}$, $c_2\mathrm{<mo>></mo>0}$, что

$\mathrm{0<mo><</mo>}{c}_1\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n+\delta \mathrm{<mo\; stretchy="false">)</mo>}\le G_n\le c_2\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n+\delta \mathrm{<mo\; stretchy="false">)</mo>.}$

Теперь имеем оценки

$Q_n\mathrm{<mo>=</mo>}{\displaystyle \sum _{k\mathrm{<mo>=</mo>1}}^{n-1}}\frac{\mathrm{<mo>|</mo>}{G}_k{G}_{n-k}\mathrm{<mo>|</mo>}}{G_{n-1}}\le \frac{c_2^2}{c_1}{\displaystyle \sum _{k\mathrm{<mo>=</mo>1}}^{n-1}}\frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}k+\delta \mathrm{<mo\; stretchy="false">)</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n-k+\delta \mathrm{<mo\; stretchy="false">)</mo>}}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n+\delta -\mathrm{1<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}$

$\mathrm{<mo>=</mo>}\frac{c_2^2}{c_1}{\displaystyle \sum _{k\mathrm{<mo>=</mo>0}}^{n-2}}\frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}k+1+\delta \mathrm{<mo\; stretchy="false">)</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n-k-1+\delta \mathrm{<mo\; stretchy="false">)</mo>}}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n+\delta -\mathrm{1<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}\frac{c_2^2}{c_1}{T}_{n-2}\mathrm{.}$

В силу леммы для для любых $\delta \ge 0$ и любых целых $n\ge 0$ получим

$Q_n\le \mathrm{2<mo\; stretchy="false">(</mo>}\delta +\mathrm{2<mo\; stretchy="false">)</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}\delta +\mathrm{1<mo\; stretchy="false">)</mo>}\frac{c_2^2}{c_1}\mathrm{,}\text{т}\text{.е}\text{.}{\displaystyle \sum _{k\mathrm{<mo>=</mo>1}}^{n-1}}\mathrm{<mo>|</mo>}{G}_k{G}_{n-k}\mathrm{<mo>|</mo><mo>=</mo>}O\mathrm{<mo\; stretchy="false">(</mo>}{G}_{n-1}\mathrm{<mo\; stretchy="false">)</mo>.}$

Поэтому условия (6) теоремы Бендера выполнены и при $n\to \infty$ верна асимптотика

$g_n\sim G_n\mathrm{,}{a}_n\mathrm{<mo>=</mo>}\frac{n{g}_n}{\beta }\sim \frac{n{G}_n}{\beta }\sim \frac{n^{2a\beta +\alpha }\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}}{\beta \Gamma \mathrm{<mo\; stretchy="false">(</mo>}a\beta \mathrm{<mo\; stretchy="false">)</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}a\beta +\alpha \mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{,}$

что равносильно формуле (4).

Следствие 1. Пусть последовательность чисел $\mathrm{<mo>\{</mo>}{e}_n\mathrm{<mo>\}</mo>}$ определяется уравнением

$e_{n+1}\mathrm{<mo>=</mo>}\left(n+\frac{2}{3}\right)e_n+{\displaystyle \sum _{k\mathrm{<mo>=</mo>0}}^n}{e}_k{e}_{n-k}\mathrm{,}n\ge \mathrm{0,}{e}_0\mathrm{<mo>=</mo>}\frac{1}{6}\mathrm{.}$

Тогда при $n\to \infty$ верна асимптотика

$e_n\sim \frac{n\mathrm{<mo>!</mo>}}{2\pi }\mathrm{.}$ (7)

Доказательство. Из теоремы 2 при $\alpha \mathrm{<mo>=</mo>2<mo>/</mo>3}$, $\beta \mathrm{<mo>=</mo>1}$, $a\mathrm{<mo>=</mo>1<mo>/</mo>6}$ при $n\to \infty$ следует асимптотика

$e_n\sim \frac{n\mathrm{<mo>!</mo>}}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}\frac{1}{6}\mathrm{<mo\; stretchy="false">)</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}\frac{5}{6}\mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{.}$

Из функционального уравнения для гамма-функции

$\Gamma \left(\frac{1}{2}+z\right)\Gamma \left(\frac{1}{2}-z\right)\mathrm{<mo>=</mo>}\frac{\pi }{\cos \mathrm{<mo\; stretchy="false">(</mo>}\pi z\mathrm{<mo\; stretchy="false">)</mo>}}$

(см. [2, с. 18]) при $z\mathrm{<mo>=</mo>1<mo>/</mo>3}$ имеем

$\Gamma \left(\frac{1}{6}\right)\Gamma \left(\frac{5}{6}\right)\mathrm{<mo>=</mo>}\frac{\pi }{\mathrm{1<mo>/</mo>2}}\mathrm{<mo>=</mo>2}\pi \mathrm{,}$

откуда следует формула (7).

Отметим, что $e_n\mathrm{<mo>=</mo>}{d}_{n}n\mathrm{<mo>!</mo>}$, где $d_n$ $—$ константы Райта (коэффициенты Степанова$–$ Райта; см. [3, 124]), используемые во многих работах по перечислению помеченных графов (см. [4, 17, 19]) и в теории случайных графов (см. [13]).