On solving some functional equations: [Doc 347]

Abstract

(ProQuest: ... denotes formulae and/or non-USASCII text omitted; see image)

Using the notion of composita and the Lagrange inversion theorem, we present techniques for solving the following functional equation ......, where ......, ...... are generating functions and ....... Also we give some examples.

Kruchinin Advances in Dierence Equations (2015) 2015:17

DOI 10.1186/s13662-014-0347-9

*Correspondence: mailto:[email protected]

Web End [email protected] Tomsk State University of Control Systems and Radioelectronics (TUSUR), Tomsk, RussiaNational Research Tomsk Polytechnic University (TPU), Tomsk, Russia

R E S E A R C H Open Access

On solving some functional equations

Dmitry V Kruchinin*

Abstract

Using the notion of composita and the Lagrange inversion theorem, we present techniques for solving the following functional equation B(x) = H(xB(x)m), where H(x), B(x) are generating functions and m

N. Also we give some examples.

MSC: Primary 05A15; secondary 65Q20; 39B12

Keywords: composita; generating function; Lagrange inversion theorem; functional equation

1 Introduction

In this paper we study the coecients of the powers of an ordinary generating function and their properties. Using the notion of composita, we get the solution of the functional equation B(x) = H(xB(x)m), which is based on the Lagrange inversion equation, where H(x), B(x) are generating functions and m

N.

In the papers [], the author introduced the notion of composita of a given ordinary generating function F(x) = [summationtext]n> f (n)xn.

Suppose F(x) = [summationtext]n> f (n)xn is the generating function, in which there is no free term f () = . From this generating function we can write the following equation:

[bracketleftbig]F(x)[bracketrightbig]k = [summationdisplay]

n>

f ()f () f (k), ()

where Cn is a set of all compositions of an integer n, k is the composition [summationtext]k

i= i = n into

k parts exactly.

The expression F (n, k) takes a triangular form

F ,

F , F ,

F , F , F ,

F , F , F , F ,... ... ... ... ...

F n, F n, . . . . . . F n,n F n,n

2015 Kruchinin; licensee Springer. This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly credited.

F(n, k)xn. ()

The expression F(n, k) is the composita, and it is denoted by F (n, k).

Denition The composita is the function of two variables dened by

F (n, k) = [summationdisplay]

kCn

Kruchinin Advances in Dierence Equations (2015) 2015:17 Page 2 of 7

2 Lagrange inversion equation

First we consider a solution of the functional equation

A(x) = xH[parenleftbig]A(x)[parenrightbig], ()

where A(x) and H(x) are generating functions such that H(x) = [summationtext]n h(n)xn and A(x) =

[summationtext]n> a(n)xn.

In the following lemma, we give the Lagrange inversion formula, which was proved by Stanley [].

Lemma (The Lagrange inversion formula) Suppose H(x) = [summationtext]n h(n)xn with h() = , and let A(x) be dened by

A(x) = xH[parenleftbig]A(x)[parenrightbig]. ()

Then

n[bracketleftbig]xn[bracketrightbig]A(x)k = k[bracketleftbig]xnk[bracketrightbig]H(x)n, ()

where [xn]A(x)k is the coecient of xn in A(x)k and [xnk]H(x)n is the coecient of xnk in H(x)n.

By using the above Lemma , we now give the following theorem.

Theorem Suppose H(x) = [summationtext]n h(n)xn is a generating function, where h() = , H x(n, k) is the composita of the generating function xH(x), and A(x) = [summationtext]n> a(n)xn is the generat

ing function, which is obtained from the functional equation A(x) = xH(A(x)). Then the following condition holds true:

A (n, k) = knH x(n k, n). ()

Proof According to Lemma , for the solution of the functional equation A(x) = xH(A(x)), we can write

n[bracketleftbig]xn[bracketrightbig]A(x)k = k[bracketleftbig]xnk[bracketrightbig]H(x)n.

On the left-hand side, there is the composita of the generating function A(x) multiplied by n:

n[bracketleftbig]xn[bracketrightbig]A(x)k = nA (n, k).

We know that

[parenleftbig]xH(x)[parenrightbig]k = [summationdisplay]

nk

H x(n, k)xn.

Kruchinin Advances in Dierence Equations (2015) 2015:17 Page 3 of 7

Then

H x(n, k)xnk.

If we replace n k by m, we obtain the following expression:

