Catalan-Zahl und Binomialkoeffizenten. Zeigen sie die angegbene Identität.

Question

Sei n eine natürliche Zahl. Die n-te Catalan-Zahl ist definiert als.

Answer 1

Falls die Rekursionsformel

( n über k ) = (n-k+1) / k * ( n über k-1) bekannt ist,

siehe https://de.wikipedia.org/wiki/Binomialkoeffizient#Eigenschaften

ist es einfach:

(2n über n ) - ( 2n über n+1 )

= (2n über n ) - ( 2n-(n+1)+1) / (n+1) * ( 2n über n )

 = (2n über n ) * ( 1  - ( 2n-(n+1)+1) / (n+1)    )

 = (2n über n ) * ( 1  - ( n / (n+1)    )

= (2n über n ) * ( 1  / (n+1)    )

= C_n          q.e.d.