:: Catalan Numbers
:: by Dorota Cz\c{e}stochowska and Adam Grabowski
::
:: Received May 31, 2004
:: Copyright (c) 2004-2019 Association of Mizar Users
:: (Stowarzyszenie Uzytkownikow Mizara, Bialystok, Poland).
:: This code can be distributed under the GNU General Public Licence
:: version 3.0 or later, or the Creative Commons Attribution-ShareAlike
:: License version 3.0 or later, subject to the binding interpretation
:: detailed in file COPYING.interpretation.
:: See COPYING.GPL and COPYING.CC-BY-SA for the full text of these
:: licenses, or see http://www.gnu.org/licenses/gpl.html and
:: http://creativecommons.org/licenses/by-sa/3.0/.
environ
vocabularies NUMBERS, ORDINAL1, XXREAL_0, ARYTM_1, RELAT_1, ARYTM_3, CARD_1,
NAT_1, ZFMISC_1, REALSET1, REAL_1, SUBSET_1, INT_1, CATALAN1, XCMPLX_0;
notations XBOOLE_0, SUBSET_1, ORDINAL1, NUMBERS, XCMPLX_0, XXREAL_0, XREAL_0,
REAL_1, NAT_1, NEWTON, INT_1, NAT_D, ZFMISC_1;
constructors XXREAL_0, REAL_1, NAT_1, NEWTON, ZFMISC_1, NAT_D, VALUED_1;
registrations XXREAL_0, XREAL_0, NAT_1, INT_1, NAT_2, ORDINAL1;
requirements REAL, NUMERALS, BOOLE, SUBSET, ARITHM;
begin :: Preliminaries
theorem :: CATALAN1:1
for n being Nat st n > 1 holds n -' 1 <= 2 * n -' 3;
theorem :: CATALAN1:2
for n being Nat st n >= 1 holds n -' 1 <= 2 * n -' 2;
theorem :: CATALAN1:3
for n being Nat st n > 1 holds n < 2 * n -' 1;
theorem :: CATALAN1:4
for n being Nat st n > 1 holds n -' 2 + 1 = n -' 1;
theorem :: CATALAN1:5
for n being Nat st n > 1 holds (4 * n * n - 2*n) / (n + 1) > 1;
theorem :: CATALAN1:6
for n being Nat st n > 1 holds (2 * n -' 2)! * n * (n
+ 1) < (2 * n)!;
theorem :: CATALAN1:7
for n being Nat holds 2 * (2 - (3 / (n + 1))) < 4;
begin :: Catalan Numbers
definition
let n be Nat;
func Catalan (n) -> Real equals
:: CATALAN1:def 1
((2*n -' 2) choose (n -' 1)) / n;
end;
theorem :: CATALAN1:8
for n being Nat st n > 1 holds Catalan (n) = (2 * n -'
2)! / ((n -' 1)! * (n!));
theorem :: CATALAN1:9
for n being Nat st n > 1 holds Catalan n = 4 * ((2*n
-' 3) choose (n -' 1)) - ((2*n -' 1) choose (n -' 1));
theorem :: CATALAN1:10
Catalan 0 = 0;
theorem :: CATALAN1:11
Catalan 1 = 1;
theorem :: CATALAN1:12
Catalan 2 = 1;
theorem :: CATALAN1:13
for n being Nat holds Catalan (n) is Integer;
theorem :: CATALAN1:14
for k being Nat holds Catalan (k + 1) = (2*k)! / (k! * ((k+1)!));
theorem :: CATALAN1:15
for n being Nat st n > 1 holds Catalan (n) < Catalan (n + 1);
theorem :: CATALAN1:16
for n being Nat holds Catalan (n) <= Catalan (n + 1);
theorem :: CATALAN1:17
for n being Nat holds Catalan (n) >= 0;
theorem :: CATALAN1:18
for n being Nat holds Catalan (n) is Element of NAT;
theorem :: CATALAN1:19
for n being Nat st n > 0 holds Catalan (n+1) = 2 * (2
- (3 / (n + 1))) * Catalan (n);
registration
let n be Nat;
cluster Catalan n -> natural;
end;
theorem :: CATALAN1:20
for n being Nat st n > 0 holds Catalan n > 0;
registration
let n be non zero Nat;
cluster Catalan n -> non zero;
end;
theorem :: CATALAN1:21
for n being Nat st n > 0 holds Catalan (n+1) < 4 * Catalan (n);