MPE Home Metamath Proof Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >  birthdaylem3 Structured version   Unicode version

Theorem birthdaylem3 23865
Description: For general  N and  K, upper-bound the fraction of injective functions from  1 ... K to  1 ... N. (Contributed by Mario Carneiro, 17-Apr-2015.)
Hypotheses
Ref Expression
birthday.s  |-  S  =  { f  |  f : ( 1 ... K ) --> ( 1 ... N ) }
birthday.t  |-  T  =  { f  |  f : ( 1 ... K ) -1-1-> ( 1 ... N ) }
Assertion
Ref Expression
birthdaylem3  |-  ( ( K  e.  NN0  /\  N  e.  NN )  ->  ( ( # `  T
)  /  ( # `  S ) )  <_ 
( exp `  -u (
( ( ( K ^ 2 )  -  K )  /  2
)  /  N ) ) )
Distinct variable groups:    f, K    f, N
Allowed substitution hints:    S( f)    T( f)

Proof of Theorem birthdaylem3
Dummy variable  k is distinct from all other variables.
StepHypRef Expression
1 birthday.t . . . . . . . 8  |-  T  =  { f  |  f : ( 1 ... K ) -1-1-> ( 1 ... N ) }
2 abn0 3781 . . . . . . . . . . . 12  |-  ( { f  |  f : ( 1 ... K
) -1-1-> ( 1 ... N ) }  =/=  (/)  <->  E. f  f : ( 1 ... K )
-1-1-> ( 1 ... N
) )
3 ovex 6329 . . . . . . . . . . . . 13  |-  ( 1 ... N )  e. 
_V
43brdom 7585 . . . . . . . . . . . 12  |-  ( ( 1 ... K )  ~<_  ( 1 ... N
)  <->  E. f  f : ( 1 ... K
) -1-1-> ( 1 ... N ) )
52, 4bitr4i 255 . . . . . . . . . . 11  |-  ( { f  |  f : ( 1 ... K
) -1-1-> ( 1 ... N ) }  =/=  (/)  <->  ( 1 ... K )  ~<_  ( 1 ... N
) )
6 hashfz1 12528 . . . . . . . . . . . . 13  |-  ( K  e.  NN0  ->  ( # `  ( 1 ... K
) )  =  K )
7 nnnn0 10876 . . . . . . . . . . . . . 14  |-  ( N  e.  NN  ->  N  e.  NN0 )
8 hashfz1 12528 . . . . . . . . . . . . . 14  |-  ( N  e.  NN0  ->  ( # `  ( 1 ... N
) )  =  N )
97, 8syl 17 . . . . . . . . . . . . 13  |-  ( N  e.  NN  ->  ( # `
 ( 1 ... N ) )  =  N )
106, 9breqan12d 4436 . . . . . . . . . . . 12  |-  ( ( K  e.  NN0  /\  N  e.  NN )  ->  ( ( # `  (
1 ... K ) )  <_  ( # `  (
1 ... N ) )  <-> 
K  <_  N )
)
11 fzfid 12185 . . . . . . . . . . . . 13  |-  ( ( K  e.  NN0  /\  N  e.  NN )  ->  ( 1 ... K
)  e.  Fin )
12 fzfid 12185 . . . . . . . . . . . . 13  |-  ( ( K  e.  NN0  /\  N  e.  NN )  ->  ( 1 ... N
)  e.  Fin )
13 hashdom 12557 . . . . . . . . . . . . 13  |-  ( ( ( 1 ... K
)  e.  Fin  /\  ( 1 ... N
)  e.  Fin )  ->  ( ( # `  (
1 ... K ) )  <_  ( # `  (
1 ... N ) )  <-> 
( 1 ... K
)  ~<_  ( 1 ... N ) ) )
1411, 12, 13syl2anc 665 . . . . . . . . . . . 12  |-  ( ( K  e.  NN0  /\  N  e.  NN )  ->  ( ( # `  (
1 ... K ) )  <_  ( # `  (
1 ... N ) )  <-> 
( 1 ... K
)  ~<_  ( 1 ... N ) ) )
15 nn0re 10878 . . . . . . . . . . . . 13  |-  ( K  e.  NN0  ->  K  e.  RR )
16 nnre 10616 . . . . . . . . . . . . 13  |-  ( N  e.  NN  ->  N  e.  RR )
17 lenlt 9712 . . . . . . . . . . . . 13  |-  ( ( K  e.  RR  /\  N  e.  RR )  ->  ( K  <_  N  <->  -.  N  <  K ) )
1815, 16, 17syl2an 479 . . . . . . . . . . . 12  |-  ( ( K  e.  NN0  /\  N  e.  NN )  ->  ( K  <_  N  <->  -.  N  <  K ) )
1910, 14, 183bitr3d 286 . . . . . . . . . . 11  |-  ( ( K  e.  NN0  /\  N  e.  NN )  ->  ( ( 1 ... K )  ~<_  ( 1 ... N )  <->  -.  N  <  K ) )
205, 19syl5bb 260 . . . . . . . . . 10  |-  ( ( K  e.  NN0  /\  N  e.  NN )  ->  ( { f  |  f : ( 1 ... K ) -1-1-> ( 1 ... N ) }  =/=  (/)  <->  -.  N  <  K ) )
2120necon4abid 2675 . . . . . . . . 9  |-  ( ( K  e.  NN0  /\  N  e.  NN )  ->  ( { f  |  f : ( 1 ... K ) -1-1-> ( 1 ... N ) }  =  (/)  <->  N  <  K ) )
2221biimpar 487 . . . . . . . 8  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  N  <  K
)  ->  { f  |  f : ( 1 ... K )
-1-1-> ( 1 ... N
) }  =  (/) )
231, 22syl5eq 2475 . . . . . . 7  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  N  <  K
)  ->  T  =  (/) )
2423fveq2d 5881 . . . . . 6  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  N  <  K
)  ->  ( # `  T
)  =  ( # `  (/) ) )
25 hash0 12547 . . . . . 6  |-  ( # `  (/) )  =  0
2624, 25syl6eq 2479 . . . . 5  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  N  <  K
)  ->  ( # `  T
)  =  0 )
2726oveq1d 6316 . . . 4  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  N  <  K
)  ->  ( ( # `
 T )  / 
( # `  S ) )  =  ( 0  /  ( # `  S
) ) )
28 birthday.s . . . . . . . . . 10  |-  S  =  { f  |  f : ( 1 ... K ) --> ( 1 ... N ) }
2928, 1birthdaylem1 23863 . . . . . . . . 9  |-  ( T 
C_  S  /\  S  e.  Fin  /\  ( N  e.  NN  ->  S  =/=  (/) ) )
3029simp3i 1016 . . . . . . . 8  |-  ( N  e.  NN  ->  S  =/=  (/) )
3130ad2antlr 731 . . . . . . 7  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  N  <  K
)  ->  S  =/=  (/) )
3229simp2i 1015 . . . . . . . 8  |-  S  e. 
Fin
33 hashnncl 12546 . . . . . . . 8  |-  ( S  e.  Fin  ->  (
( # `  S )  e.  NN  <->  S  =/=  (/) ) )
3432, 33ax-mp 5 . . . . . . 7  |-  ( (
# `  S )  e.  NN  <->  S  =/=  (/) )
3531, 34sylibr 215 . . . . . 6  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  N  <  K
)  ->  ( # `  S
)  e.  NN )
3635nncnd 10625 . . . . 5  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  N  <  K
)  ->  ( # `  S
)  e.  CC )
3735nnne0d 10654 . . . . 5  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  N  <  K
)  ->  ( # `  S
)  =/=  0 )
3836, 37div0d 10382 . . . 4  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  N  <  K
)  ->  ( 0  /  ( # `  S
) )  =  0 )
3927, 38eqtrd 2463 . . 3  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  N  <  K
)  ->  ( ( # `
 T )  / 
( # `  S ) )  =  0 )
4015adantr 466 . . . . . . . . . . 11  |-  ( ( K  e.  NN0  /\  N  e.  NN )  ->  K  e.  RR )
4140resqcld 12441 . . . . . . . . . 10  |-  ( ( K  e.  NN0  /\  N  e.  NN )  ->  ( K ^ 2 )  e.  RR )
4241, 40resubcld 10047 . . . . . . . . 9  |-  ( ( K  e.  NN0  /\  N  e.  NN )  ->  ( ( K ^
2 )  -  K
)  e.  RR )
4342rehalfcld 10859 . . . . . . . 8  |-  ( ( K  e.  NN0  /\  N  e.  NN )  ->  ( ( ( K ^ 2 )  -  K )  /  2
)  e.  RR )
44 nndivre 10645 . . . . . . . 8  |-  ( ( ( ( ( K ^ 2 )  -  K )  /  2
)  e.  RR  /\  N  e.  NN )  ->  ( ( ( ( K ^ 2 )  -  K )  / 
2 )  /  N
)  e.  RR )
4543, 44sylancom 671 . . . . . . 7  |-  ( ( K  e.  NN0  /\  N  e.  NN )  ->  ( ( ( ( K ^ 2 )  -  K )  / 
2 )  /  N
)  e.  RR )
4645renegcld 10046 . . . . . 6  |-  ( ( K  e.  NN0  /\  N  e.  NN )  -> 
-u ( ( ( ( K ^ 2 )  -  K )  /  2 )  /  N )  e.  RR )
4746adantr 466 . . . . 5  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  N  <  K
)  ->  -u ( ( ( ( K ^
2 )  -  K
)  /  2 )  /  N )  e.  RR )
4847rpefcld 14146 . . . 4  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  N  <  K
)  ->  ( exp `  -u ( ( ( ( K ^ 2 )  -  K )  / 
2 )  /  N
) )  e.  RR+ )
4948rpge0d 11345 . . 3  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  N  <  K
)  ->  0  <_  ( exp `  -u (
( ( ( K ^ 2 )  -  K )  /  2
)  /  N ) ) )
5039, 49eqbrtrd 4441 . 2  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  N  <  K
)  ->  ( ( # `
 T )  / 
( # `  S ) )  <_  ( exp `  -u ( ( ( ( K ^ 2 )  -  K )  / 
2 )  /  N
) ) )
51 simplr 760 . . . 4  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  K  <_  N
)  ->  N  e.  NN )
52 simpr 462 . . . . 5  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  K  <_  N
)  ->  K  <_  N )
53 simpll 758 . . . . . . 7  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  K  <_  N
)  ->  K  e.  NN0 )
54 nn0uz 11193 . . . . . . 7  |-  NN0  =  ( ZZ>= `  0 )
5553, 54syl6eleq 2520 . . . . . 6  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  K  <_  N
)  ->  K  e.  ( ZZ>= `  0 )
)
56 nnz 10959 . . . . . . 7  |-  ( N  e.  NN  ->  N  e.  ZZ )
5756ad2antlr 731 . . . . . 6  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  K  <_  N
)  ->  N  e.  ZZ )
58 elfz5 11792 . . . . . 6  |-  ( ( K  e.  ( ZZ>= ` 
0 )  /\  N  e.  ZZ )  ->  ( K  e.  ( 0 ... N )  <->  K  <_  N ) )
5955, 57, 58syl2anc 665 . . . . 5  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  K  <_  N
)  ->  ( K  e.  ( 0 ... N
)  <->  K  <_  N ) )
6052, 59mpbird 235 . . . 4  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  K  <_  N
)  ->  K  e.  ( 0 ... N
) )
6128, 1birthdaylem2 23864 . . . 4  |-  ( ( N  e.  NN  /\  K  e.  ( 0 ... N ) )  ->  ( ( # `  T )  /  ( # `
 S ) )  =  ( exp `  sum_ k  e.  ( 0 ... ( K  - 
1 ) ) ( log `  ( 1  -  ( k  /  N ) ) ) ) )
6251, 60, 61syl2anc 665 . . 3  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  K  <_  N
)  ->  ( ( # `
 T )  / 
( # `  S ) )  =  ( exp `  sum_ k  e.  ( 0 ... ( K  -  1 ) ) ( log `  (
1  -  ( k  /  N ) ) ) ) )
63 fzfid 12185 . . . . . 6  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  K  <_  N
)  ->  ( 0 ... ( K  - 
1 ) )  e. 
Fin )
64 elfznn0 11887 . . . . . . . . . . . . 13  |-  ( k  e.  ( 0 ... ( K  -  1 ) )  ->  k  e.  NN0 )
6564adantl 467 . . . . . . . . . . . 12  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  k  e.  NN0 )
6665nn0red 10926 . . . . . . . . . . 11  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  k  e.  RR )
6753nn0red 10926 . . . . . . . . . . . . 13  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  K  <_  N
)  ->  K  e.  RR )
68 peano2rem 9941 . . . . . . . . . . . . 13  |-  ( K  e.  RR  ->  ( K  -  1 )  e.  RR )
6967, 68syl 17 . . . . . . . . . . . 12  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  K  <_  N
)  ->  ( K  -  1 )  e.  RR )
7069adantr 466 . . . . . . . . . . 11  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  ( K  -  1 )  e.  RR )
7151adantr 466 . . . . . . . . . . . 12  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  N  e.  NN )
7271nnred 10624 . . . . . . . . . . 11  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  N  e.  RR )
73 elfzle2 11803 . . . . . . . . . . . 12  |-  ( k  e.  ( 0 ... ( K  -  1 ) )  ->  k  <_  ( K  -  1 ) )
7473adantl 467 . . . . . . . . . . 11  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  k  <_  ( K  -  1 ) )
7551nnred 10624 . . . . . . . . . . . . 13  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  K  <_  N
)  ->  N  e.  RR )
7667ltm1d 10539 . . . . . . . . . . . . 13  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  K  <_  N
)  ->  ( K  -  1 )  < 
K )
7769, 67, 75, 76, 52ltletrd 9795 . . . . . . . . . . . 12  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  K  <_  N
)  ->  ( K  -  1 )  < 
N )
7877adantr 466 . . . . . . . . . . 11  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  ( K  -  1 )  <  N )
7966, 70, 72, 74, 78lelttrd 9793 . . . . . . . . . 10  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  k  <  N )
8071nncnd 10625 . . . . . . . . . . 11  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  N  e.  CC )
8180mulid1d 9660 . . . . . . . . . 10  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  ( N  x.  1 )  =  N )
8279, 81breqtrrd 4447 . . . . . . . . 9  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  k  <  ( N  x.  1 ) )
83 1red 9658 . . . . . . . . . 10  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  1  e.  RR )
8471nngt0d 10653 . . . . . . . . . 10  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  0  <  N )
85 ltdivmul 10480 . . . . . . . . . 10  |-  ( ( k  e.  RR  /\  1  e.  RR  /\  ( N  e.  RR  /\  0  <  N ) )  -> 
( ( k  /  N )  <  1  <->  k  <  ( N  x.  1 ) ) )
8666, 83, 72, 84, 85syl112anc 1268 . . . . . . . . 9  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  (
( k  /  N
)  <  1  <->  k  <  ( N  x.  1 ) ) )
8782, 86mpbird 235 . . . . . . . 8  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  (
k  /  N )  <  1 )
8866, 71nndivred 10658 . . . . . . . . 9  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  (
k  /  N )  e.  RR )
89 1re 9642 . . . . . . . . 9  |-  1  e.  RR
90 difrp 11337 . . . . . . . . 9  |-  ( ( ( k  /  N
)  e.  RR  /\  1  e.  RR )  ->  ( ( k  /  N )  <  1  <->  ( 1  -  ( k  /  N ) )  e.  RR+ ) )
9188, 89, 90sylancl 666 . . . . . . . 8  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  (
( k  /  N
)  <  1  <->  ( 1  -  ( k  /  N ) )  e.  RR+ ) )
9287, 91mpbid 213 . . . . . . 7  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  (
1  -  ( k  /  N ) )  e.  RR+ )
9392relogcld 23558 . . . . . 6  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  ( log `  ( 1  -  ( k  /  N
) ) )  e.  RR )
9488renegcld 10046 . . . . . 6  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  -u (
k  /  N )  e.  RR )
95 elfzle1 11802 . . . . . . . . . . . 12  |-  ( k  e.  ( 0 ... ( K  -  1 ) )  ->  0  <_  k )
9695adantl 467 . . . . . . . . . . 11  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  0  <_  k )
97 divge0 10474 . . . . . . . . . . 11  |-  ( ( ( k  e.  RR  /\  0  <_  k )  /\  ( N  e.  RR  /\  0  <  N ) )  ->  0  <_  ( k  /  N ) )
9866, 96, 72, 84, 97syl22anc 1265 . . . . . . . . . 10  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  0  <_  ( k  /  N
) )
9988, 98, 87eflegeo 14162 . . . . . . . . 9  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  ( exp `  ( k  /  N ) )  <_ 
( 1  /  (
1  -  ( k  /  N ) ) ) )
10088reefcld 14129 . . . . . . . . . 10  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  ( exp `  ( k  /  N ) )  e.  RR )
101 efgt0 14144 . . . . . . . . . . 11  |-  ( ( k  /  N )  e.  RR  ->  0  <  ( exp `  (
k  /  N ) ) )
10288, 101syl 17 . . . . . . . . . 10  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  0  <  ( exp `  (
k  /  N ) ) )
10392rpregt0d 11347 . . . . . . . . . 10  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  (
( 1  -  (
k  /  N ) )  e.  RR  /\  0  <  ( 1  -  ( k  /  N
) ) ) )
104 lerec2 10494 . . . . . . . . . 10  |-  ( ( ( ( exp `  (
k  /  N ) )  e.  RR  /\  0  <  ( exp `  (
k  /  N ) ) )  /\  (
( 1  -  (
k  /  N ) )  e.  RR  /\  0  <  ( 1  -  ( k  /  N
) ) ) )  ->  ( ( exp `  ( k  /  N
) )  <_  (
1  /  ( 1  -  ( k  /  N ) ) )  <-> 
( 1  -  (
k  /  N ) )  <_  ( 1  /  ( exp `  (
k  /  N ) ) ) ) )
105100, 102, 103, 104syl21anc 1263 . . . . . . . . 9  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  (
( exp `  (
k  /  N ) )  <_  ( 1  /  ( 1  -  ( k  /  N
) ) )  <->  ( 1  -  ( k  /  N ) )  <_ 
( 1  /  ( exp `  ( k  /  N ) ) ) ) )
10699, 105mpbid 213 . . . . . . . 8  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  (
1  -  ( k  /  N ) )  <_  ( 1  / 
( exp `  (
k  /  N ) ) ) )
10792reeflogd 23559 . . . . . . . 8  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  ( exp `  ( log `  (
1  -  ( k  /  N ) ) ) )  =  ( 1  -  ( k  /  N ) ) )
10888recnd 9669 . . . . . . . . 9  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  (
k  /  N )  e.  CC )
109 efneg 14139 . . . . . . . . 9  |-  ( ( k  /  N )  e.  CC  ->  ( exp `  -u ( k  /  N ) )  =  ( 1  /  ( exp `  ( k  /  N ) ) ) )
110108, 109syl 17 . . . . . . . 8  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  ( exp `  -u ( k  /  N ) )  =  ( 1  /  ( exp `  ( k  /  N ) ) ) )
111106, 107, 1103brtr4d 4451 . . . . . . 7  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  ( exp `  ( log `  (
1  -  ( k  /  N ) ) ) )  <_  ( exp `  -u ( k  /  N ) ) )
112 efle 14159 . . . . . . . 8  |-  ( ( ( log `  (
1  -  ( k  /  N ) ) )  e.  RR  /\  -u ( k  /  N
)  e.  RR )  ->  ( ( log `  ( 1  -  (
k  /  N ) ) )  <_  -u (
k  /  N )  <-> 
( exp `  ( log `  ( 1  -  ( k  /  N
) ) ) )  <_  ( exp `  -u (
k  /  N ) ) ) )
11393, 94, 112syl2anc 665 . . . . . . 7  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  (
( log `  (
1  -  ( k  /  N ) ) )  <_  -u ( k  /  N )  <->  ( exp `  ( log `  (
1  -  ( k  /  N ) ) ) )  <_  ( exp `  -u ( k  /  N ) ) ) )
114111, 113mpbird 235 . . . . . 6  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  ( log `  ( 1  -  ( k  /  N
) ) )  <_  -u ( k  /  N
) )
11563, 93, 94, 114fsumle 13846 . . . . 5  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  K  <_  N
)  ->  sum_ k  e.  ( 0 ... ( K  -  1 ) ) ( log `  (
1  -  ( k  /  N ) ) )  <_  sum_ k  e.  ( 0 ... ( K  -  1 ) ) -u ( k  /  N ) )
11663, 108fsumneg 13835 . . . . . 6  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  K  <_  N
)  ->  sum_ k  e.  ( 0 ... ( K  -  1 ) ) -u ( k  /  N )  = 
-u sum_ k  e.  ( 0 ... ( K  -  1 ) ) ( k  /  N
) )
11751nncnd 10625 . . . . . . . . 9  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  K  <_  N
)  ->  N  e.  CC )
11866recnd 9669 . . . . . . . . 9  |-  ( ( ( ( K  e. 
NN0  /\  N  e.  NN )  /\  K  <_  N )  /\  k  e.  ( 0 ... ( K  -  1 ) ) )  ->  k  e.  CC )
119 nnne0 10642 . . . . . . . . . 10  |-  ( N  e.  NN  ->  N  =/=  0 )
120119ad2antlr 731 . . . . . . . . 9  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  K  <_  N
)  ->  N  =/=  0 )
12163, 117, 118, 120fsumdivc 13834 . . . . . . . 8  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  K  <_  N
)  ->  ( sum_ k  e.  ( 0 ... ( K  - 
1 ) ) k  /  N )  = 
sum_ k  e.  ( 0 ... ( K  -  1 ) ) ( k  /  N
) )
122 arisum2 13906 . . . . . . . . . 10  |-  ( K  e.  NN0  ->  sum_ k  e.  ( 0 ... ( K  -  1 ) ) k  =  ( ( ( K ^
2 )  -  K
)  /  2 ) )
12353, 122syl 17 . . . . . . . . 9  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  K  <_  N
)  ->  sum_ k  e.  ( 0 ... ( K  -  1 ) ) k  =  ( ( ( K ^
2 )  -  K
)  /  2 ) )
124123oveq1d 6316 . . . . . . . 8  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  K  <_  N
)  ->  ( sum_ k  e.  ( 0 ... ( K  - 
1 ) ) k  /  N )  =  ( ( ( ( K ^ 2 )  -  K )  / 
2 )  /  N
) )
125121, 124eqtr3d 2465 . . . . . . 7  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  K  <_  N
)  ->  sum_ k  e.  ( 0 ... ( K  -  1 ) ) ( k  /  N )  =  ( ( ( ( K ^ 2 )  -  K )  /  2
)  /  N ) )
126125negeqd 9869 . . . . . 6  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  K  <_  N
)  ->  -u sum_ k  e.  ( 0 ... ( K  -  1 ) ) ( k  /  N )  =  -u ( ( ( ( K ^ 2 )  -  K )  / 
2 )  /  N
) )
127116, 126eqtrd 2463 . . . . 5  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  K  <_  N
)  ->  sum_ k  e.  ( 0 ... ( K  -  1 ) ) -u ( k  /  N )  = 
-u ( ( ( ( K ^ 2 )  -  K )  /  2 )  /  N ) )
128115, 127breqtrd 4445 . . . 4  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  K  <_  N
)  ->  sum_ k  e.  ( 0 ... ( K  -  1 ) ) ( log `  (
1  -  ( k  /  N ) ) )  <_  -u ( ( ( ( K ^
2 )  -  K
)  /  2 )  /  N ) )
12963, 93fsumrecl 13787 . . . . 5  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  K  <_  N
)  ->  sum_ k  e.  ( 0 ... ( K  -  1 ) ) ( log `  (
1  -  ( k  /  N ) ) )  e.  RR )
13046adantr 466 . . . . 5  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  K  <_  N
)  ->  -u ( ( ( ( K ^
2 )  -  K
)  /  2 )  /  N )  e.  RR )
131 efle 14159 . . . . 5  |-  ( (
sum_ k  e.  ( 0 ... ( K  -  1 ) ) ( log `  (
1  -  ( k  /  N ) ) )  e.  RR  /\  -u ( ( ( ( K ^ 2 )  -  K )  / 
2 )  /  N
)  e.  RR )  ->  ( sum_ k  e.  ( 0 ... ( K  -  1 ) ) ( log `  (
1  -  ( k  /  N ) ) )  <_  -u ( ( ( ( K ^
2 )  -  K
)  /  2 )  /  N )  <->  ( exp ` 
sum_ k  e.  ( 0 ... ( K  -  1 ) ) ( log `  (
1  -  ( k  /  N ) ) ) )  <_  ( exp `  -u ( ( ( ( K ^ 2 )  -  K )  /  2 )  /  N ) ) ) )
132129, 130, 131syl2anc 665 . . . 4  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  K  <_  N
)  ->  ( sum_ k  e.  ( 0 ... ( K  - 
1 ) ) ( log `  ( 1  -  ( k  /  N ) ) )  <_  -u ( ( ( ( K ^ 2 )  -  K )  /  2 )  /  N )  <->  ( exp ` 
sum_ k  e.  ( 0 ... ( K  -  1 ) ) ( log `  (
1  -  ( k  /  N ) ) ) )  <_  ( exp `  -u ( ( ( ( K ^ 2 )  -  K )  /  2 )  /  N ) ) ) )
133128, 132mpbid 213 . . 3  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  K  <_  N
)  ->  ( exp ` 
sum_ k  e.  ( 0 ... ( K  -  1 ) ) ( log `  (
1  -  ( k  /  N ) ) ) )  <_  ( exp `  -u ( ( ( ( K ^ 2 )  -  K )  /  2 )  /  N ) ) )
13462, 133eqbrtrd 4441 . 2  |-  ( ( ( K  e.  NN0  /\  N  e.  NN )  /\  K  <_  N
)  ->  ( ( # `
 T )  / 
( # `  S ) )  <_  ( exp `  -u ( ( ( ( K ^ 2 )  -  K )  / 
2 )  /  N
) ) )
13516adantl 467 . 2  |-  ( ( K  e.  NN0  /\  N  e.  NN )  ->  N  e.  RR )
13650, 134, 135, 40ltlecasei 9742 1  |-  ( ( K  e.  NN0  /\  N  e.  NN )  ->  ( ( # `  T
)  /  ( # `  S ) )  <_ 
( exp `  -u (
( ( ( K ^ 2 )  -  K )  /  2
)  /  N ) ) )
Colors of variables: wff setvar class
Syntax hints:   -. wn 3    -> wi 4    <-> wb 187    /\ wa 370    = wceq 1437   E.wex 1659    e. wcel 1868   {cab 2407    =/= wne 2618    C_ wss 3436   (/)c0 3761   class class class wbr 4420   -->wf 5593   -1-1->wf1 5594   ` cfv 5597  (class class class)co 6301    ~<_ cdom 7571   Fincfn 7573   CCcc 9537   RRcr 9538   0cc0 9539   1c1 9540    x. cmul 9544    < clt 9675    <_ cle 9676    - cmin 9860   -ucneg 9861    / cdiv 10269   NNcn 10609   2c2 10659   NN0cn0 10869   ZZcz 10937   ZZ>=cuz 11159   RR+crp 11302   ...cfz 11784   ^cexp 12271   #chash 12514   sum_csu 13739   expce 14101   logclog 23490
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1665  ax-4 1678  ax-5 1748  ax-6 1794  ax-7 1839  ax-8 1870  ax-9 1872  ax-10 1887  ax-11 1892  ax-12 1905  ax-13 2053  ax-ext 2400  ax-rep 4533  ax-sep 4543  ax-nul 4551  ax-pow 4598  ax-pr 4656  ax-un 6593  ax-inf2 8148  ax-cnex 9595  ax-resscn 9596  ax-1cn 9597  ax-icn 9598  ax-addcl 9599  ax-addrcl 9600  ax-mulcl 9601  ax-mulrcl 9602  ax-mulcom 9603  ax-addass 9604  ax-mulass 9605  ax-distr 9606  ax-i2m1 9607  ax-1ne0 9608  ax-1rid 9609  ax-rnegex 9610  ax-rrecex 9611  ax-cnre 9612  ax-pre-lttri 9613  ax-pre-lttrn 9614  ax-pre-ltadd 9615  ax-pre-mulgt0 9616  ax-pre-sup 9617  ax-addf 9618  ax-mulf 9619
This theorem depends on definitions:  df-bi 188  df-or 371  df-an 372  df-3or 983  df-3an 984  df-tru 1440  df-fal 1443  df-ex 1660  df-nf 1664  df-sb 1787  df-eu 2269  df-mo 2270  df-clab 2408  df-cleq 2414  df-clel 2417  df-nfc 2572  df-ne 2620  df-nel 2621  df-ral 2780  df-rex 2781  df-reu 2782  df-rmo 2783  df-rab 2784  df-v 3083  df-sbc 3300  df-csb 3396  df-dif 3439  df-un 3441  df-in 3443  df-ss 3450  df-pss 3452  df-nul 3762  df-if 3910  df-pw 3981  df-sn 3997  df-pr 3999  df-tp 4001  df-op 4003  df-uni 4217  df-int 4253  df-iun 4298  df-iin 4299  df-br 4421  df-opab 4480  df-mpt 4481  df-tr 4516  df-eprel 4760  df-id 4764  df-po 4770  df-so 4771  df-fr 4808  df-se 4809  df-we 4810  df-xp 4855  df-rel 4856  df-cnv 4857  df-co 4858  df-dm 4859  df-rn 4860  df-res 4861  df-ima 4862  df-pred 5395  df-ord 5441  df-on 5442  df-lim 5443  df-suc 5444  df-iota 5561  df-fun 5599  df-fn 5600  df-f 5601  df-f1 5602  df-fo 5603  df-f1o 5604  df-fv 5605  df-isom 5606  df-riota 6263  df-ov 6304  df-oprab 6305  df-mpt2 6306  df-of 6541  df-om 6703  df-1st 6803  df-2nd 6804  df-supp 6922  df-wrecs 7032  df-recs 7094  df-rdg 7132  df-1o 7186  df-2o 7187  df-oadd 7190  df-er 7367  df-map 7478  df-pm 7479  df-ixp 7527  df-en 7574  df-dom 7575  df-sdom 7576  df-fin 7577  df-fsupp 7886  df-fi 7927  df-sup 7958  df-inf 7959  df-oi 8027  df-card 8374  df-cda 8598  df-pnf 9677  df-mnf 9678  df-xr 9679  df-ltxr 9680  df-le 9681  df-sub 9862  df-neg 9863  df-div 10270  df-nn 10610  df-2 10668  df-3 10669  df-4 10670  df-5 10671  df-6 10672  df-7 10673  df-8 10674  df-9 10675  df-10 10676  df-n0 10870  df-z 10938  df-dec 11052  df-uz 11160  df-q 11265  df-rp 11303  df-xneg 11409  df-xadd 11410  df-xmul 11411  df-ioo 11639  df-ioc 11640  df-ico 11641  df-icc 11642  df-fz 11785  df-fzo 11916  df-fl 12027  df-mod 12096  df-seq 12213  df-exp 12272  df-fac 12459  df-bc 12487  df-hash 12515  df-shft 13118  df-cj 13150  df-re 13151  df-im 13152  df-sqrt 13286  df-abs 13287  df-limsup 13513  df-clim 13539  df-rlim 13540  df-sum 13740  df-ef 14108  df-sin 14110  df-cos 14111  df-pi 14113  df-struct 15110  df-ndx 15111  df-slot 15112  df-base 15113  df-sets 15114  df-ress 15115  df-plusg 15190  df-mulr 15191  df-starv 15192  df-sca 15193  df-vsca 15194  df-ip 15195  df-tset 15196  df-ple 15197  df-ds 15199  df-unif 15200  df-hom 15201  df-cco 15202  df-rest 15308  df-topn 15309  df-0g 15327  df-gsum 15328  df-topgen 15329  df-pt 15330  df-prds 15333  df-xrs 15387  df-qtop 15393  df-imas 15394  df-xps 15397  df-mre 15479  df-mrc 15480  df-acs 15482  df-mgm 16475  df-sgrp 16514  df-mnd 16524  df-submnd 16570  df-mulg 16663  df-cntz 16958  df-cmn 17419  df-psmet 18949  df-xmet 18950  df-met 18951  df-bl 18952  df-mopn 18953  df-fbas 18954  df-fg 18955  df-cnfld 18958  df-top 19907  df-bases 19908  df-topon 19909  df-topsp 19910  df-cld 20020  df-ntr 20021  df-cls 20022  df-nei 20100  df-lp 20138  df-perf 20139  df-cn 20229  df-cnp 20230  df-haus 20317  df-tx 20563  df-hmeo 20756  df-fil 20847  df-fm 20939  df-flim 20940  df-flf 20941  df-xms 21321  df-ms 21322  df-tms 21323  df-cncf 21896  df-limc 22807  df-dv 22808  df-log 23492
This theorem is referenced by:  birthday  23866
  Copyright terms: Public domain W3C validator