Generating function of f ( n ) = C n − ∑ k = 1...

Lucian Maddox

Lucian Maddox

Answered

2022-07-13

Generating function of f ( n ) = C n k = 1 n 1 ( n k ) f ( n k ).

Answer & Explanation

billyfcash5n

billyfcash5n

Expert

2022-07-14Added 17 answers

Step 1
There are multiple types of generating functions (ordinary, exponential etc.). Your question is non-specific, so we'll go for the exponential generating function since the second part of the recurrence function looks like a binomial convolution.
So let's compute
G ( z ) = n 0 f ( n ) n ! z n
Step 2
Then we have
G ( z ) = ( n 0 C n n ! z n ) n 0 1 n ! ( k = 1 n 1 ( n k ) f ( n k ) ) z n = e 2 z ( I 0 ( 2 z ) I 1 ( 2 z ) ) n 0 ( f ( 0 ) n ! f ( n ) n ! + k = 0 n f ( n k ) k ! ( n k ) ! ) z n (1) = e 2 z ( I 0 ( 2 z ) I 1 ( 2 z ) ) + f ( 0 ) e z + G ( z ) e z G ( z ) (2)
where (1) uses the generating function for Catalan numbers, and in (2) we use the formula for the product of two series (Cauchy product). Here I 0 and I 1 represent the modified Bessel functions of the first kind.
Step 3
Using f ( 0 ) = C 0 = 1, we obtain from (3):
G ( z ) = 1 + e z ( I 0 ( 2 z ) I 1 ( 2 z ) )
If you were after the ordinary generating function
F ( z ) = n 0 f ( n ) z n
you can obtain it, if it converges, from the exponential one here, including F ( z ) = 0 + G ( z t ) e t d t

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get your answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?