[parenleftbig]H(x)[parenrightbig]k = [summationdisplay]

m

knH x(n k, n)xn,

where H x(n, k) is the composita of the generating function xH(x). Therefore,

A(x) = [summationdisplay]

n

[parenleftbig]H(x)[parenrightbig]k = [summationdisplay]

nk

H x(m + k, k)xm.

Substituting n for k and n k for m, we get

[bracketleftbig]xnk[bracketrightbig]H(x)n = H x(n k, n).

Therefore, we get

A (n, k) = knH x(n k, n).

According to the above theorem, for solutions of the functional equation A(x) = xH(A(x)), we can use the following expression:

[bracketleftbig]A(x)[bracketrightbig]k = [summationdisplay]

nk

A (n, k)xn = [summationdisplay]

nk

nH x(n , n)xn. ()

Since the composita is uniquely determined by the generating function, formula () provides a solution of the inverse equation A(x) = xH(A(x)), when A(x) is known and H(x) is unknown. Hence,

H x(n, k) = k

k nA (k, k n).

It should be noted that for n = k,

H x(n, n) = A (n, n).

Next we give some examples of functional equations.

Example Let us nd an expression for coecients of the generating function A(x) = [summationtext]n> a(n)xn, which is dened by the functional equation

A(x) = x + xA(x) + xA(x) + xA(x).

The generating function xH(x) has the form

xH(x) = x + x + x + x.

Kruchinin Advances in Dierence Equations (2015) 2015:17 Page 4 of 7

The composita of xH(x) is

H x(n, k) =

k

[summationdisplay]

j=

[parenleftbigg]k j

nk+j [summationdisplay]

i=j

n(kj)i

[parenleftbigg] ji j

[parenrightbigg][parenleftbigg] k jn (k j) i

According to formula (), the coecients of A(x) are

a(n) =

nH x(n , n).

Therefore, we get

a(n) =

n

n

[summationdisplay]

j=

[parenleftbigg]n j

n+j [summationdisplay]

i=j

[parenleftbigg] ji j

n+ji

[parenleftbigg] n jn + j i

Example Let us nd an expression for coecients of the generating function B(x) = [summationtext]n a(n)xn, which is dened by the functional equation (see A [])

B(x) = x

x x x( + x) .

Next we introduce the following generating function A(x) = xB(x). Considering the functional equation, we can notice that

A(x) = x + A(x) + A(x)

A(x) .

Then we get the following functional equation:

A(x) = xH[parenleftbig]A(x)[parenrightbig],

where H(x) = +x+xx .

Now we obtain the composita of xH(x). The composita of F(x) = x + x + x is

F (n, k) =

k

[summationdisplay]

j=

[parenleftbigg] jn k j

[parenrightbigg][parenleftbigg]k j

[parenrightbigg]

.

The expression of coecients of the generating function [R(x)]k = ( x)k is equal to

[parenleftbigg]n + k k

[parenrightbigg]

.

Then we obtain the composita of xH(x),

H x(n, k) =

nk

[summationdisplay]

i=

[parenleftbigg]k + i k

[parenrightbigg] k

[summationdisplay]

j=

[parenleftbigg] jn k j i

[parenrightbigg][parenleftbigg]k j

[parenrightbigg]

.

Kruchinin Advances in Dierence Equations (2015) 2015:17 Page 5 of 7

Hence, using Theorem , we get the composita of A(x),

A (n, k) = knH x(n k, n) =

k n

nk

[summationdisplay]

i=

[parenleftbigg]n + i n

[parenrightbigg] n

[summationdisplay]

j=

[parenleftbigg] jn k j i

[parenrightbigg][parenleftbigg]n j

[parenrightbigg]

.

The coecients of B(x) are

b(n) = A (n + , ).

Therefore, we obtain

b(n) =

n +

n

[summationdisplay]

i=

[parenleftbigg]n + i n

[parenrightbigg] n+

[summationdisplay]

j=

[parenleftbigg] jn j i

[parenrightbigg][parenleftbigg]n + j

[parenrightbigg]

.

3 The generalized Lagrange inversion equation

Next we generalize the case A(x) = xH(A(x)).

Replacing A(x) by xB(x) in the functional equation (), we get

B(x) = H[parenleftbig]xB(x)[parenrightbig]. ()

Let us introduce the following denitions.

Denition The left composita of the generating function B(x) in the functional equation () is the composita

H x(n, k) = k

k nB x(k, k n),

