6 - proof by induction

Question 1

4 steps

Answer 1

• basis - prove its true for n = 1 / smallest n
• assumption - assume its true for n = k
• inductive - show its true for n = k + 1
• conclusion

Question 2

conclusion

Answer 2

if true for n = k then true for n = k + 1
as its true for n = 1 then by mathematical induction it (insert q) is true ∀ n ∈ ℤ+ (for all positive integer values of n)

Question 3

matrices proof eg prove Mⁿ = ( )

Answer 3

n = 1 solve LHS solve RHS
n = k state assumption
n = k + 1 - M^(k+1) split into M^k M - sub in your assumed value for M^k and solve to get it in the form of k + 1

Question 4

matrices proof eg prove (1 -1)ⁿ = (1 1-2ⁿ
.(0 2) 0 2ⁿ )

Answer 4

n = 1 LHS = (1 -1)ⁿ RHS = (1 1-2
.(0 2) 0 2 )
LHS = RHS
assume (1 -1)^k = (1 1-2^k
.(0 2) 0 2^k )
n = k +1 (1 -1)^k + 1= (1 1-2^k)(1 -1)
.(0 2) (0 2^k ) (0 2)
= (1 1-2^k+1
0 2^k+1)
conc

Question 5

divisibility proof eg prove n (an eq containing n) is divisible by x

Answer 5

let f(n) = the equation
f(1) solve and show its divisible by x
assume f(k) is divisible by x
f(k+1) split up to get f(k) + x(something)
- since f(k) is divisible by x and so is x() f(k+1) is divisible by x
- conc

Question 6

divisibility proof eg prove 3²ⁿ + 11 is /4

Answer 6

f(n) = 3²ⁿ + 11
f(1) = 3² + 11 = 20 20/4 = 5
assume f(k) is /4
f(k+1) = 3^2(k+1) + 11
= 3^2 (3^2k) + 11
= 9(3^2k) + 11
= 8(3^2k) + 3^2k +11
= 4(2(3^2k)) + f(k)
so /4
conc

Question 7

inequality proof eg y > x

Answer 7

n = 1 show LHS is > RHS by subbing in 1
assume n = k is true
n = k+1 sub in k + 1 to y split any powers of factorial - use your assumption - play around until you get its > x
conc

Question 8

inequality proof eg prove 3ⁿ > n

Answer 8

n = 1 3>1
n = k assume 3^k > k
n = k+1 3^(k+1) = 3(3^k) > 3k > 2k = k + k > k + 1 (as k>=1)