Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 3 down vote accepted

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.

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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.