where H x(n, k) is the composita of the generating function xB(x).

Denition The right composita of the generating function H(x) in the functional equation () is the composita

B x(n, k) = k

nH x(n k, n),

where H x(n, k) is the composita of the generating function xH(x).

There exists the left composita for every left composita and there exists the right composita for every right composita.

Formula () can be generalized for the case when a generating function is the solution of a certain functional equation. Let us prove the following theorem.

Theorem Suppose H(x) = [summationtext]n h(n)xn and B(x) = [summationtext]n b(n)xn are generating functions

such that B(x) = H(xB(x)m), where m

N; H x(n, k) and B x(n, k) are the compositae of the generating functions xH(x) and xB(x), respectively. Then

B x(n, k) = k

im H x(im, im), ()

where im = (m + )n mk.

Kruchinin Advances in Dierence Equations (2015) 2015:17 Page 6 of 7

Proof For m = , we have

B(x) = H[parenleftbig]xB(x)[parenrightbig] = G(x), im = k, im = n.

Then we obtain the identity

B x(n, k) = kk H x(n, k).

For m = , we have

B(x) = G[parenleftbig]xB(x)[parenrightbig], im = n, im = n k.

Then we obtain

B x,(n, k) = k

nH x(n k, n)

that satisfy Theorem .

By induction, we put that for m the solution of the equation

Bm(x) = H[parenleftbig]xBm(x)m[parenrightbig] ()

is

B x,m(n, k) = k

im H x(im, im).

Then we nd the solution for m + ,

Bm+(x) = H[parenleftbig]xBm+(x)m+[parenrightbig].

For this purpose, we consider the following functional equation:

Bm+(x) = Bm[parenleftbig]xBm+(x)[parenrightbig].

Instead of Bm(x), we substitute the right hand-side of ()

Bm+(x) = H[parenleftbig]xBm+(x)[bracketleftbig]Bm[parenleftbig]xBm+(x)[parenrightbig][bracketrightbig]m[parenrightbig];

from whence it follows that

Bm+(x) = H[parenleftbig]xBm+(x)m+[parenrightbig].

We note that B x,m+(n, k) is the right composita of Bm(x),

B x,m+(n, k) = k

nB x,m(n k, n),

where B x,m(n, k) is the composita of the generating function xBm(x).

Kruchinin Advances in Dierence Equations (2015) 2015:17 Page 7 of 7

Table 1 Table of functional equations

Equation Function B(x) Composita B[Delta1]x(n, k) OEIS

B(x) = 1 + xB0(x) 1 + x [parenleftbig] k

nk

B(x) = 1 + xB1(x) 1

1x

n1 k1

[parenrightbig] [parenrightbig] A000012

B(x) = 1 + xB2(x) 114x

2x

[parenrightbig] A000108 B(x) = 1 + xB3(x) k

n

3n2k nk

k n

2nk1 n1

[parenrightbig] A001764

Then

B x,m+(n, k) = k

(m + )n mk H x

[parenleftbig](m + )n (m + )k, (m + )n mk[parenrightbig].

Therefore, for the functional equation

Bm+(x) = Bm[parenleftbig]xBm+(x)[parenrightbig],

we obtain the required condition

B x,m+(n, k) = k

im H x(im+, im),

where im = (m + )n mk.

In Table we present a sequence of functional equations for the generating function H(x) = + x, where OEIS means the On-Line Encyclopedia of Integer Sequences [].

Competing interests

The author declares that they have no competing interests.

Acknowledgements

The author wishes to thank the referees for their useful comments. This work was partially supported by the Ministry of Education and Science of Russia, government order No. 1220 Theoretical bases of designing informational-safe systems.

Received: 30 October 2014 Accepted: 25 December 2014

References

1. Kruchinin, VV, Kruchinin, DV: Composita and its properties. J. Anal. Number Theory 2(2), 1-8 (2014)2. Kruchinin, DV, Kruchinin, VV: A method for obtaining generating function for central coecients of triangles.J. Integer Seq. 15, 1-10 (2012)3. Kruchinin, DV, Kruchinin, VV: Application of a composition of generating functions for obtaining explicit formulas of polynomials. J. Math. Anal. Appl. 404, 161-171 (2013)

4. Stanley, RP: Enumerative Combinatorics, vol. 2. Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge (1999)

5. Sloane, JA: The On-Line Encyclopedia of Integer Sequences. www.oeis.org