Term Test 1 Question 1

Term Test #1,

Hello, today I'm going to go over the question 1 that baffled me in the first midterm:

1) Use Mathematical Induction to prove that for every natural number n, 13^n - 1 is a multiple of 12.

So this proof is about 1 of the 3 induction we've learned so far. As always we define our predicate P(n) first.

P(n): there exist an integer number z such that 13^n - 1 = 12z

Then we set the base case out.

Base Case:       If n = 0, then 13^n - 1 = 12z = 12*0    [Since z can be any integer]

                        Then we can show that the base case satisfy P(n)

                        So P(0) is true

Then here comes to our induction step.

Induction Step: Assume P(n), we want to prove P(n+1)

           

                        13^(n+1) - 1    =            13(13^n) - 1

                                                =             13((13^n) - 1) + 12             (still retain -1 at the end)

                                                =             13(12z) + 12                         (definition of P(n))

                                                =            12(13z + 1)                        (rearrange it)

                                                =             12 z'                                     (13z + 1 is an integer)

Since we assume n was an arbitrary natural number and P(n), and we derived P(n+1) from it so we can conclude for all natural number n, P(n)