My way of doing recursion problems

Usually, you always need to think more about recursion problems than induction problems.
The reason is: for induction problems you always consider the nth case (or first to nth)to imply NO.(n+1) case.But for recursion, you have to think from nth case all the way down the first case and then prove it by induction.

Use repeated substitution (unwinding) to find a closed form for the recurrence S when n is a power of 3:
          1 if n < 3
S(n) = {
          a1*S(ceiling[n/3])+ a2*S(floor[n/3])+sqr(n) if n>2
... where integers a1,a2≥0 and a1 + a2 = 3.

The question gives the condition of n always related to other factors.
You can find n is a power of 3 and ceiling[n/3] floor[n/3]
Since n is a power of 3 which means n=3^^k.
Then try to substitute n=3^^k into S(n) when n>2.
Because n is a power of 3,ceiling[n/3]=floor[n/3]=3^^k-1
Then S(n)=3S(n/3)+n^^2 which is 3S(3^^k-1)+n^^2

substitute again then will be able to find S(n)=9S(n/9)+n^^2/3+n^^2

keep substituting until get S(n)=n+3/2n(n-1)

then prove it by induction.

The key point is to find the realtionship between S(n) S(n/k) S(n/k^^2)....and at the end S(1)