Metamath Proof Explorer


Theorem seqcoll

Description: The function F contains a sparse set of nonzero values to be summed. The function G is an order isomorphism from the set of nonzero values of F to a 1-based finite sequence, and H collects these nonzero values together. Under these conditions, the sum over the values in H yields the same result as the sum over the original set F . (Contributed by Mario Carneiro, 2-Apr-2014)

Ref Expression
Hypotheses seqcoll.1 φ k S Z + ˙ k = k
seqcoll.1b φ k S k + ˙ Z = k
seqcoll.c φ k S n S k + ˙ n S
seqcoll.a φ Z S
seqcoll.2 φ G Isom < , < 1 A A
seqcoll.3 φ N 1 A
seqcoll.4 φ A M
seqcoll.5 φ k M G A F k S
seqcoll.6 φ k M G A A F k = Z
seqcoll.7 φ n 1 A H n = F G n
Assertion seqcoll φ seq M + ˙ F G N = seq 1 + ˙ H N

Proof

Step Hyp Ref Expression
1 seqcoll.1 φ k S Z + ˙ k = k
2 seqcoll.1b φ k S k + ˙ Z = k
3 seqcoll.c φ k S n S k + ˙ n S
4 seqcoll.a φ Z S
5 seqcoll.2 φ G Isom < , < 1 A A
6 seqcoll.3 φ N 1 A
7 seqcoll.4 φ A M
8 seqcoll.5 φ k M G A F k S
9 seqcoll.6 φ k M G A A F k = Z
10 seqcoll.7 φ n 1 A H n = F G n
11 elfznn N 1 A N
12 6 11 syl φ N
13 eleq1 y = 1 y 1 A 1 1 A
14 2fveq3 y = 1 seq M + ˙ F G y = seq M + ˙ F G 1
15 fveq2 y = 1 seq 1 + ˙ H y = seq 1 + ˙ H 1
16 14 15 eqeq12d y = 1 seq M + ˙ F G y = seq 1 + ˙ H y seq M + ˙ F G 1 = seq 1 + ˙ H 1
17 13 16 imbi12d y = 1 y 1 A seq M + ˙ F G y = seq 1 + ˙ H y 1 1 A seq M + ˙ F G 1 = seq 1 + ˙ H 1
18 17 imbi2d y = 1 φ y 1 A seq M + ˙ F G y = seq 1 + ˙ H y φ 1 1 A seq M + ˙ F G 1 = seq 1 + ˙ H 1
19 eleq1 y = m y 1 A m 1 A
20 2fveq3 y = m seq M + ˙ F G y = seq M + ˙ F G m
21 fveq2 y = m seq 1 + ˙ H y = seq 1 + ˙ H m
22 20 21 eqeq12d y = m seq M + ˙ F G y = seq 1 + ˙ H y seq M + ˙ F G m = seq 1 + ˙ H m
23 19 22 imbi12d y = m y 1 A seq M + ˙ F G y = seq 1 + ˙ H y m 1 A seq M + ˙ F G m = seq 1 + ˙ H m
24 23 imbi2d y = m φ y 1 A seq M + ˙ F G y = seq 1 + ˙ H y φ m 1 A seq M + ˙ F G m = seq 1 + ˙ H m
25 eleq1 y = m + 1 y 1 A m + 1 1 A
26 2fveq3 y = m + 1 seq M + ˙ F G y = seq M + ˙ F G m + 1
27 fveq2 y = m + 1 seq 1 + ˙ H y = seq 1 + ˙ H m + 1
28 26 27 eqeq12d y = m + 1 seq M + ˙ F G y = seq 1 + ˙ H y seq M + ˙ F G m + 1 = seq 1 + ˙ H m + 1
29 25 28 imbi12d y = m + 1 y 1 A seq M + ˙ F G y = seq 1 + ˙ H y m + 1 1 A seq M + ˙ F G m + 1 = seq 1 + ˙ H m + 1
30 29 imbi2d y = m + 1 φ y 1 A seq M + ˙ F G y = seq 1 + ˙ H y φ m + 1 1 A seq M + ˙ F G m + 1 = seq 1 + ˙ H m + 1
31 eleq1 y = N y 1 A N 1 A
32 2fveq3 y = N seq M + ˙ F G y = seq M + ˙ F G N
33 fveq2 y = N seq 1 + ˙ H y = seq 1 + ˙ H N
34 32 33 eqeq12d y = N seq M + ˙ F G y = seq 1 + ˙ H y seq M + ˙ F G N = seq 1 + ˙ H N
35 31 34 imbi12d y = N y 1 A seq M + ˙ F G y = seq 1 + ˙ H y N 1 A seq M + ˙ F G N = seq 1 + ˙ H N
36 35 imbi2d y = N φ y 1 A seq M + ˙ F G y = seq 1 + ˙ H y φ N 1 A seq M + ˙ F G N = seq 1 + ˙ H N
37 isof1o G Isom < , < 1 A A G : 1 A 1-1 onto A
38 5 37 syl φ G : 1 A 1-1 onto A
39 f1of G : 1 A 1-1 onto A G : 1 A A
40 38 39 syl φ G : 1 A A
41 elfzuz2 N 1 A A 1
42 6 41 syl φ A 1
43 eluzfz1 A 1 1 1 A
44 42 43 syl φ 1 1 A
45 40 44 ffvelrnd φ G 1 A
46 7 45 sseldd φ G 1 M
47 eluzle A 1 1 A
48 42 47 syl φ 1 A
49 fzssz 1 A
50 zssre
51 49 50 sstri 1 A
52 51 a1i φ 1 A
53 ressxr *
54 52 53 sstrdi φ 1 A *
55 eluzelre k M k
56 55 ssriv M
57 7 56 sstrdi φ A
58 57 53 sstrdi φ A *
59 eluzfz2 A 1 A 1 A
60 42 59 syl φ A 1 A
61 leisorel G Isom < , < 1 A A 1 A * A * 1 1 A A 1 A 1 A G 1 G A
62 5 54 58 44 60 61 syl122anc φ 1 A G 1 G A
63 48 62 mpbid φ G 1 G A
64 40 60 ffvelrnd φ G A A
65 7 64 sseldd φ G A M
66 eluzelz G A M G A
67 65 66 syl φ G A
68 elfz5 G 1 M G A G 1 M G A G 1 G A
69 46 67 68 syl2anc φ G 1 M G A G 1 G A
70 63 69 mpbird φ G 1 M G A
71 fveq2 k = G 1 F k = F G 1
72 71 eleq1d k = G 1 F k S F G 1 S
73 72 imbi2d k = G 1 φ F k S φ F G 1 S
74 8 expcom k M G A φ F k S
75 73 74 vtoclga G 1 M G A φ F G 1 S
76 70 75 mpcom φ F G 1 S
77 eluzelz G 1 M G 1
78 46 77 syl φ G 1
79 peano2zm G 1 G 1 1
80 78 79 syl φ G 1 1
81 80 zred φ G 1 1
82 78 zred φ G 1
83 67 zred φ G A
84 82 lem1d φ G 1 1 G 1
85 81 82 83 84 63 letrd φ G 1 1 G A
86 eluz G 1 1 G A G A G 1 1 G 1 1 G A
87 80 67 86 syl2anc φ G A G 1 1 G 1 1 G A
88 85 87 mpbird φ G A G 1 1
89 fzss2 G A G 1 1 M G 1 1 M G A
90 88 89 syl φ M G 1 1 M G A
91 90 sselda φ k M G 1 1 k M G A
92 eluzel2 G 1 M M
93 46 92 syl φ M
94 elfzm11 M G 1 k M G 1 1 k M k k < G 1
95 93 78 94 syl2anc φ k M G 1 1 k M k k < G 1
96 simp3 k M k k < G 1 k < G 1
97 82 adantr φ k A G 1
98 57 sselda φ k A k
99 f1ocnv G : 1 A 1-1 onto A G -1 : A 1-1 onto 1 A
100 38 99 syl φ G -1 : A 1-1 onto 1 A
101 f1of G -1 : A 1-1 onto 1 A G -1 : A 1 A
102 100 101 syl φ G -1 : A 1 A
103 102 ffvelrnda φ k A G -1 k 1 A
104 elfznn G -1 k 1 A G -1 k
105 103 104 syl φ k A G -1 k
106 105 nnge1d φ k A 1 G -1 k
107 5 adantr φ k A G Isom < , < 1 A A
108 54 adantr φ k A 1 A *
109 58 adantr φ k A A *
110 44 adantr φ k A 1 1 A
111 leisorel G Isom < , < 1 A A 1 A * A * 1 1 A G -1 k 1 A 1 G -1 k G 1 G G -1 k
112 107 108 109 110 103 111 syl122anc φ k A 1 G -1 k G 1 G G -1 k
113 106 112 mpbid φ k A G 1 G G -1 k
114 f1ocnvfv2 G : 1 A 1-1 onto A k A G G -1 k = k
115 38 114 sylan φ k A G G -1 k = k
116 113 115 breqtrd φ k A G 1 k
117 97 98 116 lensymd φ k A ¬ k < G 1
118 117 ex φ k A ¬ k < G 1
119 118 con2d φ k < G 1 ¬ k A
120 96 119 syl5 φ k M k k < G 1 ¬ k A
121 95 120 sylbid φ k M G 1 1 ¬ k A
122 121 imp φ k M G 1 1 ¬ k A
123 91 122 eldifd φ k M G 1 1 k M G A A
124 123 9 syldan φ k M G 1 1 F k = Z
125 1 4 46 76 124 seqid φ seq M + ˙ F G 1 = seq G 1 + ˙ F
126 125 fveq1d φ seq M + ˙ F G 1 G 1 = seq G 1 + ˙ F G 1
127 uzid G 1 G 1 G 1
128 78 127 syl φ G 1 G 1
129 128 fvresd φ seq M + ˙ F G 1 G 1 = seq M + ˙ F G 1
130 seq1 G 1 seq G 1 + ˙ F G 1 = F G 1
131 78 130 syl φ seq G 1 + ˙ F G 1 = F G 1
132 fveq2 n = 1 H n = H 1
133 2fveq3 n = 1 F G n = F G 1
134 132 133 eqeq12d n = 1 H n = F G n H 1 = F G 1
135 134 imbi2d n = 1 φ H n = F G n φ H 1 = F G 1
136 10 expcom n 1 A φ H n = F G n
137 135 136 vtoclga 1 1 A φ H 1 = F G 1
138 44 137 mpcom φ H 1 = F G 1
139 131 138 eqtr4d φ seq G 1 + ˙ F G 1 = H 1
140 126 129 139 3eqtr3d φ seq M + ˙ F G 1 = H 1
141 1z 1
142 seq1 1 seq 1 + ˙ H 1 = H 1
143 141 142 ax-mp seq 1 + ˙ H 1 = H 1
144 140 143 eqtr4di φ seq M + ˙ F G 1 = seq 1 + ˙ H 1
145 144 a1d φ 1 1 A seq M + ˙ F G 1 = seq 1 + ˙ H 1
146 simplr φ m m + 1 1 A m
147 nnuz = 1
148 146 147 eleqtrdi φ m m + 1 1 A m 1
149 nnz m m
150 149 ad2antlr φ m m + 1 1 A m
151 elfzuz3 m + 1 1 A A m + 1
152 151 adantl φ m m + 1 1 A A m + 1
153 peano2uzr m A m + 1 A m
154 150 152 153 syl2anc φ m m + 1 1 A A m
155 elfzuzb m 1 A m 1 A m
156 148 154 155 sylanbrc φ m m + 1 1 A m 1 A
157 156 ex φ m m + 1 1 A m 1 A
158 157 imim1d φ m m 1 A seq M + ˙ F G m = seq 1 + ˙ H m m + 1 1 A seq M + ˙ F G m = seq 1 + ˙ H m
159 oveq1 seq M + ˙ F G m = seq 1 + ˙ H m seq M + ˙ F G m + ˙ H m + 1 = seq 1 + ˙ H m + ˙ H m + 1
160 2 ad4ant14 φ m m + 1 1 A k S k + ˙ Z = k
161 7 ad2antrr φ m m + 1 1 A A M
162 40 ad2antrr φ m m + 1 1 A G : 1 A A
163 162 156 ffvelrnd φ m m + 1 1 A G m A
164 161 163 sseldd φ m m + 1 1 A G m M
165 nnre m m
166 165 ad2antlr φ m m + 1 1 A m
167 166 ltp1d φ m m + 1 1 A m < m + 1
168 5 ad2antrr φ m m + 1 1 A G Isom < , < 1 A A
169 simpr φ m m + 1 1 A m + 1 1 A
170 isorel G Isom < , < 1 A A m 1 A m + 1 1 A m < m + 1 G m < G m + 1
171 168 156 169 170 syl12anc φ m m + 1 1 A m < m + 1 G m < G m + 1
172 167 171 mpbid φ m m + 1 1 A G m < G m + 1
173 eluzelz G m M G m
174 164 173 syl φ m m + 1 1 A G m
175 162 169 ffvelrnd φ m m + 1 1 A G m + 1 A
176 161 175 sseldd φ m m + 1 1 A G m + 1 M
177 eluzelz G m + 1 M G m + 1
178 176 177 syl φ m m + 1 1 A G m + 1
179 zltlem1 G m G m + 1 G m < G m + 1 G m G m + 1 1
180 174 178 179 syl2anc φ m m + 1 1 A G m < G m + 1 G m G m + 1 1
181 172 180 mpbid φ m m + 1 1 A G m G m + 1 1
182 peano2zm G m + 1 G m + 1 1
183 178 182 syl φ m m + 1 1 A G m + 1 1
184 eluz G m G m + 1 1 G m + 1 1 G m G m G m + 1 1
185 174 183 184 syl2anc φ m m + 1 1 A G m + 1 1 G m G m G m + 1 1
186 181 185 mpbird φ m m + 1 1 A G m + 1 1 G m
187 183 zred φ m m + 1 1 A G m + 1 1
188 178 zred φ m m + 1 1 A G m + 1
189 83 ad2antrr φ m m + 1 1 A G A
190 188 lem1d φ m m + 1 1 A G m + 1 1 G m + 1
191 elfzle2 m + 1 1 A m + 1 A
192 191 adantl φ m m + 1 1 A m + 1 A
193 54 ad2antrr φ m m + 1 1 A 1 A *
194 58 ad2antrr φ m m + 1 1 A A *
195 60 ad2antrr φ m m + 1 1 A A 1 A
196 leisorel G Isom < , < 1 A A 1 A * A * m + 1 1 A A 1 A m + 1 A G m + 1 G A
197 168 193 194 169 195 196 syl122anc φ m m + 1 1 A m + 1 A G m + 1 G A
198 192 197 mpbid φ m m + 1 1 A G m + 1 G A
199 187 188 189 190 198 letrd φ m m + 1 1 A G m + 1 1 G A
200 67 ad2antrr φ m m + 1 1 A G A
201 eluz G m + 1 1 G A G A G m + 1 1 G m + 1 1 G A
202 183 200 201 syl2anc φ m m + 1 1 A G A G m + 1 1 G m + 1 1 G A
203 199 202 mpbird φ m m + 1 1 A G A G m + 1 1
204 uztrn G A G m + 1 1 G m + 1 1 G m G A G m
205 203 186 204 syl2anc φ m m + 1 1 A G A G m
206 fzss2 G A G m M G m M G A
207 205 206 syl φ m m + 1 1 A M G m M G A
208 207 sselda φ m m + 1 1 A k M G m k M G A
209 8 ad4ant14 φ m m + 1 1 A k M G A F k S
210 208 209 syldan φ m m + 1 1 A k M G m F k S
211 3 ad4ant14 φ m m + 1 1 A k S n S k + ˙ n S
212 164 210 211 seqcl φ m m + 1 1 A seq M + ˙ F G m S
213 simplll φ m m + 1 1 A k G m + 1 G m + 1 1 φ
214 elfzuz k G m + 1 G m + 1 1 k G m + 1
215 peano2uz G m M G m + 1 M
216 164 215 syl φ m m + 1 1 A G m + 1 M
217 uztrn k G m + 1 G m + 1 M k M
218 214 216 217 syl2anr φ m m + 1 1 A k G m + 1 G m + 1 1 k M
219 elfzuz3 k G m + 1 G m + 1 1 G m + 1 1 k
220 uztrn G A G m + 1 1 G m + 1 1 k G A k
221 203 219 220 syl2an φ m m + 1 1 A k G m + 1 G m + 1 1 G A k
222 elfzuzb k M G A k M G A k
223 218 221 222 sylanbrc φ m m + 1 1 A k G m + 1 G m + 1 1 k M G A
224 149 ad2antlr φ m m + 1 1 A k A m
225 102 ad2antrr φ m m + 1 1 A k A G -1 : A 1 A
226 simprr φ m m + 1 1 A k A k A
227 225 226 ffvelrnd φ m m + 1 1 A k A G -1 k 1 A
228 227 elfzelzd φ m m + 1 1 A k A G -1 k
229 btwnnz m m < G -1 k G -1 k < m + 1 ¬ G -1 k
230 229 3expib m m < G -1 k G -1 k < m + 1 ¬ G -1 k
231 230 con2d m G -1 k ¬ m < G -1 k G -1 k < m + 1
232 224 228 231 sylc φ m m + 1 1 A k A ¬ m < G -1 k G -1 k < m + 1
233 5 ad2antrr φ m m + 1 1 A k A G Isom < , < 1 A A
234 156 adantrr φ m m + 1 1 A k A m 1 A
235 isorel G Isom < , < 1 A A m 1 A G -1 k 1 A m < G -1 k G m < G G -1 k
236 233 234 227 235 syl12anc φ m m + 1 1 A k A m < G -1 k G m < G G -1 k
237 38 ad2antrr φ m m + 1 1 A k A G : 1 A 1-1 onto A
238 237 226 114 syl2anc φ m m + 1 1 A k A G G -1 k = k
239 238 breq2d φ m m + 1 1 A k A G m < G G -1 k G m < k
240 174 adantrr φ m m + 1 1 A k A G m
241 7 ad2antrr φ m m + 1 1 A k A A M
242 241 226 sseldd φ m m + 1 1 A k A k M
243 eluzelz k M k
244 242 243 syl φ m m + 1 1 A k A k
245 zltp1le G m k G m < k G m + 1 k
246 240 244 245 syl2anc φ m m + 1 1 A k A G m < k G m + 1 k
247 236 239 246 3bitrd φ m m + 1 1 A k A m < G -1 k G m + 1 k
248 169 adantrr φ m m + 1 1 A k A m + 1 1 A
249 isorel G Isom < , < 1 A A G -1 k 1 A m + 1 1 A G -1 k < m + 1 G G -1 k < G m + 1
250 233 227 248 249 syl12anc φ m m + 1 1 A k A G -1 k < m + 1 G G -1 k < G m + 1
251 238 breq1d φ m m + 1 1 A k A G G -1 k < G m + 1 k < G m + 1
252 178 adantrr φ m m + 1 1 A k A G m + 1
253 zltlem1 k G m + 1 k < G m + 1 k G m + 1 1
254 244 252 253 syl2anc φ m m + 1 1 A k A k < G m + 1 k G m + 1 1
255 250 251 254 3bitrd φ m m + 1 1 A k A G -1 k < m + 1 k G m + 1 1
256 247 255 anbi12d φ m m + 1 1 A k A m < G -1 k G -1 k < m + 1 G m + 1 k k G m + 1 1
257 232 256 mtbid φ m m + 1 1 A k A ¬ G m + 1 k k G m + 1 1
258 257 expr φ m m + 1 1 A k A ¬ G m + 1 k k G m + 1 1
259 258 con2d φ m m + 1 1 A G m + 1 k k G m + 1 1 ¬ k A
260 elfzle1 k G m + 1 G m + 1 1 G m + 1 k
261 elfzle2 k G m + 1 G m + 1 1 k G m + 1 1
262 260 261 jca k G m + 1 G m + 1 1 G m + 1 k k G m + 1 1
263 259 262 impel φ m m + 1 1 A k G m + 1 G m + 1 1 ¬ k A
264 223 263 eldifd φ m m + 1 1 A k G m + 1 G m + 1 1 k M G A A
265 213 264 9 syl2anc φ m m + 1 1 A k G m + 1 G m + 1 1 F k = Z
266 160 164 186 212 265 seqid2 φ m m + 1 1 A seq M + ˙ F G m = seq M + ˙ F G m + 1 1
267 266 oveq1d φ m m + 1 1 A seq M + ˙ F G m + ˙ F G m + 1 = seq M + ˙ F G m + 1 1 + ˙ F G m + 1
268 fveq2 n = m + 1 H n = H m + 1
269 2fveq3 n = m + 1 F G n = F G m + 1
270 268 269 eqeq12d n = m + 1 H n = F G n H m + 1 = F G m + 1
271 270 imbi2d n = m + 1 φ H n = F G n φ H m + 1 = F G m + 1
272 271 136 vtoclga m + 1 1 A φ H m + 1 = F G m + 1
273 272 impcom φ m + 1 1 A H m + 1 = F G m + 1
274 273 adantlr φ m m + 1 1 A H m + 1 = F G m + 1
275 274 oveq2d φ m m + 1 1 A seq M + ˙ F G m + ˙ H m + 1 = seq M + ˙ F G m + ˙ F G m + 1
276 93 ad2antrr φ m m + 1 1 A M
277 178 zcnd φ m m + 1 1 A G m + 1
278 ax-1cn 1
279 npcan G m + 1 1 G m + 1 - 1 + 1 = G m + 1
280 277 278 279 sylancl φ m m + 1 1 A G m + 1 - 1 + 1 = G m + 1
281 uztrn G m + 1 1 G m G m M G m + 1 1 M
282 186 164 281 syl2anc φ m m + 1 1 A G m + 1 1 M
283 eluzp1p1 G m + 1 1 M G m + 1 - 1 + 1 M + 1
284 282 283 syl φ m m + 1 1 A G m + 1 - 1 + 1 M + 1
285 280 284 eqeltrrd φ m m + 1 1 A G m + 1 M + 1
286 seqm1 M G m + 1 M + 1 seq M + ˙ F G m + 1 = seq M + ˙ F G m + 1 1 + ˙ F G m + 1
287 276 285 286 syl2anc φ m m + 1 1 A seq M + ˙ F G m + 1 = seq M + ˙ F G m + 1 1 + ˙ F G m + 1
288 267 275 287 3eqtr4rd φ m m + 1 1 A seq M + ˙ F G m + 1 = seq M + ˙ F G m + ˙ H m + 1
289 seqp1 m 1 seq 1 + ˙ H m + 1 = seq 1 + ˙ H m + ˙ H m + 1
290 148 289 syl φ m m + 1 1 A seq 1 + ˙ H m + 1 = seq 1 + ˙ H m + ˙ H m + 1
291 288 290 eqeq12d φ m m + 1 1 A seq M + ˙ F G m + 1 = seq 1 + ˙ H m + 1 seq M + ˙ F G m + ˙ H m + 1 = seq 1 + ˙ H m + ˙ H m + 1
292 159 291 syl5ibr φ m m + 1 1 A seq M + ˙ F G m = seq 1 + ˙ H m seq M + ˙ F G m + 1 = seq 1 + ˙ H m + 1
293 292 ex φ m m + 1 1 A seq M + ˙ F G m = seq 1 + ˙ H m seq M + ˙ F G m + 1 = seq 1 + ˙ H m + 1
294 293 a2d φ m m + 1 1 A seq M + ˙ F G m = seq 1 + ˙ H m m + 1 1 A seq M + ˙ F G m + 1 = seq 1 + ˙ H m + 1
295 158 294 syld φ m m 1 A seq M + ˙ F G m = seq 1 + ˙ H m m + 1 1 A seq M + ˙ F G m + 1 = seq 1 + ˙ H m + 1
296 295 expcom m φ m 1 A seq M + ˙ F G m = seq 1 + ˙ H m m + 1 1 A seq M + ˙ F G m + 1 = seq 1 + ˙ H m + 1
297 296 a2d m φ m 1 A seq M + ˙ F G m = seq 1 + ˙ H m φ m + 1 1 A seq M + ˙ F G m + 1 = seq 1 + ˙ H m + 1
298 18 24 30 36 145 297 nnind N φ N 1 A seq M + ˙ F G N = seq 1 + ˙ H N
299 12 298 mpcom φ N 1 A seq M + ˙ F G N = seq 1 + ˙ H N
300 6 299 mpd φ seq M + ˙ F G N = seq 1 + ˙ H N