Proof by induction: String of characters 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.
 A: Your $f$ counts the number of $F$s in the string. I think that your $g$ is meant to be the length, and that the formula should be:
$$g(A) = \left\{\begin{array}{ll}
1 &\text{if }A=F;\\
g(a_1)+g(a_2)+1 &\text{if }A=a_1\>N\>a_2
\end{array}\right.$$
I claim that $g(A)\leq 2f(A)-1$. This will also imply your inequality.
First, we show that the inequality holds for the base case: it does, since $g(F) = 1$, $f(F) = 1$, so $g(F)\leq 2f(F)-1$ holds.
For the inductive step, assume that the result holds for a particular string $A$; that is, $g(A) \leq 2f(A)-1$. You want to show that the result will also hold for the "next string"; the next string is A N A. So you want to compare $f(\text{A N A})$ with $g(\text{A N A})$.
By definition, $f(\text{A N A}) = f(A)+f(A) = 2f(A)$. On the other hand,
$$g(\text{A N A}) = g(A)+1+g(A).$$
By the induction hypothesis, $g(A)\leq 2f(A)-1$, so
$$\begin{align*}
g(\text{A N A}) &= g(A)+1+g(A)\\
&\leq 2f(A)-1 + 1 + 2f(A)-1\\
&= 2f(A)+2f(A) -1\\
&= f(\text{A N A}) + f(\text{A N A}) -1\\
&= 2f(\text{A N A}) -1.
\end{align*}$$
So this shows that if $g(A)\leq 2f(A)-1$, then $g(\text{A N A})\leq 2f(\text{A N A})-1$ will also hold.
By induction, it holds for all the strings that we generate starting with $F$ and following the given rule.
If you really did want $g(A) \leq 2f(A)+1$, then since $2f(A)-1\leq 2f(A)+1$, it will follow from this. 
If your definition for $g$ was correct, then the result also follows: it holds for $A=F$ by direct computation, and if $g(\text{A})\leq 2f(\text{A})+1$, then since $f(\text{A N A}) = 2f(A)$, we have:
$$g(\text{A N A}) = f(A)+f(A)+1 = 2f(A)+1 =f(\text{A N A})+1 \leq 2f(\text{A N A})+1$$
since $f(a)\geq 0$ for all $a$, so the desired inequality holds.
