Proof of proveit.numbers.summation.sum_first_n_int theorem

import proveit
from proveit import defaults, Function
from proveit.logic import Implies, Equals, InSet
from proveit.numbers import Add, frac, Mult, subtract, Sum
# from proveit.numbers import Natural
from proveit.numbers import zero, one, two
from proveit import m, n, x, P
# from proveit.numbers.summation  import sum_single
from proveit.numbers.number_sets.natural_numbers import fold_forall_natural_pos
# from proveit.numbers.numerals.decimals import pos_nat1
theory = proveit.Theory() # the theorem's theory

%proving sum_first_n_int

With these allowed/disallowed theorem/theory presumptions (e.g., to avoid circular dependencies), we begin our proof of
sum_first_n_int:
(see dependencies)

Instantiate the Induction Theorem for an induction proof

sum_first_n_int.instance_expr

fold_forall_natural_pos

 ⊢  

induction_inst = fold_forall_natural_pos.instantiate(
        {Function(P, n):sum_first_n_int.instance_expr})

induction_inst:  ⊢  

Note that the base case was proven automatically via auto-simplification.

Inductive Step

inductive_step = induction_inst.antecedent.operands[1]

inductive_step:

# this looks like a tuple, but is actually a set with no
# predictable order for the elements
inductive_step.conditions

defaults.assumptions = inductive_step.conditions

defaults.assumptions:

sum_one_to_m_plus_one = induction_inst.antecedent.operands[1].instance_expr.lhs

sum_one_to_m_plus_one:

sum_one_to_m_plus_one_split = sum_one_to_m_plus_one.partition(
    split_index=Add(m, one), side='before').inner_expr().rhs.associate(1, 2)

sum_one_to_m_plus_one_split:  ⊢  

sum_one_to_m_plus_one_split.rhs.operands[0].domain.simplification()

 ⊢  

inductive_hypothesis = defaults.assumptions[1]

inductive_hypothesis:

inductive_hypothesis_judgment = inductive_hypothesis.prove()

inductive_hypothesis_judgment:  ⊢  

sum_one_to_m_plus_one_simplified_01 = inductive_hypothesis.sub_right_side_into(
    sum_one_to_m_plus_one_split, auto_simplify=False)

sum_one_to_m_plus_one_simplified_01: ,  ⊢  

alg_manip_01 = Equals(Add(m, one), frac(Mult(two, Add(m, one)), two)).prove()

alg_manip_01:  ⊢  

sum_one_to_m_plus_one_simplified_02 = alg_manip_01.sub_right_side_into(sum_one_to_m_plus_one_simplified_01.inner_expr().rhs.operands[1])

sum_one_to_m_plus_one_simplified_02: ,  ⊢  

sum_one_to_m_plus_one_simplified_03 = sum_one_to_m_plus_one_simplified_02.inner_expr().rhs.factor(
    frac(Add(m, one), two))

sum_one_to_m_plus_one_simplified_03: ,  ⊢  

alg_manip_02 = frac(Mult(Add(m, one), Add(m, two)), two).factorization(
    frac(Add(m, one), two))

alg_manip_02:  ⊢  

alg_manip_02.sub_left_side_into(sum_one_to_m_plus_one_simplified_03.inner_expr().rhs)

,  ⊢  

inductive_step.prove()

 ⊢  

induction_inst.derive_consequent()

 ⊢  

sum_first_n_int has been proven.  Now simply execute "%qed".

%qed

proveit.numbers.summation.sum_first_n_int has been proven.

	step type	requirements	statement
0	modus ponens	1, 2	⊢
1	instantiation	3, 4*, 5*	⊢
	:
2	instantiation	6, 7, 8	⊢
	: , :
3	conjecture		⊢
	proveit.numbers.number_sets.natural_numbers.fold_forall_natural_pos
4	instantiation	173, 9, 10	⊢
	: , : , :
5	instantiation	173, 11, 12	⊢
	: , : , :
6	theorem		⊢
	proveit.logic.booleans.conjunction.and_if_both
7	axiom		⊢
	proveit.logic.booleans.true_axiom
8	generalization	13	⊢
9	instantiation	14, 218, 15, 19, 16, 17	⊢
	: , : , : , :
10	instantiation	18, 183	⊢
	:
11	instantiation	176, 177, 218, 215, 178, 179, 182, 193	⊢
	: , : , : , : , : , :
12	instantiation	59, 215, 218, 177, 19, 178, 182, 193, 44*	⊢
	: , : , : , : , : , :
13	instantiation	141, 20, 21	,  ⊢
	: , : , :
14	axiom		⊢
	proveit.core_expr_types.operations.operands_substitution
15	instantiation	191	⊢
	: , :
16	instantiation	22, 212	⊢
	: , :
