let n be Nat; :: thesis: for k being Nat st k < n holds
k ! <= (n |^ k) / (n choose k)
defpred S1[ Nat] means ( $1 < n implies $1 ! <= (n |^ $1) / (n choose $1) );
( n |^ 0 = 1 & n choose 0 = 1 ) by NEWTON:4, NEWTON:19;
then A1: S1[ 0 ] by NEWTON:12;
A2: for k being Nat st S1[k] holds
S1[k + 1]
proof
let k be Nat; :: thesis: ( S1[k] implies S1[k + 1] )
assume A3: S1[k] ; :: thesis: S1[k + 1]
set k1 = k + 1;
assume A4: k + 1 < n ; :: thesis: (k + 1) ! <= (n |^ (k + 1)) / (n choose (k + 1))
then A5: k < n by NAT_1:13;
A6: (n |^ (k + 1)) / (n choose (k + 1)) = (n |^ (k + 1)) / (((n - k) / (k + 1)) * (n choose k)) by IRRAT_1:5
.= ((n |^ (k + 1)) / (n choose k)) / ((n - k) / (k + 1)) by XCMPLX_1:78
.= ((n |^ (k + 1)) / (n choose k)) * ((k + 1) / (n - k)) by XCMPLX_1:79
.= ((n * (n |^ k)) / (n choose k)) * ((k + 1) / (n - k)) by NEWTON:6
.= (((n |^ k) / (n choose k)) * n) * ((k + 1) / (n - k)) by XCMPLX_1:74
.= ((n |^ k) / (n choose k)) * (n * ((k + 1) / (n - k))) ;
A7: n >= n - k by XREAL_1:43;
n - k > 0 by A5, XREAL_1:50;
then n / (n - k) >= 1 by A7, XREAL_1:181;
then A8: (k + 1) * (n / (n - k)) >= (k + 1) * 1 by XREAL_1:64;
(k + 1) * (n / (n - k)) = (n * (k + 1)) / (n - k) by XCMPLX_1:74
.= n * ((k + 1) / (n - k)) by XCMPLX_1:74 ;
then ((n |^ k) / (n choose k)) * (n * ((k + 1) / (n - k))) >= (k !) * (k + 1) by A4, NAT_1:13, A3, A8, XREAL_1:66;
hence (k + 1) ! <= (n |^ (k + 1)) / (n choose (k + 1)) by A6, NEWTON:15; :: thesis: verum
end;
for k being Nat holds S1[k] from NAT_1:sch 2(A1, A2);
 hence for k being Nat st k < n holds
k ! <= (n |^ k) / (n choose k) ; :: thesis: verum