On asymptotics of solution of nonlinear difference equation of convolution type

Abstract

Nonlinear difference equations appear in many problems of probability theory, computer science, and combinatorics. In this paper, a nonlinear difference equation of the convolution type with parameters is considered. Asymptotics of solutions of such equations are used for the enumeration of labeled connected graphs. To obtain the asymptotics, we apply Bender’s theorem for the coefficients of formal power series.

Full Text

Нелинейные разностные уравнения типа свертки возникают в теории вероятности при изучении броуновского движения (см. [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]).