17	instantiation	173, 23, 24	⊢
	: , : , :
18	axiom		⊢
	proveit.logic.booleans.eq_true_intro
19	instantiation	191	⊢
	: , :
20	instantiation	141, 25, 26	,  ⊢
	: , : , :
21	instantiation	76, 77, 27, 200, 138	⊢
	: , : , :
22	axiom		⊢
	proveit.numbers.summation.sum_single
23	instantiation	188, 28	⊢
	: , : , :
24	instantiation	29, 200, 138	⊢
	:
25	instantiation	30, 31, 32	,  ⊢
	: , : , :
26	instantiation	144, 33, 34, 35	⊢
	: , : , : , :
27	instantiation	103, 182, 200	⊢
	: , :
28	instantiation	173, 36, 172	⊢
	: , : , :
29	conjecture		⊢
	proveit.numbers.division.frac_cancel_complete
30	theorem		⊢
	proveit.logic.equality.sub_left_side_into
31	instantiation	141, 37, 38	,  ⊢
	: , : , :
32	instantiation	173, 39, 40	⊢
	: , : , :
33	instantiation	188, 41	⊢
	: , : , :
34	instantiation	188, 42	⊢
	: , : , :
35	instantiation	65, 43	⊢
	: , :
36	instantiation	188, 44	⊢
	: , : , :
37	instantiation	141, 45, 46	⊢
	: , : , :
38	assumption		⊢
39	instantiation	188, 47	⊢
	: , : , :
40	instantiation	48, 86, 200, 138, 49*	⊢
	: , :
41	instantiation	173, 50, 51	⊢
	: , : , :
42	instantiation	173, 52, 53	⊢
	: , : , :
43	instantiation	87, 215, 218, 177, 54, 178, 55, 182, 200	⊢
	: , : , : , : , : , :
44	conjecture		⊢
	proveit.numbers.numerals.decimals.add_1_1
45	instantiation	56, 212, 122, 57, 58*	⊢
	: , : , : , :
46	instantiation	59, 215, 218, 177, 179, 178, 82, 182, 193	⊢
	: , : , : , : , : , :
47	instantiation	87, 215, 218, 177, 179, 178, 200, 182, 193	⊢
	: , : , : , : , : , :
48	conjecture		⊢
	proveit.numbers.division.div_as_mult
49	instantiation	173, 60, 61	⊢
	: , : , :
50	instantiation	188, 62	⊢
	: , : , :
51	instantiation	65, 63	⊢
	: , :
52	instantiation	188, 64	⊢
	: , : , :
53	instantiation	65, 66	⊢
	: , :
54	instantiation	191	⊢
	: , :
55	instantiation	137, 77, 200, 138	⊢
	: , :
56	axiom		⊢
	proveit.numbers.summation.sum_split_last
57	instantiation	67, 201, 68, 194, 69, 70*	⊢
	: , : , :
58	instantiation	173, 71, 72	⊢
	: , : , :
59	conjecture		⊢
	proveit.numbers.addition.association
60	instantiation	188, 73	⊢
	: , : , :
61	instantiation	173, 74, 75	⊢
	: , : , :
62	instantiation	85, 182, 77	⊢
	: , :
63	instantiation	76, 77, 182, 200, 138	⊢
	: , : , :
64	instantiation	85, 200, 77	⊢
	: , :
65	theorem		⊢
	proveit.logic.equality.equals_reversal
66	instantiation	76, 77, 200, 138	⊢
	: , : , :
67	conjecture		⊢
	proveit.numbers.addition.strong_bound_via_left_term_bound
68	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.zero_is_real
69	instantiation	78, 204	⊢
	:
70	instantiation	141, 79, 80	⊢
	: , : , :
71	instantiation	188, 81	⊢
	: , : , :
72	instantiation	176, 215, 218, 177, 179, 178, 82, 182, 193	⊢
	: , : , : , : , : , :
73	instantiation	83, 154, 196, 84*	⊢
	: , :
74	instantiation	85, 86, 130	⊢
	: , :
75	instantiation	87, 215, 218, 177, 88, 178, 130, 104, 105, 89*, 90*	⊢
	: , : , : , : , : , :
76	conjecture		⊢
	proveit.numbers.division.mult_frac_left
77	instantiation	216, 205, 91	⊢
	: , : , :
78	conjecture		⊢
	proveit.numbers.number_sets.natural_numbers.natural_pos_is_pos
79	instantiation	92, 193	⊢
	:
80	instantiation	93, 193, 94	⊢
	: , :
81	instantiation	95, 198, 96, 97, 98, 99	⊢
	: , : , :
82	modus ponens	100, 101	⊢
83	conjecture		⊢
	proveit.numbers.exponentiation.neg_power_as_div
84	instantiation	102, 200	⊢
	:
