Y1, C8 - Proof by Induction

Question 1

What are the steps for a general proof by induction

Answer 1

1) Base case- n = 1 and solve
2) Assumption- n = k and assume correct
3) Inductive case- n = k + 1
4) Conclusion- Write sentence proving is it true

Question 2

What should the conclusion step say

Answer 2

Since true for n = 1 and if true for n = k, true for n = k + 1. Therefore true for all n

Question 3

How do you do summation proof

Answer 3

1) Write out LHS and RHS for n = 1 and show they are equal
2) Write out LHS and RHS for n = k and assume true
3) Write out LHS and RHS for n = k + 1, splitting the summation from r = 1 to k and then adding the function of (k + 1)
4) Sub in your known value of the sum of n = 1 to k and solve
5) LHS should then equal RHS for n = k + 1
6) Conclusion step

Question 4

How would you split the sum of (2r - 1) from n = 1 to k +1

Answer 4

(The sum of (2r - 1) from n = 1 to k) + (2(k+1) - 1)

Question 5

How to sub in n = k + 1 for a summation

Answer 5

Split the summation into form r = 1 to n = k + (the function of (k + 1))

Question 6

How to solve divisibility proof by inductions

Answer 6

1) Solve for n = 1
2) Assume n = k
3) f(k + 1) - f(k)
Simplify
Get into form polynomial + f(k) = f(k + 1) where the polynomial is divisible by the required integer
4) Polynomial is divisible and we know f(k) is divisible therefore true for all +ve integers

Question 7

Prove by induction that n^3 - 7n + 9 is divisible by 3 for all positive integers n

Answer 7

1) n = 1 –> 1 - 7 + 9 = 3
2) n = k –> k^3 - 7k + 9 assume divisible by 3
3) n = k + 1 –> (k + 1)^3 - 7(k + 1) + 9
–> k^3 + 3k^2 + 3k + 3
f(k+1) - f(k) = k^3 + 3k^2 + 3k + 3 - (k^3 - 7k + 9) = 3k^2 + 3k + 6
Therefore f(k+1) - f(k) = 3(k^2 + k + 2) and so f(k+1) = 3(k^2 + k + 2) + f(k) which is all divisible by 3

Question 8

Prove by induction that 8^n - 3^n is divisible by 5

Answer 8

1) n = 1
2) n = k –> 8^k - 3^k
3) f(k+1) - f(k) –> 8^k+1 - 3^k+1 - (8^k - 3^k)
8 * 8^k - 3 * 3k - 8^k + 3^k
7 * 8^k - 23^k
= 5 * 8^k - 23^k + 2 * 8^k
= 5 * 8^k + 2(8^k - 3^k)
Therefore f(k+1) - f(k) = 58^k + 2f(k)
And so f(k+1) = 5*8^k + 3f(k) which is all divisible by 5

Question 9

How do you do matrix proofs by induction

Answer 9

1) n = 1
2) Assume n = k for LHS = RHS
3) n = k+1, write out LHS and RHS (aim)
4) Split the matrix to have it in the form matrix^n + matrix
5) Sub in known result for M^k and multiply the matrices so they equal the RHS (aim)
6) Conclusion

Question 10

Which type of proof by induction isn’t in the specification

Answer 10

Recurrence relation proofs

Question 11

How do you do recurrence relation proofs (1 assumption)

Answer 11

1) n = 1
2) n = k, write out LHS and RHS
3) n = k+1, write out LHS and RHS (aim)
4) Sub in u(k) into formula for u(k+1) and solve through so LHS = RHS (aim)
5) Conclusion

Question 12

How do you do recurrence relation proofs (2 assumptions)

Answer 12

1) n = 1, check true
2) n = 2, check true
3) n = k, write out LHS and RHS and assume true
4) n = k+1, write out LHS and RHS and assume true
5) n = k+2, write out LHS and RHS (aim)
6) Sub in u(k) and u(k+1) into formula for u(k+2) and solve through so it equals RHS (aim)
7) Conclusion

Question 13

How would you write 3^k+1 in the form of k * 3^k-2 where k is a constant

Answer 13

k = 27
27 * 3^k-2 = 3^k+1