Q:
Consider the following recursively-de ned function:
\forall n \in N G(n) = 1, if n = 0
3G(n - 1) + 1, if n > 0
Gain some insight into G(n) through unwinding (also called repeated substitution). Make a conjecture about a closed-form for G(n), and then prove your conjecture.
1. UNDERSTANDING THE PROBLEM
First. Given the definition of G(n) for some natural number n, my tasks are
1) finding a closed-form for G(n) using unwinding
2) constructing a conjecture about (1)
3) proving (2)
2. DEVISING A PLAN
Second. Find the connection between G(n) and the closed-form of G(n). I am instructed to apply unwinding in the question. Thus, the closed-form of G(n) should be driven from the repeated substitution. Once I succeed in obtaining the closed-form of G(n), make a conjecture regarding G(n) and its closed form. I have seen similar questions before asking for a conjecture as well. In this type of question, a conjecture can be constructed by comparing the data and the unknown or by indicating the upper/lower bound of the unknown. In this case, it is very likely to a relation such as G(n) = closed-form of G(n).
3. CARRYING OUT THE PLAN
Third.
1) Unwinding G(n):
Third.
1) Unwinding G(n):
G(n) = 3G(n - 1) + 1
= 3[3G(n - 2) + 1] + 1 = 9G(n - 2) + 3 + 1
= 9[3G(n - 3) + 1] + 3 + 1 = 27G(n - 3) + 9 + 3 + 1
= 27[3G(n - 4) + 1] + 9 + 3 + 1 = 81G(n - 4) + 27 + 9 + 3 + 1
= [make a guess] 3^n + 3^(n - 1) + ... + 3^0
= (3^(n + 1) - 1) / 2
2) P(n): G(n) = (3^(n + 1) - 1) / 2
3) Claim: \forall n \in N, P(n)
Proof by simple induction
Base Case
When n = 0, G(0) = 1 [by the definition of G(n)] and (3^(0 + 1) - 1) / 2 = 1 as well.
Thus, P(0) is true.
Induction Step
Assume n \in N. Also assume that P(n) is true. So G(n) = (3^(n + 1) - 1) / 2. Then,
G(n + 1) = 3G(n + 1 - 1) + 1
= 3G(n) + 1
= 3[(3^(n + 1) - 1) / 2] + 1 # by IH
= [3(3^(n + 1)) - 3] / 2 + (2 / 2)
= (3^(n + 2) - 3 + 2) / 2
= (3^(n + 2) - 1) / 2
= (3^((n + 1) + 1) - 1) / 2
Therefore P(n) => P(n + 1). Conclude \forall n \in N, P(n).
4. LOOKING BACK
Fourth. Check the result.
G(1) = 3G(0) + 1 = 4 = (3^(2) - 1) / 2
G(2) = 3G(1) + 1 = 13 = (3^(3) - 1) / 2
G(3) = 3G(2) + 1 = 40 = (3^(4) - 1) / 2
G(4) = 3G(3) + 1 = 121 = (3^(5) - 1) / 2
G(5) = 3G(4) + 1 = 364 = (3^(6) - 1) / 2