85	conjecture		⊢
	proveit.numbers.multiplication.commutation
86	instantiation	103, 104, 105	⊢
	: , :
87	conjecture		⊢
	proveit.numbers.multiplication.distribute_through_sum
88	instantiation	191	⊢
	: , :
89	instantiation	144, 106, 107, 108	⊢
	: , : , : , :
90	instantiation	173, 109, 110	⊢
	: , : , :
91	instantiation	216, 210, 111	⊢
	: , : , :
92	conjecture		⊢
	proveit.numbers.addition.elim_zero_right
93	conjecture		⊢
	proveit.numbers.addition.commutation
94	conjecture		⊢
	proveit.numbers.number_sets.complex_numbers.zero_is_complex
95	conjecture		⊢
	proveit.core_expr_types.tuples.tuple_eq_via_elem_eq
96	instantiation	191	⊢
	: , :
97	instantiation	191	⊢
	: , :
98	instantiation	188, 112	⊢
	: , : , :
99	instantiation	195	⊢
	:
100	instantiation	113	⊢
	: , : , :
101	generalization	114	⊢
102	conjecture		⊢
	proveit.numbers.exponentiation.complex_x_to_first_power_is_x
103	conjecture		⊢
	proveit.numbers.addition.add_complex_closure_bin
104	instantiation	115, 200, 182	⊢
	: , :
105	instantiation	115, 200, 193	⊢
	: , :
106	instantiation	119, 215, 218, 177, 116, 178, 130, 200, 182	⊢
	: , : , : , : , : , :
107	instantiation	173, 117, 118	⊢
	: , : , :
108	instantiation	187, 182	⊢
	:
109	instantiation	119, 215, 218, 177, 120, 178, 130, 200, 193	⊢
	: , : , : , : , : , :
110	instantiation	173, 121, 127	⊢
	: , : , :
111	instantiation	216, 213, 122	⊢
	: , : , :
112	modus ponens	123, 124	⊢
113	conjecture		⊢
	proveit.numbers.summation.summation_complex_closure
114	instantiation	216, 205, 125	,  ⊢
	: , : , :
115	conjecture		⊢
	proveit.numbers.multiplication.mult_complex_closure_bin
116	instantiation	191	⊢
	: , :
117	instantiation	126, 177, 218, 215, 178, 129, 130, 200, 182	⊢
	: , : , : , : , : , :
118	instantiation	188, 127	⊢
	: , : , :
119	conjecture		⊢
	proveit.numbers.multiplication.disassociation
120	instantiation	191	⊢
	: , :
121	instantiation	128, 218, 177, 129, 178, 130, 200	⊢
	: , : , : , :
122	instantiation	131, 160, 212	⊢
	: , :
123	instantiation	132, 196	⊢
	: , : , : , : , : , :
124	generalization	133	⊢
125	instantiation	216, 210, 134	,  ⊢
	: , : , :
126	conjecture		⊢
	proveit.numbers.multiplication.association
127	instantiation	141, 135, 136	⊢
	: , : , :
128	conjecture		⊢
	proveit.numbers.multiplication.elim_one_any
129	instantiation	191	⊢
	: , :
130	instantiation	137, 193, 200, 138	⊢
	: , :
131	conjecture		⊢
	proveit.numbers.addition.add_int_closure_bin
132	axiom		⊢
	proveit.core_expr_types.lambda_maps.lambda_substitution
133	instantiation	188, 139	⊢
	: , : , :
134	instantiation	216, 213, 140	,  ⊢
	: , : , :
135	instantiation	141, 142, 143	⊢
	: , : , :
136	instantiation	144, 145, 146, 147	⊢
	: , : , : , :
137	conjecture		⊢
	proveit.numbers.division.div_complex_closure
138	instantiation	148, 198	⊢
	:
139	instantiation	188, 149	⊢
	: , : , :
140	instantiation	216, 150, 151	,  ⊢
	: , : , :
141	theorem		⊢
	proveit.logic.equality.sub_right_side_into
142	instantiation	152, 193, 153, 154	⊢
	: , : , : , : , :
143	instantiation	173, 155, 156	⊢
	: , : , :
144	conjecture		⊢
	proveit.logic.equality.four_chain_transitivity
145	instantiation	188, 157	⊢
	: , : , :
146	instantiation	188, 157	⊢
	: , : , :
147	instantiation	199, 193	⊢
	:
148	conjecture		⊢
	proveit.numbers.number_sets.natural_numbers.nonzero_if_is_nat_pos
149	instantiation	188, 158	⊢
	: , : , :
150	instantiation	159, 212, 160	⊢
	: , :
151	assumption		⊢
152	conjecture		⊢
	proveit.numbers.division.mult_frac_cancel_denom_left
