First (and last?) problem solving episode

so school is about to end in less than 2 weeks, yay, at the same time test 3 is next week, followed by the exam itself the next next week, and i have to write a problem solving episode to at least get full credits for this, booo. now all ranting aside,

i suppose i'll prove ∀ n ∈ ℕ, Me > n. haha now all jokes aside, i guess i'll do this episode on problem set #3. So using Polya's steps, i have to make a conjecture about a closed form for G(n) and prove my conjecture given that

∀ n ∈ ℕ, G(n) = { 1, if n = 0 and 3G(n-1) + 1, if n > 0

Step 1: Understand the problem
So here we have to find a close form for G(n), make a statement for our claim, and then prove the claim.

Step 2: Devising a plan.
1) we will have to unwind G(n) and see how the values may have a pattern. so set n as a not too small, but not too large number, and we find the value for G(n) for each n.
2) Given we have found a pattern for the values, we will have to rewrite it in the closed form of G(n).
3) now with the closed form we will actually prove the closed form is correct. Given the closed form does not rely on previous values of G, simple induction should suffice.

Step 3: Carry out the plan
1) so we unwind G(n) now say when n = 5, so
G(0) = 1
G(1) = 3G(0) + 1 = 3(1) + 1 = 4
G(2) = 3G(1) + 1 = 3(4) + 1 = 13
G(3) = 3G(2) + 1 = 3(13) + 1 = 40
G(4) = 3G(3) + 1 = 3(40) + 1 = 121
G(5) = 3G(4) + 1 = 3(121) + 1 = 364

2) looking at this, we see a pattern where to find G(n+1) we add 3^n+1 to G(n), so we can say G(n) = \sum i=0 to n, 3^i, but since we need a closed form expression, thus we must rewrite the equation in another way.

From above we know G(n+1) = G(n) + 3^(n+1), and from the definition of G(n), we know G(n+1) = 3G(n) + 1, thus equation both expressions we get
G(n) + 3^(n+1) = 3G(n) + 1
3 G(n) - G(n) = 3^(n+1) - 1
G(n) (2) = 3^(n+1) - 1
G(n) = 3^(n+1)-1 / 2

3) so now proving this using simple induction, as always we start with a claim.

Claim: P(n) : ∀ n ∈ ℕ, G(n) = 3^(n+1)-1 / 2

Then we start with the base case.

Base Case: n = 0, G(0) = 3^(0+1) - 1 / 2 = 3 - 1 / 2 = 2 / 2 = 1, so P(0) is true.

Then we will state our induction hypothesis and induction step.
Induction Step:
Assume n is an arbitrary number, and that P(n) is true, i will prove that P(n) => P(n+1).

G(n+1) = 3G(n) + 1
= 3(3^(n+1)-1 / 2 ) + 1 // by IH
= 3(3^(n+1)-1/2) + 1
= 3^(n+2) - 1 / 2
= 3^((n+1)+1) - 1 /2 as required

∀ n ∈ ℕ, P(n) => P(n+1)

Step 4. Looking Back

then we have proven the close form of G(n) so we can conclude that ∀ n ∈ ℕ, P(n) is true.

Assignment 3

so our group started assignment 3 a while ago, looking at it, it was relatively easy to do. This seems easier than the past 2 assignments, question 1 was about loop termination, and loop invariants, it was a easy question as we've done it on test 2, and proving IH ^ precondition => post condition is easy.

Question 2 was about proving a Regular Expression denotes L, this was easy since there was an example in the lecture on how to prove it, we have to prove L is a subset of the RE, and the RE is a subset of L, otherwise RE does not denote L. although it is a bit messy with some of the parts since there's kleene stars everywhere, but i got through that question easily.

Question 3 was about proving that any regular expression that doesn't include a Kleene star denotes a finite language. we have a general idea on how to prove this, just need to write it down in complete sentences, we will be using the inductive definition of RE, and proving it by excluding the Kleene star, so all the languages even by concatentation should be finite.

Question 4 deals with DFSA and the carteisan product technique, and state invariants, our group have already derived the machine for that question, just takes a long time to write down all the states for the machine in words as opposed to a diagram.

i guess i will be doing my first problem solving episode huh since school's almost ending, 1 more week!! :D:D

A2 Handbacks, Test 2 and RegExp

Assignment 2 were marked and marks were handed back today, haha i was surprised when i first saw my mark, i thought i did a lot worse. But i suppose i did ok now

Test 2 is coming up this week, i think i won't have a problem with it since i pretty much know what i did for assignment 2 and the problem set 4, the only thing i might have to review is the master theorem and try to absorb what it is all about.

We did regular expressions this week, reg exp is ok for me since i know how to write and use them in programming, the only think awkward is the new symbols like + for ors(since + means 1 or more occurences in programming), and multiply to concatinate strings together, it is also awkward because now we try to prove some regular expressions, though i feel that i understand what is being said in lecture., so i guess it'll be pretty alright.

speaking of which i still have to write some problem solving episodes for this slog.