Proof by Induction

Question 1

Steps

Answer 1

Basis - prove true for n=1
Assumption- assume true for n=k
Induction- Show the statement is then true for n=k+1
Conclusion- The statement is true for all integers n

Question 2

Basis

Answer 2

Substitute 1 into the LHS and RHS. Prove equal

“Therefore true for n=1”

Question 3

Assumption

Answer 3

Write out the statement with k instead of n

“Assume true for n=k”

Question 4

Series Induction

Answer 4

Sum the answer for k with k+1 substituted in place of r and write the output
Work out what your output should be first and write in a separate

Question 5

Conclusion

Answer 5

Since true for n=1 and if true for n=k, true for n=k+1

Therefore true for all n

Question 6

How to prove a divisibility

Answer 6

Prove it is a multiple of the factor

Question 7

Divisibility proofs

Answer 7

Find f(k+1) and write it as a multiple of f(k) plus y, so that y is a multiple of the factor you are proving
Remember to write f(k) instead of the numbers

Question 8

What if you have it to the power of k+1 but it is to the power of k-1 in f(k)

Answer 8

Multiply by the base squared and both will be in terms of k-1

Question 9

Matrix proofs

Answer 9

Substitute 1 into the LHS and RHS and show equal

Multiply the RHS by the original for M^k+1

Question 10

Raising a matrix by a power

Answer 10

Raise every value in the matrix by that power

Question 11

2(2^k)

Answer 11

2^k+1