153	instantiation	216, 162, 161	⊢
	: , : , :
154	instantiation	216, 162, 163	⊢
	: , : , :
155	instantiation	188, 164	⊢
	: , : , :
156	instantiation	188, 165	⊢
	: , : , :
157	instantiation	190, 193	⊢
	:
158	instantiation	173, 166, 167	⊢
	: , : , :
159	conjecture		⊢
	proveit.numbers.number_sets.integers.int_interval_within_int
160	instantiation	216, 168, 204	⊢
	: , : , :
161	instantiation	216, 170, 169	⊢
	: , : , :
162	conjecture		⊢
	proveit.numbers.number_sets.complex_numbers.real_nonzero_within_complex_nonzero
163	instantiation	216, 170, 171	⊢
	: , : , :
164	instantiation	188, 172	⊢
	: , : , :
165	instantiation	173, 174, 175	⊢
	: , : , :
166	instantiation	176, 177, 218, 215, 178, 179, 182, 193, 180	⊢
	: , : , : , : , : , :
167	instantiation	181, 193, 182, 183	⊢
	: , : , :
168	conjecture		⊢
	proveit.numbers.number_sets.integers.nat_pos_within_int
169	instantiation	216, 185, 184	⊢
	: , : , :
170	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.rational_nonzero_within_real_nonzero
171	instantiation	216, 185, 186	⊢
	: , : , :
172	instantiation	187, 200	⊢
	:
173	axiom		⊢
	proveit.logic.equality.equals_transitivity
174	instantiation	188, 189	⊢
	: , : , :
175	instantiation	190, 200	⊢
	:
176	conjecture		⊢
	proveit.numbers.addition.disassociation
177	axiom		⊢
	proveit.numbers.number_sets.natural_numbers.zero_in_nats
178	conjecture		⊢
	proveit.core_expr_types.tuples.tuple_len_0_typical_eq
179	instantiation	191	⊢
	: , :
180	instantiation	192, 193	⊢
	:
181	conjecture		⊢
	proveit.numbers.addition.subtraction.add_cancel_triple_23
182	instantiation	216, 205, 194	⊢
	: , : , :
183	instantiation	195	⊢
	:
184	instantiation	216, 197, 196	⊢
	: , : , :
185	conjecture		⊢
	proveit.numbers.number_sets.rational_numbers.nonzero_int_within_rational_nonzero
186	instantiation	216, 197, 198	⊢
	: , : , :
187	conjecture		⊢
	proveit.numbers.multiplication.elim_one_left
188	axiom		⊢
	proveit.logic.equality.substitution
189	instantiation	199, 200	⊢
	:
190	conjecture		⊢
	proveit.numbers.division.frac_one_denom
191	conjecture		⊢
	proveit.numbers.numerals.decimals.tuple_len_2_typical_eq
192	conjecture		⊢
	proveit.numbers.negation.complex_closure
193	instantiation	216, 205, 201	⊢
	: , : , :
194	instantiation	202, 203, 204	⊢
	: , : , :
195	axiom		⊢
	proveit.logic.equality.equals_reflexivity
196	conjecture		⊢
	proveit.numbers.numerals.decimals.posnat1
197	conjecture		⊢
	proveit.numbers.number_sets.integers.nat_pos_within_nonzero_int
198	conjecture		⊢
	proveit.numbers.numerals.decimals.posnat2
199	conjecture		⊢
	proveit.numbers.multiplication.elim_one_right
200	instantiation	216, 205, 206	⊢
	: , : , :
201	instantiation	216, 210, 207	⊢
	: , : , :
202	theorem		⊢
	proveit.logic.sets.inclusion.unfold_subset_eq
203	instantiation	208, 209	⊢
	: , :
204	assumption		⊢
205	conjecture		⊢
	proveit.numbers.number_sets.complex_numbers.real_within_complex
206	instantiation	216, 210, 211	⊢
	: , : , :
207	instantiation	216, 213, 212	⊢
	: , : , :
208	theorem		⊢
	proveit.logic.sets.inclusion.relax_proper_subset
209	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.nat_pos_within_real
210	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.rational_within_real
211	instantiation	216, 213, 214	⊢
	: , : , :
212	instantiation	216, 217, 215	⊢
	: , : , :
213	conjecture		⊢
	proveit.numbers.number_sets.rational_numbers.int_within_rational
214	instantiation	216, 217, 218	⊢
	: , : , :
215	theorem		⊢
	proveit.numbers.numerals.decimals.nat1
216	theorem		⊢
	proveit.logic.sets.inclusion.superset_membership_from_proper_subset
217	conjecture		⊢
	proveit.numbers.number_sets.integers.nat_within_int
218	conjecture		⊢
	proveit.numbers.numerals.decimals.nat2
*equality replacement requirements