Proof by induction

Question 1

How to prove that a number is even:

Answer 1

Take out a common factor of 2

Question 2

How to prove that a number is odd

Answer 2

Take out a common factor of 2 and have a remainder of 1

Question 3

3 steps for proof by induction

Answer 3

Prove true for one value (usually n=1)
Assume true for n=k
By using step 2 to simplify, show that the statement holds for n=k+1.

Question 4

Conclusion for proof by induction

Answer 4

Having assumed the statement true for n=k, the statement has been proven for n=k+1. Since it’s true for n=1 then it’s true for all values of n by mathematical induction.

Question 5

Proof by induction step 1

Answer 5

Split into LHS and RHS, substitute in n=1.
Prove true and state LHS = RHS for n=1

Question 6

Proof by induction step 2

Answer 6

Assume true for n=k, so sub in k.

Question 7

Proof by induction step 3

Answer 7

First work out goal by subbing in n=k+1 for n=k in assumption, this is what we want reach.
Use our assumed value for n=k and work through algebra until we reach our goal. Then state conclusion.

Question 8

How to substitute in n=k for n=k+1 equation in summation notation

Answer 8

(U)k+1(L)1 Σ =(U)k (L)1 Σ + (U)k+1 (L) k+1
Then sub in assumed value for n=k Σ

Question 9

How to use proof by induction to show that a number is always divisible by m

Answer 9

Work through proof by induction steps then for n=k+1 take out m as a common factor. As such it is always divisible by that.