Here is a question I've been working on and so far, can't get anything.
Suppose we have a string which is recursively defined as:
base case: A = F
recursive case: ( A N A )
such as a string X = ( ( F N ( F N F ) ) N ( ( ( F N F ) N F) N (F N F ) ) )
We have two functions used to calculate the amount of characters in the string. First, the function $f(a) = \left\{ \begin{array}{ll} 1 &\text{if }a=F;\\ f(a_1)+f(a_2) &\text{if }a=a_1\>N\>a_2. \end{array}\right.$ calculates the amounts of 'F' in the string.
Second, the function: $g(a) = \left\{ \begin{array}{ll} 1 &\text{if }a=F;\\ f(a_1)+1+f(a_2) &\text{if }a=a_1\>N\>a_2. \end{array}\right.$
I need to prove by induction that $g(a) \leq 2f(a) + 1$.
I've tried drawing trees of the string, finding a pattern in various strings generated by the recursive definition and I really cant seem to be able to find anything.
Thanks for your help.