Proofs

Question 1

Proof by Induction

Answer 1

1. Base Case: Prove a base case is true P(1)
2. Inductive Hypothesis: suppose the claim holds from Base Case to n=k
3. Inductive Step: we want to prove P(k+1)
   …
   So, the claim holds for n=k+1
   Thus, by induction, the claim is true for all n >= base case

Question 2

Proof by Contradiction

Answer 2

Claim
Proof by contradiction: suppose the contrary is true
Show how it leads to a contradiction
Thus the claim holds