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)

Welcome!

Hello TAs and fellow students,
Welcome to my first SLOG (or second one, first one was mistakenly created on the other site). I hope everyone's doing ok about the first midterm. I personally found it challenging yet rewarding if you did put effort in studying. I enjoy this course so far and hopefully will be for the rest of this term. Stay tuned , peace out!