Term Test 1 Question 3

Hello fellows, today I'm going to tackle the question regarding structural induction. It is just something that I couldn't put my finger on at the first glance. I found this hard at the term test 1 so I'll take a few step down to look at the structural induction

So here's an explanation I found in the course notes:
Provided a recursive definition of a set, we naturally use structural induction to prove properties of its elements by using induction.
Suppose X is a defined set using induction and we want to prove that every element of X has a certain property P. A proof by structural induction proceeds in two steps.

Basis: We prove that every "smallest" or "simplest" element of X satisfy property P

Induction Step: We also prove that the larger elements that are made of these"smallest" or "simplest" elements satisfy property P

I didn't get the third question of term test 1 right so I'll take a few step to look into it.

Here's the question:
Define epsilon as the smallest set such that
1. Symbols x,y,z are elements of epsilon.
2. If expressions e1 and e2 are elements of epsilon, then so is (e1 + e2)
For e in epsilon, define vr(e) as the number of occurrences of symbols from the set {x,y,z} in e, and p(e) as the number o occurrences of parentheses from the set  {(,)} in e. For example, vr(((x+y)+z)) = 3 and p(((x+y)+z) = 4. Use Structural Induction to prove that for every e in epsilon, 2vr(e) = p(e) + 2

So as all induction proof, we start by defining the predicate: P(e): "2vr(e) = p(e) + 2"

First step would be looking for the basis

Basis: e in {x,y,z}: Each of these expressions has exactly one variable and 0 parentheses, so according to P(e) we have 2 * 1 = 0 + 2 = 2, so we know P(e) holds for e in the basis.

Secondly we show the induction step

Induction: Assume e1 and e2 are in epsilon and P(e1), P(e2)  [P(e1) and P(e2) have to hold in order to prove P((e1 + e2))

So 2vr((e1 + e2) =  2(vr(e1) + vr(e2))    #just rearrange it
                           =  2vr(e1) + 2vr(e2)
                           =  p(e1) + 2 + p(e2) + 2  #left hand side of the equation 2vr(e) = p(e) + 2
                           =  (p(e1) + p(e2) + 2) + 2
                           = p(e1 + e2) + 2  # because only two parentheses needed to wrap (e1 + e2)

So, for all e1 and e2 in epsilon, P(e1) and P(e2) implies P((e1 + e2)) by structural induction.

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)