HomeHome Metamath Proof Explorer < Previous   Next >
Related theorems
Unicode version

Theorem bcxmas 8336
Description: Parallel summation (Christmas Stocking) theorem for Pascal's Triangle. (Contributed by Paul Chapman, 18-May-2007.)
Assertion
Ref Expression
bcxmas |- ((N e. NN0 /\ M e. NN0) -> (((N + 1) + M) _C M) = sum_j e. (0...M)((N + j) _C j))
Distinct variable group:   j,N

Proof of Theorem bcxmas
StepHypRef Expression
1 bcxmaslem1 8334 . . . . 5 |- (m = 0 -> (((N + 1) + m) _C m) = (((N + 1) + 0) _C 0))
2 opreq2 4890 . . . . . 6 |- (m = 0 -> (0...m) = (0...0))
32sumeq1d 8250 . . . . 5 |- (m = 0 -> sum_j e. (0...m)((N + j) _C j) = sum_j e. (0...0)((N + j) _C j))
41, 3eqeq12d 1899 . . . 4 |- (m = 0 -> ((((N + 1) + m) _C m) = sum_j e. (0...m)((N + j) _C j) <-> (((N + 1) + 0) _C 0) = sum_j e. (0...0)((N + j) _C j)))
54imbi2d 674 . . 3 |- (m = 0 -> ((N e. NN0 -> (((N + 1) + m) _C m) = sum_j e. (0...m)((N + j) _C j)) <-> (N e. NN0 -> (((N + 1) + 0) _C 0) = sum_j e. (0...0)((N + j) _C j))))
6 bcxmaslem1 8334 . . . . 5 |- (m = k -> (((N + 1) + m) _C m) = (((N + 1) + k) _C k))
7 opreq2 4890 . . . . . 6 |- (m = k -> (0...m) = (0...k))
87sumeq1d 8250 . . . . 5 |- (m = k -> sum_j e. (0...m)((N + j) _C j) = sum_j e. (0...k)((N + j) _C j))
96, 8eqeq12d 1899 . . . 4 |- (m = k -> ((((N + 1) + m) _C m) = sum_j e. (0...m)((N + j) _C j) <-> (((N + 1) + k) _C k) = sum_j e. (0...k)((N + j) _C j)))
109imbi2d 674 . . 3 |- (m = k -> ((N e. NN0 -> (((N + 1) + m) _C m) = sum_j e. (0...m)((N + j) _C j)) <-> (N e. NN0 -> (((N + 1) + k) _C k) = sum_j e. (0...k)((N + j) _C j))))
11 bcxmaslem1 8334 . . . . 5 |- (m = (k + 1) -> (((N + 1) + m) _C m) = (((N + 1) + (k + 1)) _C (k + 1)))
12 opreq2 4890 . . . . . 6 |- (m = (k + 1) -> (0...m) = (0...(k + 1)))
1312sumeq1d 8250 . . . . 5 |- (m = (k + 1) -> sum_j e. (0...m)((N + j) _C j) = sum_j e. (0...(k + 1))((N + j) _C j))
1411, 13eqeq12d 1899 . . . 4 |- (m = (k + 1) -> ((((N + 1) + m) _C m) = sum_j e. (0...m)((N + j) _C j) <-> (((N + 1) + (k + 1)) _C (k + 1)) = sum_j e. (0...(k + 1))((N + j) _C j)))
1514imbi2d 674 . . 3 |- (m = (k + 1) -> ((N e. NN0 -> (((N + 1) + m) _C m) = sum_j e. (0...m)((N + j) _C j)) <-> (N e. NN0 -> (((N + 1) + (k + 1)) _C (k + 1)) = sum_j e. (0...(k + 1))((N + j) _C j))))
16 bcxmaslem1 8334 . . . . 5 |- (m = M -> (((N + 1) + m) _C m) = (((N + 1) + M) _C M))
17 opreq2 4890 . . . . . 6 |- (m = M -> (0...m) = (0...M))
1817sumeq1d 8250 . . . . 5 |- (m = M -> sum_j e. (0...m)((N + j) _C j) = sum_j e. (0...M)((N + j) _C j))
1916, 18eqeq12d 1899 . . . 4 |- (m = M -> ((((N + 1) + m) _C m) = sum_j e. (0...m)((N + j) _C j) <-> (((N + 1) + M) _C M) = sum_j e. (0...M)((N + j) _C j)))
2019imbi2d 674 . . 3 |- (m = M -> ((N e. NN0 -> (((N + 1) + m) _C m) = sum_j e. (0...m)((N + j) _C j)) <-> (N e. NN0 -> (((N + 1) + M) _C M) = sum_j e. (0...M)((N + j) _C j))))
21 0nn0 7322 . . . . 5 |- 0 e. NN0
22 nn0addcl 7329 . . . . . 6 |- ((N e. NN0 /\ 0 e. NN0) -> (N + 0) e. NN0)
23 bcn0 8215 . . . . . 6 |- ((N + 0) e. NN0 -> ((N + 0) _C 0) = 1)
2422, 23syl 12 . . . . 5 |- ((N e. NN0 /\ 0 e. NN0) -> ((N + 0) _C 0) = 1)
2521, 24mpan2 760 . . . 4 |- (N e. NN0 -> ((N + 0) _C 0) = 1)
26 bcxmaslem1 8334 . . . . . 6 |- (j = 0 -> ((N + j) _C j) = ((N + 0) _C 0))
2726fsum1i 8265 . . . . 5 |- ((((N + 0) _C 0) e. NN0 /\ 0 e. ZZ) -> sum_j e. (0...0)((N + j) _C j) = ((N + 0) _C 0))
28 1nn0 7323 . . . . . 6 |- 1 e. NN0
2925, 28syl6eqel 1979 . . . . 5 |- (N e. NN0 -> ((N + 0) _C 0) e. NN0)
30 0z 7355 . . . . 5 |- 0 e. ZZ
3127, 29, 30sylancl 525 . . . 4 |- (N e. NN0 -> sum_j e. (0...0)((N + j) _C j) = ((N + 0) _C 0))
32 peano2nn0 7333 . . . . . 6 |- (N e. NN0 -> (N + 1) e. NN0)
3332, 21jctir 317 . . . . 5 |- (N e. NN0 -> ((N + 1) e. NN0 /\ 0 e. NN0))
34 nn0addcl 7329 . . . . 5 |- (((N + 1) e. NN0 /\ 0 e. NN0) -> ((N + 1) + 0) e. NN0)
35 bcn0 8215 . . . . 5 |- (((N + 1) + 0) e. NN0 -> (((N + 1) + 0) _C 0) = 1)
3633, 34, 353syl 24 . . . 4 |- (N e. NN0 -> (((N + 1) + 0) _C 0) = 1)
3725, 31, 363eqtr4rd 1939 . . 3 |- (N e. NN0 -> (((N + 1) + 0) _C 0) = sum_j e. (0...0)((N + j) _C j))
38 simpr 350 . . . . . . . . . . 11 |- ((N e. NN0 /\ k e. NN0) -> k e. NN0)
39 elnn0uz 7610 . . . . . . . . . . 11 |- (k e. NN0 <-> k e. (ZZ>=` 0))
4038, 39sylib 215 . . . . . . . . . 10 |- ((N e. NN0 /\ k e. NN0) -> k e. (ZZ>=` 0))
41 oprex 4907 . . . . . . . . . . 11 |- ((N + j) _C j) e. _V
42 oprex 4907 . . . . . . . . . . 11 |- ((N + (k + 1)) _C (k + 1)) e. _V
43 bcxmaslem1 8334 . . . . . . . . . . 11 |- (j = (k + 1) -> ((N + j) _C j) = ((N + (k + 1)) _C (k + 1)))
4441, 42, 43fsump1i 8266 . . . . . . . . . 10 |- (k e. (ZZ>=`
0) -> sum_j e. (0...(k + 1))((N + j) _C j) = (sum_j e. (0...k)((N + j) _C j) + ((N + (k + 1)) _C (k + 1))))
4540, 44syl 12 . . . . . . . . 9 |- ((N e. NN0 /\ k e. NN0) -> sum_j e. (0...(k + 1))((N + j) _C j) = (sum_j e. (0...k)((N + j) _C j) + ((N + (k + 1)) _C (k + 1))))
46 nn0cn 7318 . . . . . . . . . . . . 13 |- (N e. NN0 -> N e. CC)
4746adantr 425 . . . . . . . . . . . 12 |- ((N e. NN0 /\ k e. NN0) -> N e. CC)
48 nn0cn 7318 . . . . . . . . . . . . 13 |- (k e. NN0 -> k e. CC)
4948adantl 424 . . . . . . . . . . . 12 |- ((N e. NN0 /\ k e. NN0) -> k e. CC)
50 ax1cn 6422 . . . . . . . . . . . . 13 |- 1 e. CC
5150a1i 8 . . . . . . . . . . . 12 |- ((N e. NN0 /\ k e. NN0) -> 1 e. CC)
52 bcxmaslem2 8335 . . . . . . . . . . . 12 |- ((N e. CC /\ k e. CC /\ 1 e. CC) -> (N + (k + 1)) = ((N + 1) + k))
5347, 49, 51, 52syl111anc 1100 . . . . . . . . . . 11 |- ((N e. NN0 /\ k e. NN0) -> (N + (k + 1)) = ((N + 1) + k))
5453opreq1d 4897 . . . . . . . . . 10 |- ((N e. NN0 /\ k e. NN0) -> ((N + (k + 1)) _C (k + 1)) = (((N + 1) + k) _C (k + 1)))
5554opreq2d 4898 . . . . . . . . 9 |- ((N e. NN0 /\ k e. NN0) -> (sum_j e. (0...k)((N + j) _C j) + ((N + (k + 1)) _C (k + 1))) = (sum_j e. (0...k)((N + j) _C j) + (((N + 1) + k) _C (k + 1))))
5645, 55eqtrd 1925 . . . . . . . 8 |- ((N e. NN0 /\ k e. NN0) -> sum_j e. (0...(k + 1))((N + j) _C j) = (sum_j e. (0...k)((N + j) _C j) + (((N + 1) + k) _C (k + 1))))
5756adantr 425 . . . . . . 7 |- (((N e. NN0 /\ k e. NN0) /\ (((N + 1) + k) _C k) = sum_j e. (0...k)((N + j) _C j)) -> sum_j e. (0...(k + 1))((N + j) _C j) = (sum_j e. (0...k)((N + j) _C j) + (((N + 1) + k) _C (k + 1))))
58 opreq1 4889 . . . . . . . 8 |- ((((N + 1) + k) _C k) = sum_j e. (0...k)((N + j) _C j) -> ((((N + 1) + k) _C k) + (((N + 1) + k) _C (k + 1))) = (sum_j e. (0...k)((N + j) _C j) + (((N + 1) + k) _C (k + 1))))
5958adantl 424 . . . . . . 7 |- (((N e. NN0 /\ k e. NN0) /\ (((N + 1) + k) _C k) = sum_j e. (0...k)((N + j) _C j)) -> ((((N + 1) + k) _C k) + (((N + 1) + k) _C (k + 1))) = (sum_j e. (0...k)((N + j) _C j) + (((N + 1) + k) _C (k + 1))))
60 pncan 6557 . . . . . . . . . . . . 13 |- ((k e. CC /\ 1 e. CC) -> ((k + 1) - 1) = k)
6160, 49, 50sylancl 525 . . . . . . . . . . . 12 |- ((N e. NN0 /\ k e. NN0) -> ((k + 1) - 1) = k)
6261opreq2d 4898 . . . . . . . . . . 11 |- ((N e. NN0 /\ k e. NN0) -> (((N + 1) + k) _C ((k + 1) - 1)) = (((N + 1) + k) _C k))
6362opreq2d 4898 . . . . . . . . . 10 |- ((N e. NN0 /\ k e. NN0) -> ((((N + 1) + k) _C (k + 1)) + (((N + 1) + k) _C ((k + 1) - 1))) = ((((N + 1) + k) _C (k + 1)) + (((N + 1) + k) _C k)))
64 nnnn0addcl 7334 . . . . . . . . . . . 12 |- (((N + 1) e. NN /\ k e. NN0) -> ((N + 1) + k) e. NN)
65 nn0p1nn 7384 . . . . . . . . . . . 12 |- (N e. NN0 -> (N + 1) e. NN)
6664, 65sylan 497 . . . . . . . . . . 11 |- ((N e. NN0 /\ k e. NN0) -> ((N + 1) + k) e. NN)
67 nn0p1nn 7384 . . . . . . . . . . . 12 |- (k e. NN0 -> (k + 1) e. NN)
6867adantl 424 . . . . . . . . . . 11 |- ((N e. NN0 /\ k e. NN0) -> (k + 1) e. NN)
69 nnre 7112 . . . . . . . . . . . . . 14 |- ((k + 1) e. NN -> (k + 1) e. RR)
7068, 69syl 12 . . . . . . . . . . . . 13 |- ((N e. NN0 /\ k e. NN0) -> (k + 1) e. RR)
71 simpl 346 . . . . . . . . . . . . 13 |- ((N e. NN0 /\ k e. NN0) -> N e. NN0)
72 nn0addge2 7340 . . . . . . . . . . . . 13 |- (((k + 1) e. RR /\ N e. NN0) -> (k + 1) <_ (N + (k + 1)))
7370, 71, 72syl11anc 524 . . . . . . . . . . . 12 |- ((N e. NN0 /\ k e. NN0) -> (k + 1) <_ (N + (k + 1)))
7473, 53breqtrd 3361 . . . . . . . . . . 11 |- ((N e. NN0 /\ k e. NN0) -> (k + 1) <_ ((N + 1) + k))
75 bcpasc2 8220 . . . . . . . . . . 11 |- ((((N + 1) + k) e. NN /\ (k + 1) e. NN /\ (k + 1) <_ ((N + 1) + k)) -> ((((N + 1) + k) _C (k + 1)) + (((N + 1) + k) _C ((k + 1) - 1))) = ((((N + 1) + k) + 1) _C (k + 1)))
7666, 68, 74, 75syl111anc 1100 . . . . . . . . . 10 |- ((N e. NN0 /\ k e. NN0) -> ((((N + 1) + k) _C (k + 1)) + (((N + 1) + k) _C ((k + 1) - 1))) = ((((N + 1) + k) + 1) _C (k + 1)))
7763, 76eqtr3d 1927 . . . . . . . . 9 |- ((N e. NN0 /\ k e. NN0) -> ((((N + 1) + k) _C (k + 1)) + (((N + 1) + k) _C k)) = ((((N + 1) + k) + 1) _C (k + 1)))
78 nnnn0 7315 . . . . . . . . . . . . 13 |- (((N + 1) + k) e. NN -> ((N + 1) + k) e. NN0)
7966, 78syl 12 . . . . . . . . . . . 12 |- ((N e. NN0 /\ k e. NN0) -> ((N + 1) + k) e. NN0)
80 nnz 7362 . . . . . . . . . . . . 13 |- ((k + 1) e. NN -> (k + 1) e. ZZ)
8168, 80syl 12 . . . . . . . . . . . 12 |- ((N e. NN0 /\ k e. NN0) -> (k + 1) e. ZZ)
82 bccl 8224 . . . . . . . . . . . 12 |- ((((N + 1) + k) e. NN0 /\ (k + 1) e. ZZ) -> (((N + 1) + k) _C (k + 1)) e. NN0)
8379, 81, 82syl11anc 524 . . . . . . . . . . 11 |- ((N e. NN0 /\ k e. NN0) -> (((N + 1) + k) _C (k + 1)) e. NN0)
84 nn0cn 7318 . . . . . . . . . . 11 |- ((((N + 1) + k) _C (k + 1)) e. NN0 -> (((N + 1) + k) _C (k + 1)) e. CC)
8583, 84syl 12 . . . . . . . . . 10 |- ((N e. NN0 /\ k e. NN0) -> (((N + 1) + k) _C (k + 1)) e. CC)
86 nn0addcl 7329 . . . . . . . . . . . . 13 |- (((N + 1) e. NN0 /\ k e. NN0) -> ((N + 1) + k) e. NN0)
87 nn0z 7363 . . . . . . . . . . . . . 14 |- (k e. NN0 -> k e. ZZ)
8887adantl 424 . . . . . . . . . . . . 13 |- (((N + 1) e. NN0 /\ k e. NN0) -> k e. ZZ)
89 bccl 8224 . . . . . . . . . . . . 13 |- ((((N + 1) + k) e. NN0 /\ k e. ZZ) -> (((N + 1) + k) _C k) e. NN0)
9086, 88, 89syl11anc 524 . . . . . . . . . . . 12 |- (((N + 1) e. NN0 /\ k e. NN0) -> (((N + 1) + k) _C k) e. NN0)
9190, 32sylan 497 . . . . . . . . . . 11 |- ((N e. NN0 /\ k e. NN0) -> (((N + 1) + k) _C k) e. NN0)
92 nn0cn 7318 . . . . . . . . . . 11 |- ((((N + 1) + k) _C k) e. NN0 -> (((N + 1) + k) _C k) e. CC)
9391, 92syl 12 . . . . . . . . . 10 |- ((N e. NN0 /\ k e. NN0) -> (((N + 1) + k) _C k) e. CC)
94 addcom 6458 . . . . . . . . . 10 |- (((((N + 1) + k) _C (k + 1)) e. CC /\ (((N + 1) + k) _C k) e. CC) -> ((((N + 1) + k) _C (k + 1)) + (((N + 1) + k) _C k)) = ((((N + 1) + k) _C k) + (((N + 1) + k) _C (k + 1))))
9585, 93, 94syl11anc 524 . . . . . . . . 9 |- ((N e. NN0 /\ k e. NN0) -> ((((N + 1) + k) _C (k + 1)) + (((N + 1) + k) _C k)) = ((((N + 1) + k) _C k) + (((N + 1) + k) _C (k + 1))))
96 peano2cn 6498 . . . . . . . . . . . . 13 |- (N e. CC -> (N + 1) e. CC)
9746, 96syl 12 . . . . . . . . . . . 12 |- (N e. NN0 -> (N + 1) e. CC)
9897adantr 425 . . . . . . . . . . 11 |- ((N e. NN0 /\ k e. NN0) -> (N + 1) e. CC)
99 addass 6460 . . . . . . . . . . 11 |- (((N + 1) e. CC /\ k e. CC /\ 1 e. CC) -> (((N + 1) + k) + 1) = ((N + 1) + (k + 1)))
10098, 49, 51, 99syl111anc 1100 . . . . . . . . . 10 |- ((N e. NN0 /\ k e. NN0) -> (((N + 1) + k) + 1) = ((N + 1) + (k + 1)))
101100opreq1d 4897 . . . . . . . . 9 |- ((N e. NN0 /\ k e. NN0) -> ((((N + 1) + k) + 1) _C (k + 1)) = (((N + 1) + (k + 1)) _C (k + 1)))
10277, 95, 1013eqtr3d 1934 . . . . . . . 8 |- ((N e. NN0 /\ k e. NN0) -> ((((N + 1) + k) _C k) + (((N + 1) + k) _C (k + 1))) = (((N + 1) + (k + 1)) _C (k + 1)))
103102adantr 425 . . . . . . 7 |- (((N e. NN0 /\ k e. NN0) /\ (((N + 1) + k) _C k) = sum_j e. (0...k)((N + j) _C j)) -> ((((N + 1) + k) _C k) + (((N + 1) + k) _C (k + 1))) = (((N + 1) + (k + 1)) _C (k + 1)))
10457, 59, 1033eqtr2rd 1933 . . . . . 6 |- (((N e. NN0 /\ k e. NN0) /\ (((N + 1) + k) _C k) = sum_j e. (0...k)((N + j) _C j)) -> (((N + 1) + (k + 1)) _C (k + 1)) = sum_j e. (0...(k + 1))((N + j) _C j))
105104ex 402 . . . . 5 |- ((N e. NN0 /\ k e. NN0) -> ((((N + 1) + k) _C k) = sum_j e. (0...k)((N + j) _C j) -> (((N + 1) + (k + 1)) _C (k + 1)) = sum_j e. (0...(k + 1))((N + j) _C j)))
106105expcom 403 . . . 4 |- (k e. NN0 -> (N e. NN0 -> ((((N + 1) + k) _C k) = sum_j e. (0...k)((N + j) _C j) -> (((N + 1) + (k + 1)) _C (k + 1)) = sum_j e. (0...(k + 1))((N + j) _C j))))
107106a2d 16 . . 3 |- (k e. NN0 -> ((N e. NN0 -> (((N + 1) + k) _C k) = sum_j e. (0...k)((N + j) _C j)) -> (N e. NN0 -> (((N + 1) + (k + 1)) _C (k + 1)) = sum_j e. (0...(k + 1))((N + j) _C j))))
1085, 10, 15, 20, 37, 107nn0ind 7424 . 2 |- (M e. NN0 -> (N e. NN0 -> (((N + 1) + M) _C M) = sum_j e. (0...M)((N + j) _C j)))
109108impcom 378 1 |- ((N e. NN0 /\ M e. NN0) -> (((N + 1) + M) _C M) = sum_j e. (0...M)((N + j) _C j))
Colors of variables: wff set class
Syntax hints:   -> wi 3   /\ wa 240   = wceq 1298   e. wcel 1300   class class class wbr 3338  ` cfv 3998  (class class class)co 4884  CCcc 6384  RRcr 6385  0cc0 6386  1c1 6387   + caddc 6389   - cmin 6445   <_ cle 6448  NNcn 6449  NN0cn0 6450  ZZcz 6451  ZZ>=cuz 7586  ...cfz 7637   _C cbc 8208  sum_csu 8239
This theorem was proved from axioms:  ax-1 4  ax-2 5  ax-3 6  ax-mp 7  ax-7 1304  ax-gen 1305  ax-8 1306  ax-9 1307  ax-10 1308  ax-11 1309  ax-12 1310  ax-13 1311  ax-14 1312  ax-17 1317  ax-4 1319  ax-5o 1321  ax-6o 1324  ax-9o 1481  ax-10o 1500  ax-16 1580  ax-11o 1588  ax-ext 1865  ax-rep 3428  ax-sep 3438  ax-nul 3445  ax-pow 3481  ax-pr 3524  ax-un 3790  ax-inf2 5731
This theorem depends on definitions:  df-bi 164  df-or 241  df-an 242  df-3or 859  df-3an 860  df-ex 1327  df-sb 1536  df-eu 1775  df-mo 1776  df-clab 1872  df-cleq 1877  df-clel 1880  df-ne 2019  df-nel 2020  df-ral 2109  df-rex 2110  df-reu 2111  df-rab 2112  df-v 2294  df-sbc 2454  df-csb 2541  df-dif 2597  df-un 2600  df-in 2603  df-ss 2605  df-pss 2607  df-nul 2876  df-if 2983  df-pw 3035  df-sn 3049  df-pr 3050  df-tp 3052  df-op 3053  df-uni 3178  df-int 3215  df-iun 3257  df-br 3339  df-opab 3396  df-tr 3412  df-eprel 3583  df-id 3586  df-po 3591  df-so 3604  df-fr 3625  df-we 3644  df-ord 3660  df-on 3661  df-lim 3662  df-suc 3663  df-om 3950  df-xp 4000  df-rel 4001  df-cnv 4002  df-co 4003  df-dm 4004  df-rn 4005  df-res 4006  df-ima 4007  df-fun 4008  df-fn 4009  df-f 4010  df-f1 4011  df-fo 4012  df-f1o 4013  df-fv 4014  df-opr 4886  df-oprab 4887  df-mpt 5006  df-1st 5020  df-2nd 5021  df-iota 5089  df-rdg 5140  df-1o 5177  df-oadd 5179  df-omul 5180  df-er 5318  df-ec 5320  df-qs 5323  df-en 5427  df-dom 5428  df-sdom 5429  df-undef 5556  df-riota 5560  df-ni 6152  df-pli 6153  df-mi 6154  df-lti 6155  df-plpq 6187  df-mpq 6188  df-enq 6189  df-nq 6190  df-plq 6191  df-mq 6192  df-rq 6193  df-ltq 6194  df-1q 6195  df-np 6238  df-1p 6239  df-plp 6240  df-mp 6241  df-ltp 6242  df-plpr 6316  df-mpr 6317  df-enr 6318  df-nr 6319  df-plr 6320  df-mr 6321  df-ltr 6322  df-0r 6323  df-1r 6324  df-m1r 6325  df-c 6392  df-0 6393  df-1 6394  df-i 6395  df-r 6396  df-plus 6397  df-mul 6398  df-lt 6399  df-sub 6511  df-neg 6513  df-pnf 6654  df-mnf 6655  df-xr 6656  df-ltxr 6657  df-le 6658  df-div 6892  df-n 7108  df-n0 7309  df-z 7345  df-uz 7587  df-fz 7638  df-seq1 7721  df-shft 7754  df-seqz 7776  df-fac 8184  df-bc 8209  df-sum 8240
Copyright terms: Public domain