contestada

Let Sn be the number of lattice paths in the Cartesian plane that start at (0,0), end at (n,n), contain no points above the line y = x, and are composed only of steps (0, 1), (1,0), and (1, 1), i.e. 1, +, and /. So = 1. Consider the generating function S(x):=∑_(n=0)^[infinity]▒〖SnX^n〗. Prove that 1 + (x – 1)S(x) + xS(x)2 = 0.

Respuesta :

A formal power series that encodes the coefficients of a sequence of numbers is a generating function.

Here, the coefficients of the sequence {Sₙ} are encoded by the generating function S(x). where Sₙ is the number of lattice paths as described above.

Here we will use the fact that the generating function for a sequence satisfies a functional equation that relates the generating function to the sequence itself to prove that 1 + (x – 1)S(x) + xS(x)² = 0,

Here, the functional equation is

S(x) = 1 + xS(x) + xS(x)²

This equation implies that

The term 1 on the right-hand side corresponds to the fact that to reach the point (0,0) (the starting point), there is exactly one way which is to stay at the starting point.

The term xS(x) corresponds to the fact that by taking a step in the positive x-direction and then following a path to (n-1, n-1) we can reach any point (n,n)

The term xS(x)² corresponds to the fact that by taking a step in the positive x-direction and then following a path to (n-2, n-2), and then taking another step in the positive x-direction and following a path to (n-1, n-1) we can reach any point (n,n)

Thus, 1 + (x – 1)S(x) + xS(x)² = 0. Hence proved.

To learn more about Generating functions visit

https://brainly.com/question/13092641

#SPJ4

Otras preguntas