Proof Notebook
Discrete Mathematics, Dr. Jason Smith
William Coltyn Levi Weston
12-9-2019
Homework 05.1
Coltyn Weston
September 25th 2019
Fact. Prove that 4+9+14+· · · + (5n−1) = n
2(3 + 5n)for n≥1.
Proof. Base Case [n= 1]
5(1) −1=4
1
2(8) = 4
4 = 4 for n= 1
Inductive Hypothesis: For some k≥1 we have 4 + 9 + 14 + · · · + (5k−1) =
k
2(3 + 5k)
Inductive Step:
4+9+14+· · · + (5n−1) + (5k+ 4) = k
2(3 + 5k) + (5k+ 4)
k
2(3 + 5k) + (5k+ 4) = 1
2(k+ 1)(5k+ 8)
1
2(k+ 1)(5k+ 8) = 1
2(k+ 1)(5k+ 8)
We can thus prove that the fact is true for the k+ 1 term.
1
Homework 05.2
Coltyn Weston
October 1st 2019
Fact. Prove that 4+9+14+· · · + (5n−1) = n
2(3 + 5n)for n≥1.
Proof. Base Case [n= 1]
5(1) −1=4
1
2(8) = 4
4 = 4 for n= 1
Inductive Hypothesis: For some k≥1 we have 4 + 9 + 14 + · · · + (5k−1) =
k
2(3 + 5k)
Inductive Step:
4+9+14+· · · + (5k−1) + (5k+ 4) = k+1
2(3 + 5(k+ 1))
k
2(3 + 5k) + (5k+ 4) = k+1
2(3 + 5(k+ 1))
1
2(5k2+ 13k+ 8) = k+1
2(3 + 5(k+ 1))
1
2(5k2+ 13k+ 8) = 1
2(k+ 1) + (5k+ 8)
1
2(5k2+ 13k+ 8) = 1
2(5k2+ 13k+ 8)
We can thus prove that the fact is true for the k+ 1 term.
1
Homework 05.3
Coltyn Weston
October 9th 2019
Fact. Prove that 4+9+14+· · · + (5n−1) = n
2(3 + 5n)for n≥1.
Proof. Base Case [n= 1]
5(1) −1=4
1
2(8) = 4
4 = 4 for n= 1
Inductive Hypothesis: For some k≥1 we have 4 + 9 + 14 + · · · + (5k−1) =
k
2(3 + 5k)
Inductive Step: starting with the left side
4+9+14+· · · + (5k−1) + (5k+ 4)
k
2(3 + 5k) + (5k+ 4)
1
2(5k2+ 13k+ 8)
Thus the right side
k+1
2(3 + 5(k+ 1))
1
2(k+ 1) + (5k+ 8)
1
2(5k2+ 13k+ 8)
Combined this yields 1
2(5k2+ 13k+ 8) = 1
2(5k2+ 13k+ 8). We can thus
prove that the fact is true for the k+ 1 term.
1
Textbook Proof 5.4
Coltyn Weston
October 9th 2019
Fact. Prove that 4+9+14+· · · + (5n−1) = n
2(3 + 5n)for n≥1.
Proof. Base Case [n= 1]
5(1) −1=4
1
2(8) = 4
4 = 4 for n= 1
Inductive Hypothesis: For some k≥1 we have 4 + 9 + 14 + · · · + (5k−1) =
k
2(3 + 5k)
Inductive Step:
LHS: 4 + 9 + 14 + · · · + (5k−1) + (5k+ 4)
LHS: k
2(3 + 5k) + (5k+ 4)
LHS: 1
2(5k2+ 13k+ 8)
RHS: k+1
2(3 + 5(k+ 1))
RHS: 1
2(k+ 1) + (5k+ 8)
RHS: 1
2(5k2+ 13k+ 8)
Combined this yields 1
2(5k2+ 13k+ 8) = 1
2(5k2+ 13k+ 8). We can thus
prove that the fact is true for the k+ 1 term.
1
Homework 06.1
Coltyn Weston
September 27th 2019
Fact. For n≥1,(1 + x)n≥1 + xn
Proof. Base Case[N= 1]
(1 + x)1≥1+1x
Inductive Hypothesis: Assume that k≥1, (1 + x)k≥1 + xk
Inductive Step: (1 + x)k+1 ≥1+(k+ 1)x
Right Side:(1 + kx)(1 + x)
Right Side: kx2+kx +x+ 1
(1 + x)k+1 ≥1+(k+ 1)x+kx2
(1 + x)k+1 = 1 + (k+ 1)x
The addition of kx2ensures that the right side is greater, thus proving our
fact.
1
Homework 06.2
Coltyn Weston
October 3rd 2019
Fact. For n≥1,(1 + x)n≥1 + xn
Proof. Base Case[n= 1]
(1 + x)1≥1+1x
Inductive Hypothesis: Assume that k≥1, (1 + x)k≥1 + xk
