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.