Q1. If you're counting the number of ternary trees with 3
nodes, you might organize your count as follows.  If the left-subtree
has zero nodes, how many possibilities are there for middle and right
subtrees?  How about if the left subtree has one node?  How about if
it has two?  Does this approach generalize to other cases?

Q2. By "Your expression should assign a constant..." we mean that
the recurrence relation will have constants that relates to parts 
of the code, like we saw in other examples. 

Q3. You don't necessarily want to get a closed form of G. Think about 
comparing two functions by by comparing their recurrence relations.

Q4. Theta notation. I thought you knew that, but anyway, f(n) = Theta(n) (or
sometime denoted as f(n) beloongs to Theta(n))means that   
c*n <= f(n) <= d*n, where c, d are some constants. For example 
   5n = Theta(n), n+6 = Theta(n), n + log n = Theta(n), but n^2 != Theta(n),
sqrt(n) != Theta(n), n/log n != Theta(n)

Another clarification. Notice that there are two conventions about indices for arrays.
(i)  the possible indices are 0,..., len(A)-1
(ii) the possible indices are 1,...,len(A)

In this question the second convention is chosen (notice also the "nonnegtie" includes 0). 
It is a minor technical point and should not really change the way a valid correctness proof should look.