# 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.

-
By "recursive case", you mean that you start with the string A, and you end up with the string A N A, correct? – Arturo Magidin Apr 18 '11 at 0:02
I think you have the definition of $g$ incorrect, and that what you are trying to prove is that $g(a)\leq 2f(a)-1$. Is this correct? – Arturo Magidin Apr 18 '11 at 0:11
Indeed ! Sorry, I've been working on this all day long, brain is a bit slushy. – slaughterize Apr 18 '11 at 0:28

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.

-
Wow, thanks for the quick and extremely clear answer. I could not have asked for more ! – slaughterize Apr 18 '11 at 0:26