How to solve the recurrence relation a <mrow class="MJX-TeXAtom-ORD"> n <

Gael Gardner

Gael Gardner

Answered question

2022-05-19

How to solve the recurrence relation a n = i = 1 n 1 a i a n i
The relation is: a n = i = 1 n 1 a i a n i n > 1 , a 1 = 2
I know I probably should create a generating function for a n , like G ( x ) = f ( x ) g ( x ), but I'm not sure what f(x) and g(x) exactly should be, are they just a i x i and a n i x n i ? And are there any other methods to solve it? Any hint would be useful to me.

Answer & Explanation

szilincsifs

szilincsifs

Beginner2022-05-20Added 15 answers

Step 1
We can use generating functions to solve this recurrence relation. We set according to the stated recurrence relation (1) A ( x ) = n = 1 a n x n = 2 x + n = 2 ( i = 0 n 1 a i a n i ) x n
Note we start the generating function with 2x since the recurrence relation has initial condition a 1 = 2.
Since ( A ( x ) ) 2 = ( k = 1 a k x k ) ( l = 1 a l x l ) = n = 2 ( k + l = n k , l 1 a k a l ) x n (2) = n = 2 ( k = 1 n 1 a k a n k ) x n we obtain from (1) and (2) the functional equation ( A ( x ) ) 2 = A ( x ) 2 x
Solving this quadratic equation we find (3) A ( x ) = 1 2 ( 1 ± 1 8 x ) where we take the minus sign, since this provides a generating function with constant term zero.
Step 2
Note: Evaluating the first few terms a n gives
A ( x ) = 1 2 ( 1 1 8 x ) = 2 x + 4 x 2 + 16 x 3 + 80 x 4 + 448 x 5 +
We find the sequence ( a n ) n 1 stored as A025225 in OEIS. There's also an explicit expression given for a n :
a n = 2 n n ( 2 n 2 n 1 ) n = 1 , 2 , which can be easily derived from (3) and we find a strong connection with the ubiquituous Catalan numbers.

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Discrete math

Ask your question.
Get an expert answer.

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

Didn't find what you were looking for?