Metamath Proof Explorer


Theorem o1fsum

Description: If A ( k ) is O(1), then sum_ k <_ x , A ( k ) is O( x ). (Contributed by Mario Carneiro, 23-May-2016)

Ref Expression
Hypotheses o1fsum.1 φ k A V
o1fsum.2 φ k A 𝑂1
Assertion o1fsum φ x + k = 1 x A x 𝑂1

Proof

Step Hyp Ref Expression
1 o1fsum.1 φ k A V
2 o1fsum.2 φ k A 𝑂1
3 nnssre
4 3 a1i φ
5 1 2 o1mptrcl φ k A
6 1red φ 1
7 4 5 6 elo1mpt2 φ k A 𝑂1 c 1 +∞ m k c k A m
8 2 7 mpbid φ c 1 +∞ m k c k A m
9 rpssre +
10 9 a1i φ c 1 +∞ m k c k A m +
11 nfcv _ n A
12 nfcsb1v _ k n / k A
13 csbeq1a k = n A = n / k A
14 11 12 13 cbvsumi k = 1 x A = n = 1 x n / k A
15 fzfid φ c 1 +∞ m k c k A m x + 1 x Fin
16 o1f k A 𝑂1 k A : dom k A
17 2 16 syl φ k A : dom k A
18 1 ralrimiva φ k A V
19 dmmptg k A V dom k A =
20 18 19 syl φ dom k A =
21 20 feq2d φ k A : dom k A k A :
22 17 21 mpbid φ k A :
23 eqid k A = k A
24 23 fmpt k A k A :
25 22 24 sylibr φ k A
26 25 ad3antrrr φ c 1 +∞ m k c k A m x + k A
27 elfznn n 1 x n
28 12 nfel1 k n / k A
29 13 eleq1d k = n A n / k A
30 28 29 rspc n k A n / k A
31 30 impcom k A n n / k A
32 26 27 31 syl2an φ c 1 +∞ m k c k A m x + n 1 x n / k A
33 15 32 fsumcl φ c 1 +∞ m k c k A m x + n = 1 x n / k A
34 14 33 eqeltrid φ c 1 +∞ m k c k A m x + k = 1 x A
35 rpcn x + x
36 35 adantl φ c 1 +∞ m k c k A m x + x
37 rpne0 x + x 0
38 37 adantl φ c 1 +∞ m k c k A m x + x 0
39 34 36 38 divcld φ c 1 +∞ m k c k A m x + k = 1 x A x
40 simplrl φ c 1 +∞ m k c k A m c 1 +∞
41 1re 1
42 elicopnf 1 c 1 +∞ c 1 c
43 41 42 ax-mp c 1 +∞ c 1 c
44 40 43 sylib φ c 1 +∞ m k c k A m c 1 c
45 44 simpld φ c 1 +∞ m k c k A m c
46 fzfid φ c 1 +∞ m k c k A m 1 c Fin
47 25 ad2antrr φ c 1 +∞ m k c k A m k A
48 elfznn n 1 c n
49 47 48 31 syl2an φ c 1 +∞ m k c k A m n 1 c n / k A
50 49 abscld φ c 1 +∞ m k c k A m n 1 c n / k A
51 46 50 fsumrecl φ c 1 +∞ m k c k A m n = 1 c n / k A
52 simplrr φ c 1 +∞ m k c k A m m
53 51 52 readdcld φ c 1 +∞ m k c k A m n = 1 c n / k A + m
54 34 36 38 absdivd φ c 1 +∞ m k c k A m x + k = 1 x A x = k = 1 x A x
55 54 adantrr φ c 1 +∞ m k c k A m x + c x k = 1 x A x = k = 1 x A x
56 rprege0 x + x 0 x
57 56 ad2antrl φ c 1 +∞ m k c k A m x + c x x 0 x
58 absid x 0 x x = x
59 57 58 syl φ c 1 +∞ m k c k A m x + c x x = x
60 59 oveq2d φ c 1 +∞ m k c k A m x + c x k = 1 x A x = k = 1 x A x
61 55 60 eqtrd φ c 1 +∞ m k c k A m x + c x k = 1 x A x = k = 1 x A x
62 34 adantrr φ c 1 +∞ m k c k A m x + c x k = 1 x A
63 62 abscld φ c 1 +∞ m k c k A m x + c x k = 1 x A
64 fzfid φ c 1 +∞ m k c k A m x + c x 1 x Fin
65 47 27 31 syl2an φ c 1 +∞ m k c k A m n 1 x n / k A
66 65 adantlr φ c 1 +∞ m k c k A m x + c x n 1 x n / k A
67 66 abscld φ c 1 +∞ m k c k A m x + c x n 1 x n / k A
68 64 67 fsumrecl φ c 1 +∞ m k c k A m x + c x n = 1 x n / k A
69 57 simpld φ c 1 +∞ m k c k A m x + c x x
70 51 adantr φ c 1 +∞ m k c k A m x + c x n = 1 c n / k A
71 52 adantr φ c 1 +∞ m k c k A m x + c x m
72 70 71 readdcld φ c 1 +∞ m k c k A m x + c x n = 1 c n / k A + m
73 69 72 remulcld φ c 1 +∞ m k c k A m x + c x x n = 1 c n / k A + m
74 14 fveq2i k = 1 x A = n = 1 x n / k A
75 64 66 fsumabs φ c 1 +∞ m k c k A m x + c x n = 1 x n / k A n = 1 x n / k A
76 74 75 eqbrtrid φ c 1 +∞ m k c k A m x + c x k = 1 x A n = 1 x n / k A
77 fzfid φ c 1 +∞ m k c k A m x + c x c + 1 x Fin
78 ssun2 c + 1 x 1 c c + 1 x
79 flge1nn c 1 c c
80 44 79 syl φ c 1 +∞ m k c k A m c
81 80 adantr φ c 1 +∞ m k c k A m x + c x c
82 81 nnred φ c 1 +∞ m k c k A m x + c x c
83 45 adantr φ c 1 +∞ m k c k A m x + c x c
84 flle c c c
85 83 84 syl φ c 1 +∞ m k c k A m x + c x c c
86 simprr φ c 1 +∞ m k c k A m x + c x c x
87 82 83 69 85 86 letrd φ c 1 +∞ m k c k A m x + c x c x
88 fznnfl x c 1 x c c x
89 69 88 syl φ c 1 +∞ m k c k A m x + c x c 1 x c c x
90 81 87 89 mpbir2and φ c 1 +∞ m k c k A m x + c x c 1 x
91 fzsplit c 1 x 1 x = 1 c c + 1 x
92 90 91 syl φ c 1 +∞ m k c k A m x + c x 1 x = 1 c c + 1 x
93 78 92 sseqtrrid φ c 1 +∞ m k c k A m x + c x c + 1 x 1 x
94 93 sselda φ c 1 +∞ m k c k A m x + c x n c + 1 x n 1 x
95 65 abscld φ c 1 +∞ m k c k A m n 1 x n / k A
96 95 adantlr φ c 1 +∞ m k c k A m x + c x n 1 x n / k A
97 94 96 syldan φ c 1 +∞ m k c k A m x + c x n c + 1 x n / k A
98 77 97 fsumrecl φ c 1 +∞ m k c k A m x + c x n = c + 1 x n / k A
99 69 70 remulcld φ c 1 +∞ m k c k A m x + c x x n = 1 c n / k A
100 69 71 remulcld φ c 1 +∞ m k c k A m x + c x x m
101 70 recnd φ c 1 +∞ m k c k A m x + c x n = 1 c n / k A
102 101 mulid2d φ c 1 +∞ m k c k A m x + c x 1 n = 1 c n / k A = n = 1 c n / k A
103 1red φ c 1 +∞ m k c k A m x + c x 1
104 49 absge0d φ c 1 +∞ m k c k A m n 1 c 0 n / k A
105 46 50 104 fsumge0 φ c 1 +∞ m k c k A m 0 n = 1 c n / k A
106 51 105 jca φ c 1 +∞ m k c k A m n = 1 c n / k A 0 n = 1 c n / k A
107 106 adantr φ c 1 +∞ m k c k A m x + c x n = 1 c n / k A 0 n = 1 c n / k A
108 44 simprd φ c 1 +∞ m k c k A m 1 c
109 108 adantr φ c 1 +∞ m k c k A m x + c x 1 c
110 103 83 69 109 86 letrd φ c 1 +∞ m k c k A m x + c x 1 x
111 lemul1a 1 x n = 1 c n / k A 0 n = 1 c n / k A 1 x 1 n = 1 c n / k A x n = 1 c n / k A
112 103 69 107 110 111 syl31anc φ c 1 +∞ m k c k A m x + c x 1 n = 1 c n / k A x n = 1 c n / k A
113 102 112 eqbrtrrd φ c 1 +∞ m k c k A m x + c x n = 1 c n / k A x n = 1 c n / k A
114 hashcl c + 1 x Fin c + 1 x 0
115 nn0re c + 1 x 0 c + 1 x
116 77 114 115 3syl φ c 1 +∞ m k c k A m x + c x c + 1 x
117 116 71 remulcld φ c 1 +∞ m k c k A m x + c x c + 1 x m
118 71 adantr φ c 1 +∞ m k c k A m x + c x n c + 1 x m
119 elfzuz n c + 1 x n c + 1
120 81 peano2nnd φ c 1 +∞ m k c k A m x + c x c + 1
121 eluznn c + 1 n c + 1 n
122 120 121 sylan φ c 1 +∞ m k c k A m x + c x n c + 1 n
123 simpllr φ c 1 +∞ m k c k A m x + c x n c + 1 k c k A m
124 83 adantr φ c 1 +∞ m k c k A m x + c x n c + 1 c
125 reflcl c c
126 peano2re c c + 1
127 124 125 126 3syl φ c 1 +∞ m k c k A m x + c x n c + 1 c + 1
128 122 nnred φ c 1 +∞ m k c k A m x + c x n c + 1 n
129 fllep1 c c c + 1
130 124 129 syl φ c 1 +∞ m k c k A m x + c x n c + 1 c c + 1
131 eluzle n c + 1 c + 1 n
132 131 adantl φ c 1 +∞ m k c k A m x + c x n c + 1 c + 1 n
133 124 127 128 130 132 letrd φ c 1 +∞ m k c k A m x + c x n c + 1 c n
134 nfv k c n
135 nfcv _ k abs
136 135 12 nffv _ k n / k A
137 nfcv _ k
138 nfcv _ k m
139 136 137 138 nfbr k n / k A m
140 134 139 nfim k c n n / k A m
141 breq2 k = n c k c n
142 13 fveq2d k = n A = n / k A
143 142 breq1d k = n A m n / k A m
144 141 143 imbi12d k = n c k A m c n n / k A m
145 140 144 rspc n k c k A m c n n / k A m
146 122 123 133 145 syl3c φ c 1 +∞ m k c k A m x + c x n c + 1 n / k A m
147 119 146 sylan2 φ c 1 +∞ m k c k A m x + c x n c + 1 x n / k A m
148 77 97 118 147 fsumle φ c 1 +∞ m k c k A m x + c x n = c + 1 x n / k A n = c + 1 x m
149 71 recnd φ c 1 +∞ m k c k A m x + c x m
150 fsumconst c + 1 x Fin m n = c + 1 x m = c + 1 x m
151 77 149 150 syl2anc φ c 1 +∞ m k c k A m x + c x n = c + 1 x m = c + 1 x m
152 148 151 breqtrd φ c 1 +∞ m k c k A m x + c x n = c + 1 x n / k A c + 1 x m
153 biidd n = c + 1 0 m 0 m
154 0red φ c 1 +∞ m k c k A m x + c x n c + 1 0
155 47 30 mpan9 φ c 1 +∞ m k c k A m n n / k A
156 155 adantlr φ c 1 +∞ m k c k A m x + c x n n / k A
157 122 156 syldan φ c 1 +∞ m k c k A m x + c x n c + 1 n / k A
158 157 abscld φ c 1 +∞ m k c k A m x + c x n c + 1 n / k A
159 71 adantr φ c 1 +∞ m k c k A m x + c x n c + 1 m
160 157 absge0d φ c 1 +∞ m k c k A m x + c x n c + 1 0 n / k A
161 154 158 159 160 146 letrd φ c 1 +∞ m k c k A m x + c x n c + 1 0 m
162 161 ralrimiva φ c 1 +∞ m k c k A m x + c x n c + 1 0 m
163 120 nnzd φ c 1 +∞ m k c k A m x + c x c + 1
164 uzid c + 1 c + 1 c + 1
165 163 164 syl φ c 1 +∞ m k c k A m x + c x c + 1 c + 1
166 153 162 165 rspcdva φ c 1 +∞ m k c k A m x + c x 0 m
167 reflcl x x
168 69 167 syl φ c 1 +∞ m k c k A m x + c x x
169 ssdomg 1 x Fin c + 1 x 1 x c + 1 x 1 x
170 64 93 169 sylc φ c 1 +∞ m k c k A m x + c x c + 1 x 1 x
171 hashdomi c + 1 x 1 x c + 1 x 1 x
172 170 171 syl φ c 1 +∞ m k c k A m x + c x c + 1 x 1 x
173 flge0nn0 x 0 x x 0
174 hashfz1 x 0 1 x = x
175 57 173 174 3syl φ c 1 +∞ m k c k A m x + c x 1 x = x
176 172 175 breqtrd φ c 1 +∞ m k c k A m x + c x c + 1 x x
177 flle x x x
178 69 177 syl φ c 1 +∞ m k c k A m x + c x x x
179 116 168 69 176 178 letrd φ c 1 +∞ m k c k A m x + c x c + 1 x x
180 116 69 71 166 179 lemul1ad φ c 1 +∞ m k c k A m x + c x c + 1 x m x m
181 98 117 100 152 180 letrd φ c 1 +∞ m k c k A m x + c x n = c + 1 x n / k A x m
182 70 98 99 100 113 181 le2addd φ c 1 +∞ m k c k A m x + c x n = 1 c n / k A + n = c + 1 x n / k A x n = 1 c n / k A + x m
183 ltp1 c c < c + 1
184 fzdisj c < c + 1 1 c c + 1 x =
185 82 183 184 3syl φ c 1 +∞ m k c k A m x + c x 1 c c + 1 x =
186 96 recnd φ c 1 +∞ m k c k A m x + c x n 1 x n / k A
187 185 92 64 186 fsumsplit φ c 1 +∞ m k c k A m x + c x n = 1 x n / k A = n = 1 c n / k A + n = c + 1 x n / k A
188 36 adantrr φ c 1 +∞ m k c k A m x + c x x
189 188 101 149 adddid φ c 1 +∞ m k c k A m x + c x x n = 1 c n / k A + m = x n = 1 c n / k A + x m
190 182 187 189 3brtr4d φ c 1 +∞ m k c k A m x + c x n = 1 x n / k A x n = 1 c n / k A + m
191 63 68 73 76 190 letrd φ c 1 +∞ m k c k A m x + c x k = 1 x A x n = 1 c n / k A + m
192 rpregt0 x + x 0 < x
193 192 ad2antrl φ c 1 +∞ m k c k A m x + c x x 0 < x
194 ledivmul k = 1 x A n = 1 c n / k A + m x 0 < x k = 1 x A x n = 1 c n / k A + m k = 1 x A x n = 1 c n / k A + m
195 63 72 193 194 syl3anc φ c 1 +∞ m k c k A m x + c x k = 1 x A x n = 1 c n / k A + m k = 1 x A x n = 1 c n / k A + m
196 191 195 mpbird φ c 1 +∞ m k c k A m x + c x k = 1 x A x n = 1 c n / k A + m
197 61 196 eqbrtrd φ c 1 +∞ m k c k A m x + c x k = 1 x A x n = 1 c n / k A + m
198 10 39 45 53 197 elo1d φ c 1 +∞ m k c k A m x + k = 1 x A x 𝑂1
199 198 ex φ c 1 +∞ m k c k A m x + k = 1 x A x 𝑂1
200 199 rexlimdvva φ c 1 +∞ m k c k A m x + k = 1 x A x 𝑂1
201 8 200 mpd φ x + k = 1 x A x 𝑂1